<p>Quantum annealing essentially offers a square-root speed-up over classical simulated annealing in many circumstances. So, yes, it is potentially a faster approach for some optimization problems, but the speed-up isn't enough to make most hard problems tractable.</p>

<p>Unfortunately, you cannot efficiently simulate quantum annealing classically, because any approaches we know of require you to keep track of the state of the system, which requires keeping track of exponentially many parameters (the amplitude of each possible classical state). Thus any attempt to simulate quantum annealing incurs a huge overhead which kills any advantage.</p>

CC BY-SA 3.0
2013-03-31T03:07:54.830Z
Any references for the square-root speedup part?
hadsed
CC BY-SA 3.0
2013-11-15T15:52:20.787Z
See for example http://arxiv.org/abs/0712.1008
Joe Fitzsimons
CC BY-SA 3.0
2015-02-09T17:02:34.413Z
@JoeFitzsimons, what allows this quadratic speedup? Why isn't it available for all problem?
Omar Shehab
CC BY-SA 3.0
2015-02-12T16:08:02.880Z
@JoeFitzsimons, I would like to quote from the discussion (elaborating the acronyms of the methods) of the 2006 paper, "Convergence theorems for quantum annealing written" by Nishimori et al.
Omar Shehab
CC BY-SA 3.0
2015-02-12T16:08:43.553Z
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.
Omar Shehab
CC BY-SA 3.0
2015-02-12T16:09:37.290Z
The convergence of QA is guaranteed if the transverse field decreases as $\Gamma(t) ≈ \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.
Omar Shehab
CC BY-SA 3.0
2015-02-12T16:10:20.177Z
Shouldn't it be enough to argue the supremacy of the speed of QA over that of SA? Thanks.
Omar Shehab
CC BY-SA 3.0
2012-11-26T13:11:47.927Z
2012-11-26T13:11:47.927Z
Joe Fitzsimons
<p>There is a fully solvable model for QA to arbitrary target Hamiltonian:
<a href="https://arxiv.org/pdf/2110.12354.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/2110.12354.pdf</a></p>
<p>It shows that generally, if we do not use hints from oracles, QA has the same performance as some classical Monte-Carlo search algorithms. However, in the case of degeneracy of the target Hamiltonian eigenvalues, the exponential speedup is possible but this case is currently impossible to realize with DWave.</p>

CC BY-SA 4.0
2021-11-04T01:25:17.963Z
2021-11-04T01:25:17.963Z
Nik
<p>There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as opposed to classical simulated annealing is that quantum annealing allows the particle/search point to tunnel through high barriers with probability as a function of barrier width, instead of having to climb all the way over the barrier (which in some cases wouldn't be possible because there wouldn't be enough energy). This is my understanding from here: <a href="http://en.wikipedia.org/wiki/Quantum_annealing" rel="nofollow">http://en.wikipedia.org/wiki/Quantum_annealing</a></p>

<p>If quantum annealing is better than simulated annealing in this fundamental way, would it not be faster to implement QA instead of SA or GA's for solving optimization problems on a classical computer? If so, why aren't people using it? Or are they, and I'm just unaware (in which case I'd love to see references)?</p>

<p>D-Wave seems to be banking on the practicality of their quantum computer, not so much insane accuracy or other more "scientific" pursuits. If it just so happens that D-Wave's computers aren't really quantum, shouldn't we be able to find a fast classically implemented quantum annealing algorithm to compete with the quantumly implemented version also?</p>

