Parameterized Algorithms to Compute Ising Partition Function

• HIRAISHI Hidefumi

  Graduate School of Information Science and Technology, The University of Tokyo

• IMAI Hiroshi

  Graduate School of Information Science and Technology, The University of Tokyo

• IWATA Yoichi

  National Institute of Informatics

• LIN Bingkai

  National Institute of Informatics

Abstract

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^{ \frac{\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(\tilde{G})})$ time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph $\tilde{G}$ with width $rw(\tilde{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.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E101.A (9), 1398-1403, 2018-09-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• Ising model
• partition function
• branch decomposition
• rank decomposition
• fixed parameter tractability

Details

• CRID: 1390845712992648704
• NII Article ID: 130007479457
• DOI: 10.1587/transfun.e101.a.1398
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E101.A/9/E101.A_1398/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed