Quantum algorithms for classical lattice models

Abstract

We give efficient quantum algorithms to estimate the partition function of (i) the six vertex model on a two-dimensional (2D) square lattice, (ii) the Ising model with magnetic fields on a planar graph, (iii) the Potts model on a quasi 2D square lattice, and (iv) the Z_2 lattice gauge theory on a three-dimensional square lattice. Moreover, we prove that these problems are BQP-complete, that is, that estimating these partition functions is as hard as simulating arbitrary quantum computation. The results are proven for a complex parameter regime of the models. The proofs are based on a mapping relating partition functions to quantum circuits introduced in [Van den Nest et al., Phys. Rev. A 80, 052334 (2009)] and extended here.

21 pages, 12 figures

References in corpus (6)

• On measurement-based quantum computation with the toric code states
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• Unifying all classical spin models in a Lattice Gauge Theory
• On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
• Mapping all classical spin models to a lattice gauge theory
• A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs

Cited by in corpus (25)

• Quantum algorithms: an overview
• Quantum speedup of Monte Carlo methods
• Computational advantage of quantum random sampling
• A Quantum-Quantum Metropolis Algorithm
• Quantum Machine Learning: from physics to software engineering
• Architectures for quantum simulation showing a quantum speedup
• Digital Quantum Simulation of the Statistical Mechanics of a Frustrated Magnet
• Variational inference with a quantum computer
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Quantum Discord and Quantum Computing - An Appraisal
• Classical simulation of short-time quantum dynamics
• Computing partition functions in the one clean qubit model
• Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
• Twins Percolation for Qubit Losses in Topological Color Codes
• A quantum algorithm for additive approximation of Ising partition functions
• Dual correspondence between classical spin models and quantum CSS states
• Fundamental thresholds of realistic quantum error correction circuits from classical spin models
• Low Depth Quantum Circuits for Ising Models
• Phase transition in a noisy Kitaev toric code model
• Analytical percolation theory for topological color codes under qubit loss
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• A quantum information approach to statistical mechanics
• Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
• Systematic study of the completeness of two-dimensional classical ${\varphi }^4$ theory
• Ising models and topological codes: classical algorithms and quantum simulation