Quantum algorithm for an additive approximation of Ising partition functions

Akira Matsuo, Keisuke Fujii, and Nobuyuki Imoto
Phys. Rev. A 90, 022304 – Published 5 August 2014

Abstract

We investigate quantum-computational complexity of calculating partition functions of Ising models. We construct a quantum algorithm for an additive approximation of Ising partition functions on square lattices. To this end, we utilize the overlap mapping developed by M. Van den Nest, W. Dür, and H. J. Briegel [Phys. Rev. Lett. 98, 117207 (2007)] and its interpretation through measurement-based quantum computation (MBQC). We specify an algorithmic domain, on which the proposed algorithm works, and an approximation scale, which determines the accuracy of the approximation. We show that the proposed algorithm performs a nontrivial task, which would be intractable on any classical computer, by showing that the problem that is solvable by the proposed quantum algorithm is BQP-complete. In the construction of the BQP-complete problem coupling strengths and magnetic fields take complex values. However, the Ising models that are of central interest in statistical physics and computer science consist of real coupling strengths and magnetic fields. Thus we extend the algorithmic domain of the proposed algorithm to such a real physical parameter region and calculate the approximation scale explicitly. We found that the overlap mapping and its MBQC interpretation improve the approximation scale exponentially compared to a straightforward constant-depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides partial evidence that there exist no efficient classical algorithm for a multiplicative approximation of the Ising partition functions even on the square lattice. This result supports the observation that the proposed quantum algorithm also performs a nontrivial task in the physical parameter region.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
5 More
  • Received 13 May 2014

DOI:https://doi.org/10.1103/PhysRevA.90.022304

©2014 American Physical Society

Authors & Affiliations

Akira Matsuo1, Keisuke Fujii2,3, and Nobuyuki Imoto1

  • 1Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka, 560-8531, Japan
  • 2The Hakubi Center for Advanced Research, Kyoto University, Yoshida-Ushinomiya-cho, Sakyo-ku, Kyoto 606-8302, Japan
  • 3Graduate School of Informatics, Kyoto University, Yoshida Honmachi, Sakyo-ku, Kyoto 606-8501, Japan

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 90, Iss. 2 — August 2014

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×