Exponentially improved classical and quantum algorithms for three-body Ising models

2013/04/10 by M. Van den Nest, Wolfgang Dür, W. Dür · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Combinatorics #Computer science #Ising model #Markov Chains and Monte Carlo Methods #Mathematics #Observable #Partition (number theory) #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum algorithm #Quantum many-body systems #Quantum mechanics #Statistical physics #cond-mat.stat-mech #cond-mat.str-el #hep-th #quant-ph

paper · pdf · doi:10.1103/physreva.89.012334

published in Physical Review A 89(1) (American Physical Society) · 5 pages + supplementary material

arxiv created 2013/04/10 · openalex publication_date 2014/01/29 · arxiv updated 2014/02/05 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

Abstract

We present an algorithm to approximate partition functions of three-body classical Ising models on two-dimensional lattices of arbitrary genus, in the real-temperature regime. Even though our algorithm is purely classical, it is designed by exploiting a connection to topological quantum systems, namely, the color codes. The algorithm performance (in achievable accuracy) is exponentially better than other approaches that employ mappings between partition functions and quantum state overlaps. In addition, our approach gives rise to a protocol for quantum simulation of such Ising models by simply measuring local observables on color codes.

Citations

• Completeness of the Classical 2D Ising Model and Universal Quantum Computation
• Simulating Ising spin glasses on a quantum computer
• Measurement-based quantum computation with the toric code states
• Speedup via quantum sampling
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• Quantum algorithms for classical lattice models
• Criticality, the area law, and the computational power of PEPS
• Measurement-based quantum computation
• 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
• Quantum algorithm for approximating partition functions
• Fault-tolerant quantum computation by anyons
• Non-Abelian anyons and topological quantum computation
• Stabilizer Codes and Quantum Error Correction