Classical Simulation of High Temperature Quantum Ising Models

Abstract

We consider generalized quantum Ising models, including those which could describe disordered materials or quantum annealers, and we prove that for all temperatures above a system-size independent threshold the path integral Monte Carlo method based on worldline heat-bath updates always mixes to stationarity in time $\mathcal{O}(n\log n)$ for an $n$ qubit system, and therefore provides a fully polynomial-time approximation scheme for the partition function. This result holds whenever the temperature is greater than four plus twice the maximum interaction degree (valence) over all qubits, measured in units of the local coupling strength. For example, this implies that the classical simulation of the thermal state of a superconducting device modeling a frustrated quantum Ising model with maximum valence of 6 and coupling strengths of 1 GHz is always possible at temperatures above 800 mK. Despite the quantum system being at high temperature, the classical spin system resulting from the quantum-to-classical mapping contains strong couplings which cause the single-site Glauber dynamics to mix slowly, therefore this result depends on the use of worldline updates (which are a form of cluster updates that can be implemented efficiently). This result places definite constraints on the temperatures required for a quantum advantage in analog quantum simulation with various NISQ devices based on equilibrium states of quantum Ising models.

10 pages, 1 figure

References in corpus (19)

• Quantum Computing in the NISQ era and beyond
• Adiabatic Quantum Computing
• Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
• Worm Algorithm for Continuous-space Path Integral Monte Carlo Simulations
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Universal Quantum Hamiltonians
• Finite-range interacting Ising quantum magnets with Rydberg atoms in optical lattices - From Rydberg superatoms to crystallization
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• On the Computational Complexity of Curing the Sign Problem
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Merlin-Arthur Games and Stoquastic Complexity
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• Adiabatic optimization versus diffusion Monte Carlo
• A general lower bound for mixing of single-site dynamics on graphs
• Polynomial-time classical simulation of quantum ferromagnets
• Two-local qubit Hamiltonians: when are they stoquastic?
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians