Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
QUBO = 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 Nov 14 '13 at 16:40
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 Nov 14 '13 at 19:41
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 Nov 14 '13 at 19:50

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
Any references for the square-root speedup part? –  hadsed Mar 31 '13 at 3:07
See for example arxiv.org/abs/0712.1008 –  Joe Fitzsimons Nov 15 '13 at 15:52
@JoeFitzsimons, what allows this quadratic speedup? Why isn't it available for all problem? –  Omar Shehab Feb 9 at 17:02
@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 Feb 12 at 16:08
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 Feb 12 at 16:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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