Quantum annealing speedup over simulated annealing on random Ising chains

Abstract

We show clear evidence of a quadratic speedup of a quantum annealing (QA) Schroedinger dynamics over a Glauber master-equation simulated annealing (SA) for a random Ising model in one dimension, via an equal-footing exact deterministic dynamics of the Jordan-Wigner fermionized problems. This is remarkable, in view of the arguments of Katzgraber et al., PRX 4, 021008 (2014), since SA does not encounter any phase transition, while QA does. We also find a second remarkable result: that a "quantum-inspired" imaginary-time Schroedinger QA provides a further exponential speedup, i.e., an asymptotic residual error decreasing as a power-law ${\tau }^{-\mu }$ of the annealing time $\tau$.

Revised Abstract and Introduction. Removed 1 figure. Added references. Results unchanged. 5 pages, 2 figures

References in corpus (13)

• Mathematical Foundation of Quantum Annealing
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Adiabatic quantum dynamics of the Lipkin-Meshkov-Glick model
• A Quantum Approach to Classical Statistical Mechanics
• 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
• Cooling dynamics of pure and random Ising chains
• Simulated quantum annealing of double-well and multi-well potentials
• Fast Quantum Methods for Optimization
• Adiabatic approximation for the imaginary-time Schroedinger equation and its application to simulated annealing
• Computational Bottlenecks of Quantum Annealing

Cited by in corpus (16)

• Coherent quantum annealing in a programmable 2000-qubit Ising chain
• Efficient partition of integer optimization problems with one-hot encoding
• Variational Neural Annealing
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability
• Entanglement transitions and quantum bifurcations under continuous long-range monitoring
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Discretized quantum adiabatic process for free fermions and comparison with the imaginary-time evolution
• Engineering non-equilibrium quantum phase transitions via causally gapped Hamiltonians
• On the dynamics of Simulated Quantum Annealing in random Ising chains
• A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• Difference between quantum annealing by imaginary-time and real-time Schrödinger equation of Grover's search
• Time-dependent Real-space Renormalization-Group Approach: application to an adiabatic random quantum Ising model
• Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems
• Mechanism of defect formation in the quantum annealing of the random transverse-field Ising chain