2
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ i will agree with that "I assume to settle the question we need to find a quantum annealing schedule which is faster than all simulated annealing schedules", reading referenced paper for further info $\endgroup$ – Nikos M. Apr 27 '15 at 21:01
  • 1
    $\begingroup$ furthermorte you might want to look into the No Free Lunch set of related theorems on optimisation $\endgroup$ – Nikos M. Apr 27 '15 at 21:02
  • 1
    $\begingroup$ well the NFL theorem(s) have applications to whole range of optimisation methods (and not for specific details). So by statistical arguments it is shown that the efficiency of optimisation methods is uniform over all methods (no method is better on average than another, of course there are further assumptions and implications), but it relates to your question quoted in my 1st comment $\endgroup$ – Nikos M. Apr 28 '15 at 9:30
  • 1
    $\begingroup$ it is clear that diferent algorithms and approaches can have different efficiency and performance for a specific problem or specific instance of a problem the NFL is statistical and asumes all potential methods over the space of problems at once $\endgroup$ – Nikos M. Apr 28 '15 at 9:41
  • 1
    $\begingroup$ also one would have to bare in mind that quantum computing or quantum methods have not been shown to be superior to classical methods in general (meaning methods not using quantum formalism per se in an obvious way). This mostly stems from other physical arguments (which is for another discussion) $\endgroup$ – Nikos M. Apr 28 '15 at 9:46
1
$\begingroup$

In Rough Large Deviation Estimates for Simulated Annealing: Application to Exponential Schedules a theoretical justification for the exponential cooling schedule was given. The results there basically state that for a fixed computation time N you can always choose an appropriate constant $ C= f(N)$ for an exponential cooling schedule $ \beta = \beta_0 \cdot \exp \left( n f(N) \right) $ with $ f(N) \sim N^{-1} \ln\left(N\right) $, such that simulated annealing will converge. So in light of these results I would say it is clear that simulated annealing can converge faster than quantum annealing, at least for the quantum annealing schedule result you cited. Although, it seems you have to tweak the cooling schedule to the computation time.

A nice overview of theoretically grounded acceleration of simulate annealing is given here Theoretically Grounded Acceleration Techniques for Simulated Annealing

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.