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
add comment

1 Answer

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
1  
See for example arxiv.org/abs/0712.1008 –  Joe Fitzsimons Nov 15 '13 at 15:52
add comment

Your Answer

 
discard

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.