<p>In <a href="https://projecteuclid.org/euclid.aop/1176989682" rel="nofollow">Rough Large Deviation Estimates for Simulated Annealing: Application to Exponential Schedules</a> 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.</p>

<p>A nice overview of theoretically grounded acceleration of simulate annealing is given here <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-30504-7_13" rel="nofollow">Theoretically Grounded Acceleration Techniques for Simulated Annealing</a></p>

CC BY-SA 3.0
2016-06-11T03:05:32.213Z
2016-06-11T03:11:08.830Z
2016-06-11T03:11:08.830Z
mithrawnuruodo
<p>How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms?</p>

<p>In <a href="http://arxiv.org/abs/quant-ph/0608154" rel="nofollow">Convergence theorems for quantum annealing</a> by Morita and Nishimori, it has been shown that QA performs better than SA. Let's me quote from the Discussion section:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

<p>So, is the performance comparison between SA and QA settled? Is yes, how? If no, how can we do it?</p>

CC BY-SA 3.0
2015-04-27T21:01:03.463Z
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
Nikos M.
CC BY-SA 3.0
2015-04-27T21:02:44.807Z
furthermorte you might want to look into the [No Free Lunch](http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization) set of related theorems on optimisation
Nikos M.
CC BY-SA 3.0
2015-04-28T05:12:08.840Z
@NikosM., thanks for sharing the Wiki page on the No Free Lunch theorem. I am afraid it might not be applicable when we compare between simulated annealing and quantum annealing. In simulated annealing, a worse candidate configuration might be chosen with some probability (to avoid local minima). But, in quantum annealing, a configuration with higher energy is never accepted. Am I making sense?
Omar Shehab
CC BY-SA 3.0
2015-04-28T09:30:24.873Z
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
Nikos M.
CC BY-SA 3.0
2015-04-28T09:38:52.067Z
@NikosM. What if we fix a problem (not a class of problem). Let's say we pick the simple undirected graph isomorphism problem. The optimization version of this problem is given in Eq. 4 of [this paper][1]. Is it possible to find the best SA schedule to minimize this expression? [1]:http://arxiv.org/pdf/1503.06453v1.pdf
Omar Shehab
CC BY-SA 3.0
2015-04-28T09:41:05.767Z
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
Nikos M.
CC BY-SA 3.0
2015-04-28T09:46:39.027Z
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)
Nikos M.
<cc.complexity-theory><optimization><quantum-computing><boolean-functions><physics>
Complexity: simulated annealing vs. quantum annealing
Omar Shehab
# Complexity: simulated annealing vs. quantum annealing

(Asked by: username_0 on 2015-04-20)

How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms?

In [Convergence theorems for quantum annealing](http://arxiv.org/abs/quant-ph/0608154) 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?

**Tags:** cc.complexity-theory, optimization, quantum-computing, boolean-functions, physics
> **Comments:**
> **username_1**: 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  
> **username_1**: furthermorte you might want to look into the [No Free Lunch](http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization) set of related theorems on optimisation  
> **username_0**: @NikosM., thanks for sharing the Wiki page on the No Free Lunch theorem. I am afraid it might not be applicable when we compare between simulated annealing and quantum annealing. In simulated annealing, a worse candidate configuration might be chosen with some probability (to avoid local minima). But, in quantum annealing, a configuration with higher energy is never accepted. Am I making sense?  
> **username_1**: 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  
> **username_0**: @NikosM. What if we fix a problem (not a class of problem). Let's say we pick the simple undirected graph isomorphism problem. The optimization version of this problem is given in Eq. 4 of [this paper][1]. Is it possible to find the best SA schedule to minimize this expression? [1]:http://arxiv.org/pdf/1503.06453v1.pdf  
> **username_1**: 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  
> **username_1**: 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)  

---

## 1 answers

### Answer by username_2 on 2016-06-11. Score: 1 | Accepted answer

In [Rough Large Deviation Estimates for Simulated Annealing: Application to Exponential Schedules](https://projecteuclid.org/euclid.aop/1176989682) 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](http://link.springer.com/chapter/10.1007%2F978-3-642-30504-7_13)


---

