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>>
Buy this Article



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*(cp) 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{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.