IEICE Trans - Parameterized Algorithms to Compute Ising Partition Function

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.E101-A No.9 pp.1398-1403
Publication Date: 2018/09/01
Online ISSN: 1745-1337
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>>

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, measurement-based 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 n-vertex 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 parameter-exponential, 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ⁿ, bw(G)^O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.