Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet

Abstract

We compare the performance of quantum annealing (QA, through Schrödinger dynamics) and simulated annealing (SA, through a classical master equation) on the $p$-spin infinite range ferromagnetic Ising model, by slowly driving the system across its equilibrium, quantum or classical, phase transition. When the phase transition is second-order ($p=2$, the familiar two-spin Ising interaction) SA shows a remarkable exponential speed-up over QA. For a first-order phase transition ($p\ge 3$, i.e., with multi-spin Ising interactions), in contrast, the classical annealing dynamics appears to remain stuck in the disordered phase, while we have clear evidence that QA shows a residual energy which decreases towards $0$ when the total annealing time $\tau$ increases, albeit in a rather slow (logarithmic) fashion. This is one of the rare examples where a limited quantum speedup, a speedup by QA over SA, has been shown to exist by direct solutions of the Schrödinger and master equations in combination with a non-equilibrium Landau-Zener analysis. We also analyse the imaginary-time QA dynamics of the model, finding a $1/{\tau }^2$ behaviour for all finite values of $p$, as predicted by the adiabatic theorem of quantum mechanics. The Grover-search limit $p(\mathrm{odd})=\infty$ is also discussed.

arXiv commentSubmitted to PRA

References in corpus (48)

• Quantum Mechanics helps in searching for a needle in a haystack
• Ising formulations of many NP problems
• 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
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Quantum Search by Local Adiabatic Evolution
• Defining and detecting quantum speedup
• Mathematical Foundation of Quantum Annealing
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• What is the Computational Value of Finite Range Tunneling?
• Quantum Optimization of Fully-Connected Spin Glasses
• Quantum annealing of the Traveling Salesman Problem
• Quantum versus Classical Annealing of Ising Spin Glasses
• First order phase transition in the Quantum Adiabatic Algorithm
• Probing for quantum speedup in spin glass problems with planted solutions
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Quantum annealing with antiferromagnetic fluctuations
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
• Adiabatic quantum dynamics of the Lipkin-Meshkov-Glick model
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Universal nonequilibrium quantum dynamics in imaginary time
• Reexamining classical and quantum models for the D-Wave One processor
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• On quantum mean-field models and their quantum annealing
• Residual Energies after Slow Quantum Annealing
• Unraveling Quantum Annealers using Classical Hardness
• Optimization by Quantum Annealing: Lessons from Simple Cases
• Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Heavy tails in the distribution of time-to-solution for classical and quantum annealing
• Comparative Study of the Performance of Quantum Annealing and Simulated Annealing
• Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian
• Practical engineering of hard spin-glass instances
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
• Quantum annealing speedup over simulated annealing on random Ising chains
• Open system quantum annealing in mean field models with exponential degeneracy
• Monte Carlo studies of quantum and classical annealing on a double-well

Cited by in corpus (17)

• Efficient partition of integer optimization problems with one-hot encoding
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Lindblad dissipative dynamics in presence of phase coexistence
• Symmetries and conserved quantities of boundary time crystals in generalized spin models
• Reverse quantum annealing of the $p$-spin model with relaxation
• Counterdiabatic driving in the quantum annealing of the $p$-spin model: a variational approach
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Dissipative phase transitions in the fully-connected Ising model with $p$-spin interaction
• A dissipative environment may improve the quantum annealing performances of the ferromagnetic p-spin model
• On the optimal working point in dissipative quantum annealing
• The three phases of quantum annealing: fast, slow, and very slow
• Counterdiabatic Reverse Annealing
• On the dynamics of Simulated Quantum Annealing in random Ising chains
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• Optimal parent Hamiltonians for time-dependent states
• Counterdiabatic Hamiltonians for multistate Landau-Zener problem
• Difference between quantum annealing by imaginary-time and real-time Schrödinger equation of Grover's search