Quantum annealing speedup over simulated annealing on random Ising chains

摘要

We show clear evidence of a quadratic speedup of a quantum annealing (QA) Schrodinger 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 Schroedinger QA provides a further exponential speedup, i.e., an asymptotic residual error decreasing as a power law τ~μ of the annealing time τ.