Quantum annealing speedup over simulated annealing on random Ising chains

Tommaso Zanca, Giuseppe E. Santoro

Published 2015-11-05Version 1

We show clear evidence of a 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. Annealings are tackled on equal footing, by a deterministic dynamics of the resulting Jordan-Wigner fermionic problems. We find that disorder, without frustration, makes both SA and real-time QA logarithmically slow in the annealing time $\tau$, but QA shows a quadratic speedup with respect to SA. We also find that an imaginary-time Schr\"odinger QA dynamics provides a further exponential speedup, with an asymptotic residual error compatible with a power-law $\tau^{-\mu}$.