
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Parameterized Algorithms to Compute Ising Partition Function
Hidefumi HIRAISHI Hiroshi IMAI Yoichi IWATA Bingkai LIN
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E101A
No.9
pp.13981403 Publication Date: 2018/09/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E101.A.1398
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: Ising model, partition function, branch decomposition, rank decomposition, fixed parameter tractability,
Full Text: PDF(882.1KB)>>
Summary:
Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurementbased quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An $O^*(2^{ rac{omega}{2} bw(G)})$time algorithm is developed for the partition function on nvertex graph G with branch decomposition of width bw(G), where O^{*} ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of $O^*(4^{rw( ilde{G})})$ time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph $ ilde{G}$ with width $rw( ilde{G})$. These algorithms are parameterexponential, i.e., O^{*}(c^{p}) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O^{*}(min{2^{n}, bw(G)^{O(bw(G))}})) with a negative result in terms of the cliquewidth, related to the rankwidth, under ETH.

