Simulating Ising Spin Glasses on a Quantum Computer

Abstract

A linear-time algorithm is presented for the construction of the Gibbs distribution of configurations in the Ising model, on a quantum computer. The algorithm is designed so that each run provides one configuration with a quantum probability equal to the corresponding thermodynamic weight. The partition function is thus approximated efficiently. The algorithm neither suffers from critical slowing down, nor gets stuck in local minima. The algorithm can be A linear-time algorithm is presented for the construction of the Gibbs distribution of configurations in the Ising model, on a quantum computer. The algorithm is designed so that each run provides one configuration with a quantum probability equal to the corresponding thermodynamic weight. The partition function is thus approximated efficiently. The algorithm neither suffers from critical slowing down, nor gets stuck in local minima. The algorithm can be applied in any dimension, to a class of spin-glass Ising models with a finite portion of frustrated plaquettes, diluted Ising models, and models with a magnetic field. applied in any dimension, to a class of spin-glass Ising models with a finite portion of frustrated plaquettes, diluted Ising models, and models with a magnetic field.

24 pages, 3 epsf figures, replaced with published and significantly revised version. More info available at http://www.fh.huji.ac.il/~dani/ and http://www.fiz.huji.ac.il/staff/acc/faculty/biham

References in corpus (10)

• Mixed State Entanglement and Quantum Error Correction
• Good Quantum Error-Correcting Codes Exist
• Strengths and Weaknesses of Quantum Computing
• Measurement of conditional phase shifts for quantum logic
• From quantum cellular automata to quantum lattice gases
• Simulations of Many-Body Quantum Systems by a Quantum Computer
• Quantum Physics and Computers
• Fault Tolerant Quantum Computation with Constant Error
• Exact Solution of a Three-Dimensional Dimer System
• Error correction and symmetrization in quantum computers

Cited by in corpus (59)

• Quantum Simulation
• Quantum Computing
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Quantum Simulations of Lattice Gauge Theories using Ultracold Atoms in Optical Lattices
• Quantum speedup of Monte Carlo methods
• From transistor to trapped-ion computers for quantum chemistry
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Observation of Lee-Yang zeros
• The problem of equilibration and the computation of correlation functions on a quantum computer
• Adiabatic Quantum Simulation of Quantum Chemistry
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Quantum simulation of a three-body interaction Hamiltonian on an NMR quantum computer
• Quantum Computing: Pro and Con
• Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
• Tensor lattice field theory with applications to the renormalization group and quantum computing
• Rapid adiabatic preparation of injective PEPS and Gibbs states
• Completeness of the classical 2D Ising model and universal quantum computation
• Digital Quantum Simulation of the Statistical Mechanics of a Frustrated Magnet
• Classical spin models and the quantum stabilizer formalism
• Exact solution of multi-angle quantum many-body collective neutrino flavor oscillations
• Introduction to Quantum Algorithms for Physics and Chemistry
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Quantum algorithms for spin models and simulable gate sets for quantum computation
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• Quantum Sampling Algorithms for Near-Term Devices
• Quantum algorithms for classical lattice models
• On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
• Simulation of Classical Thermal States on a Quantum Computer: A Transfer Matrix Approach
• Quantum Computation of a Complex System : the Kicked Harper Model
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Quantum state manipulation of trapped atomic ions
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• Quantum Chaos and Quantum Algorithms
• Quantum Algorithms for Quantum Chemistry based on the sparsity of the CI-matrix
• Completeness of classical spin models and universal quantum computation
• A quantum algorithm for additive approximation of Ising partition functions
• Twins Percolation for Qubit Losses in Topological Color Codes
• Classical Ising model test for quantum circuits
• Dual correspondence between classical spin models and quantum CSS states
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• Fundamental thresholds of realistic quantum error correction circuits from classical spin models
• Eigenvalue Estimation of Differential Operators
• An algorithmic proof for the completeness of two-dimensional Ising model
• Low Depth Quantum Circuits for Ising Models
• Quantum Computing of Poincare Recurrences and Periodic Orbits
• Phase transition in a noisy Kitaev toric code model
• A quantum information approach to statistical mechanics
• Arbitrage risk induced by transaction costs
• Implementation of a Quantum Algorithm to Estimate the Energy of a Particle in a Finite Square Well Potential on IBM Quantum Computer
• Analytical percolation theory for topological color codes under qubit loss
• Classical spin systems and the quantum stabilizer formalism: general mappings and applications
• Quantum simulation of classical thermal states
• Quantum algorithm for exact Monte Carlo sampling
• Quantum sampling for the Euclidean path integral of lattice gauge theory
• Noisy Toric code and random bond Ising model: The error threshold in a dual picture
• Towards quantum simulation of spin systems using continuous variable quantum devices
• Systematic study of the completeness of two-dimensional classical ${\varphi }^4$ theory
• Ising models and topological codes: classical algorithms and quantum simulation
• Quantum computing classical physics