Quantum algorithms for classical lattice models

2011/04/13 by G. De las Cuevas, G De las Cuevas, W. Dür +5 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Lattice (music) #Lattice model (finance) #Markov Chains and Monte Carlo Methods #Mathematical proof #Partition function (quantum field theory) #Planar #Potts model #Quantum #Quantum Computing Algorithms and Architecture #Quantum algorithm #Random Matrices and Applications #Square lattice #cond-mat.stat-mech #hep-lat #hep-th #quant-ph

paper · pdf · doi:10.1088/1367-2630/13/9/093021

published as New J.Phys.13:093021,2011 · 21 pages, 12 figures

arxiv created 2011/04/13 · openalex publication_date 2011/09/09 · arxiv updated 2011/09/16 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

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 3D 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 by Van den Nest et al (2009 Phys.Rev. A 80 052334) and extended here.

Citations

• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Simulating Ising spin glasses on a quantum computer
• Measurement-based quantum computation with the toric code states
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• Duality in Generalized Ising Models and Phase Transitions without Local Order Parameters
• Distance measures to compare real and ideal quantum processes
• The renormalization group: Critical phenomena and the Kondo problem
• Concatenated tensor network states
• Quantum algorithms for spin models and simulable gate sets for quantum computation
• Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
• 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
• The BQP-hardness of approximating the Jones polynomial
• An introduction to lattice gauge theory and spin systems
• Algorithms for quantum computation: discrete logarithms and factoring
• Quantum Computation

Cited by

• Quantum Annealing Algorithms for Estimating Ising Partition Functions

Related

• Quantum algorithms for spin models and simulable gate sets for quantum computation
• A quantum algorithm for additive approximation of Ising partition functions
• Completeness of the Classical 2D Ising Model and Universal Quantum Computation
• On the quantum computational complexity of the Ising spin glass partition function and of knot invariants
• Efficient Algorithms for Approximating Quantum Partition Functions