A quantum algorithm for additive approximation of Ising partition functions

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 Van den Nest, Dür, and 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 does a nontrivial task, which would be intractable on any classical computer, by showing the problem solvable by the proposed quantum algorithm are 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 improves the approximation scale exponentially compared to a straightforward constant depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides us a 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 that the proposed quantum algorithm does a nontrivial task also in the physical parameter region.

18 pages, 12 figures

References in corpus (23)

• Measurement-based quantum computation with cluster states
• Multi-party entanglement in graph states
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Blind quantum computation protocol in which Alice only makes measurements
• Determinism in the one-way model
• Generalized Flow and Determinism in Measurement-based Quantum Computation
• Simulating Ising Spin Glasses on a Quantum Computer
• The BQP-hardness of approximating the Jones Polynomial
• Inapproximability of the Tutte polynomial
• On measurement-based quantum computation with the toric code states
• Completeness of the classical 2D Ising model and universal quantum computation
• Classical spin models and the quantum stabilizer formalism
• A quantum cellular automaton for universal quantum computation
• Quantum algorithms for spin models and simulable gate sets for quantum computation
• Unifying all classical spin models in a Lattice Gauge Theory
• Quantum algorithms for classical lattice models
• Simulation of Classical Thermal States on a Quantum Computer: A Transfer Matrix Approach
• Mapping all classical spin models to a lattice gauge theory
• The U(1) Lattice Gauge Theory Universally Connects All Classical Models with Continuous Variables, Including Background Gravity
• An algorithmic proof for the completeness of two-dimensional Ising model
• Low Depth Quantum Circuits for Ising Models
• Efficiency of free energy calculations of spin lattices by spectral quantum algorithms
• Ising models and topological codes: classical algorithms and quantum simulation

Cited by in corpus (9)

• Quantum speedup of Monte Carlo methods
• Architectures for quantum simulation showing a quantum speedup
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Measurement-based quantum simulation of Abelian lattice gauge theories
• Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
• Sumcheck-based delegation of quantum computing to rational server
• Phase context decomposition of diagonal unitaries for higher-dimensional systems
• Computational quantum-classical boundary of complex and noisy quantum systems
• Quantum estimation bound of Gaussian matrix permanent