Quantum annealing speedup over simulated annealing on random Ising chains
Tommaso Zanca, Giuseppe E. Santoro · Physical review. B./Physical review. B · 2016
We show clear evidence of a quadratic speedup of a quantum annealing (QA) Schr\"odinger 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 H. G. Katzgraber et al. [Phys. Rev. X 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 Schr\"odinger QA provides a further exponential speedup, i.e., an asymptotic residual error decreasing as a power law ${\ensuremath{\tau}}^{\ensuremath{-}\ensuremath{\mu}}$ of the annealing time $\ensuremath{\tau}$.