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.

Submitted to PRA

References in corpus (11)

• Mathematical Foundation of Quantum Annealing
• Quantum annealing with antiferromagnetic fluctuations
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Adiabatic quantum dynamics of the Lipkin-Meshkov-Glick model
• Reexamining classical and quantum models for the D-Wave One processor
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• On quantum mean-field models and their quantum annealing
• Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
• Comparative Study of the Performance of Quantum Annealing and Simulated Annealing

Cited by in corpus (8)

• Digitized-counterdiabatic quantum approximate optimization algorithm
• Symmetries and conserved quantities of boundary time crystals in generalized spin models
• Reverse quantum annealing of the $p$-spin model with relaxation
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Dissipative phase transitions in the fully-connected Ising model with $p$-spin interaction
• The three phases of quantum annealing: fast, slow, and very slow
• Counterdiabatic Reverse Annealing
• Optimal parent Hamiltonians for time-dependent states