2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$
    – vzn
    Commented Nov 14, 2013 at 16:40
  • $\begingroup$ 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. $\endgroup$
    – hadsed
    Commented Nov 14, 2013 at 19:41
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Nov 14, 2013 at 19:50

2 Answers 2

Reset to default
8
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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