How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms?
In Convergence theorems for quantum annealing by Morita and Nishimori, it has been shown that QA performs better than SA. Let's me quote from the Discussion section:
We have proved strong ergodicity of the inhomogeneous Markov chains associated with Quantum Annealing using both Path Integral Monte Carlo and Green's Function Monte Carlo methods, mainly with the application to the Transverse Field Ising Model in mind, which covers a wide range of combinatorial optimization problems. Our proof is quite general in the sense that it does not depend on the spatial dimensionality or the lattice structure of the system. The convergence of QA is guaranteed if the transverse field decreases as $\Gamma(t) \approx \frac{const}{t^c}$ asymptotically. This annealing schedule for the transverse field is faster than the temperature-annealing schedule, the log-inverse law, found by Geman and Geman for Simulated Annealing.
Does this result settle the question of the performances for Simulated vs. Quantum annealings? I have a feeling that we should put a little more context here.
I assume to settle the question we need to find a quantum annealing schedule which is faster than all simulated annealing schedules. The problem can be reduced to finding a quantum annealing schedule which is faster than the fastest simulated annealing schedule. Now, to me, the fastest simulated annealing schedule makes sense only when we know what optimization problem we are talking about. We cannot find the fastest simulated annealing schedule for all conceivable optimization problems. That just doesn't make sense to me.
So, is the performance comparison between SA and QA settled? Is yes, how? If no, how can we do it?