Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs

Abstract

We discuss an Ising spin glass where each $S=1/2$ spin is coupled antiferromagnetically to three other spins (3-regular graphs). Inducing quantum fluctuations by a time-dependent transverse field, we use out-of-equilibrium quantum Monte Carlo simulations to study dynamic scaling at the quantum glass transition. Comparing the dynamic exponent and other critical exponents with those of the classical (temperature-driven) transition, we conclude that quantum annealing is less efficient than classical simulated annealing in bringing the system into the glass phase. Quantum computing based on the quantum annealing paradigm is therefore inferior to classical simulated annealing for this class of problems. We also comment on previous simulations where a parameter is changed with the simulation time, which is very different from the true Hamiltonian dynamics simulated here.

arXiv comment5 pages, 3 figures

References in corpus (30)

• Nonequilibrium dynamics of closed interacting quantum systems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum annealing with more than one hundred qubits
• Dynamics of a Quantum Phase Transition
• Theory of Quantum Annealing of an Ising Spin Glass
• Dynamics of a Quantum Phase Transition and Relaxation to a Steady State
• Quantum Annealing and Analog Quantum Computation
• Dynamics of quantum phase transition: exact solution in quantum Ising model
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Universal adiabatic dynamics across a quantum critical point
• Phase Transitions in the Coloring of Random Graphs
• Quench dynamics near a quantum critical point
• Stochastic series expansion method for quantum Ising models with arbitrary interactions
• First order phase transition in the Quantum Adiabatic Algorithm
• Landau theory of quantum spin glasses of rotors and Ising spins
• Zero--Temperature Quantum Phase Transition of a Two--Dimensional Ising Spin--Glass
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• From quantum mechanics to classical statistical physics: generalized Rokhsar-Kivelson Hamiltonians and the "Stochastic Matrix Form" decomposition
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Universal nonequilibrium quantum dynamics in imaginary time
• Adiabatic Quantum Computing for Random Satisfiability Problems
• Dynamic scaling at classical phase transitions approached through non-equilibrium quenching
• Potts Glass on Random Graphs
• Comparative Study of the Performance of Quantum Annealing and Simulated Annealing
• Quasi-adiabatic quantum Monte Carlo algorithm for quantum evolution in imaginary time
• Microscopic theory of non-adiabatic response in real and imaginary time
• Relaxational behavior of the infinite-range Ising spin-glass in a transverse field
• Solving the Schroedinger equation for the Sherrington-Kirkpatrick model in a transverse field

Cited by in corpus (47)

• Adiabatic Quantum Computing
• Coherent quantum annealing in a programmable 2000-qubit Ising chain
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• Kibble-Zurek scaling in the Yang-Lee edge singularity
• Hybrid quantum annealing for larger-than-QPU lattice-structured problems
• Theory of Driven Nonequilibrium Critical Phenomena
• A dissipative environment may improve the quantum annealing performances of the ferromagnetic p-spin model
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Off-Diagonal Expansion Quantum Monte Carlo
• Quantum annealing speedup over simulated annealing on random Ising chains
• Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
• Universal dynamic scaling in three-dimensional Ising spin glasses
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Simulated quantum annealing of double-well and multi-well potentials
• Dynamic scaling of topological ordering in classical systems
• Simulating disordered quantum systems via dense and sparse restricted Boltzmann machines
• Hybridized Kibble-Zurek scaling in the driven critical dynamics across an overlapping critical region
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• Kibble-Zurek mechanism in a one-dimensional incarnation of deconfined quantum critical point
• Nonequilibrium dynamics of the Ising chain in a fluctuating transverse field
• Dual time scales in simulated annealing of a two-dimensional Ising spin glass
• Exploring Quantum Annealing Architectures: A Spin Glass Perspective
• Ising Hamiltonian Minimization: Gain-Based Computing with Manifold Reduction of Soft-Spins vs Quantum Annealing
• Driving Driven Lattice Gases to Identify Their Universality Classes
• Dynamic scaling in the 2D Ising spin glass with Gaussian couplings
• Nonequilibrium critical dynamics in the quantum chiral clock model
• Scaling in driven dynamics starting in the vicinity of a quantum critical point
• Self-similarity breaking: Anomalous nonequilibrium finite-size scaling and finite-time scaling
• Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
• Quantum optimization within lattice gauge theory model on a quantum simulator
• Finite-time scaling beyond the Kibble-Zurek prerequisite in Dirac systems
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Nonequilibrium Critical Dynamics with Emergent Supersymmetry
• Effects of low-lying excitations on ground-state energy and energy gap of Sherrington-Kirkpatrick model in transverse field
• The performance of the quantum adiabatic algorithm on spike Hamiltonians
• Nonequilibrium Dynamics of Dirac Quantum Criticality in Imaginary Time
• Driven Critical Dynamics in Tricitical Point
• Theory of Critical Phenomena with Memory
• Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
• Theory of Critical Phenomena with Long-Range Temporal Interaction
• Separation of the Kibble-Zurek Mechanism from Quantum Criticality
• Optimization via Quantum Preconditioning
• Is there Kibble-Zurek scaling of topological defects in first-order phase transitions?
• Effects of dynamical paths on the energy gap and the corrections to free energy in path integrals of mean-field quantum spin systems
• Dissipation-Induced Deviations from Kibble-Zurek Scaling in Non-Hermitian Quantum Annealing