CC BY-SA 3.0
2013-11-14T16:40:22.150Z
[QUBO](http://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization) = quantum unconstrained binary optimization. QA is a quantum algorithm therefore implementing it on a classical computer is a classical simulation of a quantum process, which is basically conjectured to generally be slower than the quantum processes.... however "the devil is in the details". yes, recent research results are about precisely quantifying the dwave claimed quantum speedup and is subject to controversy...
vzn
CC BY-SA 3.0
2013-11-14T19:41:21.510Z
Right right, of course. But what I was really trying to get at was if there were some approximations made to reduce that and still have a useful classical quantum annealing algorithm.
hadsed
CC BY-SA 3.0
2013-11-14T19:50:27.810Z
its basically an open question with active/ongoing research of how exactly quantum annealing differs from classical annealing, how to precisely quantify that, what effect the difference (if any) has on computational complexity, and not surprisingly a question at the heart of the dwave claims.
vzn
<quantum-computing><optimization><quantum-information>
Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?
hadsed
# Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

(Asked by: username_0 on 2012-11-09)

There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as opposed to classical simulated annealing is that quantum annealing allows the particle/search point to tunnel through high barriers with probability as a function of barrier width, instead of having to climb all the way over the barrier (which in some cases wouldn't be possible because there wouldn't be enough energy). This is my understanding from here: <http://en.wikipedia.org/wiki/Quantum_annealing>

If quantum annealing is better than simulated annealing in this fundamental way, would it not be faster to implement QA instead of SA or GA's for solving optimization problems on a classical computer? If so, why aren't people using it? Or are they, and I'm just unaware (in which case I'd love to see references)?

D-Wave seems to be banking on the practicality of their quantum computer, not so much insane accuracy or other more "scientific" pursuits. If it just so happens that D-Wave's computers aren't really quantum, shouldn't we be able to find a fast classically implemented quantum annealing algorithm to compete with the quantumly implemented version also?

**Tags:** quantum-computing, optimization, quantum-information
> **Comments:**
> **username_1**: [QUBO](http://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization) = quantum unconstrained binary optimization. QA is a quantum algorithm therefore implementing it on a classical computer is a classical simulation of a quantum process, which is basically conjectured to generally be slower than the quantum processes.... however "the devil is in the details". yes, recent research results are about precisely quantifying the dwave claimed quantum speedup and is subject to controversy...  
> **username_0**: Right right, of course. But what I was really trying to get at was if there were some approximations made to reduce that and still have a useful classical quantum annealing algorithm.  
> **username_1**: its basically an open question with active/ongoing research of how exactly quantum annealing differs from classical annealing, how to precisely quantify that, what effect the difference (if any) has on computational complexity, and not surprisingly a question at the heart of the dwave claims.  

---

## 2 answers

### Answer by username_2 on 2012-11-26. Score: 8 | Accepted answer

Quantum annealing essentially offers a square-root speed-up over classical simulated annealing in many circumstances. So, yes, it is potentially a faster approach for some optimization problems, but the speed-up isn't enough to make most hard problems tractable.

Unfortunately, you cannot efficiently simulate quantum annealing classically, because any approaches we know of require you to keep track of the state of the system, which requires keeping track of exponentially many parameters (the amplitude of each possible classical state). Thus any attempt to simulate quantum annealing incurs a huge overhead which kills any advantage.

> **Comments:**
> **username_0**: Any references for the square-root speedup part?  
> **username_2**: See for example http://arxiv.org/abs/0712.1008  
> **username_3**: @JoeFitzsimons, what allows this quadratic speedup? Why isn't it available for all problem?  
> **username_3**: @JoeFitzsimons, I would like to quote from the discussion (elaborating the acronyms of the methods) of the 2006 paper, "Convergence theorems for quantum annealing written" by Nishimori et al.  
> **username_3**: 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.  
> **username_3**: The convergence of QA is guaranteed if the transverse field decreases as $\Gamma(t) ≈ \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.  
> **username_3**: Shouldn't it be enough to argue the supremacy of the speed of QA over that of SA? Thanks.  

---

### Answer by username_4 on 2021-11-04. Score: 0

There is a fully solvable model for QA to arbitrary target Hamiltonian:
<https://arxiv.org/pdf/2110.12354.pdf>

It shows that generally, if we do not use hints from oracles, QA has the same performance as some classical Monte-Carlo search algorithms. However, in the case of degeneracy of the target Hamiltonian eigenvalues, the exponential speedup is possible but this case is currently impossible to realize with DWave.


---

