In both algorithms objective functions, that will be executed with non quantum computers, are used. Both algorithms are methods for finding the global minimum of a given objective function.

From wikipedia:

Quantum annealing can be compared to simulated annealing (SA), whose "temperature" parameter plays a similar role to QA's tunneling field strength.

What is meant by "tunneling field strength"?

The choice of next candidate state seems to be the only difference between the algorithms, is that correct?

Finally, what are the advantages of Quantum annealing? Is it faster, or is it just better at handling local minima?

  • 1
    Hi Pavel. Algorithmic questions are perfectly on topic on Programmers, and as you've noticed yours was answered pretty quickly. That said, I'd like to point you to our new sister site, Computer Science Stack Exchange that's more focused to computer science questions than we are. Not for this question, but if you have more questions that require mathematical answers, you might want to try their site first (if only because they support MathJax - a display engine for maths - and we, intentionally, don't). – yannis Apr 10 '13 at 13:30

what is "tunneling field strength"?

The distance in which you randomly select the next candidate.

Choosing of next candidate state the only difference between algorithms, is it?

No. Normal simulated annealing works with fixed parameter, but quantum annealing always works with gradually decreasing parameter more like adaptive simulated annealing.

What advantage of Quantum annealing? Is it faster, or is it just better handle local minima?

It can handle wider, but slightly different set of problems. Simulated annealing only works when the barriers separating minima are relatively low, but they can be any wide. The adaptive version compensates a bit, but it remains inefficient when the barriers are high.

Quantum annealing is not limited by barrier heights and because it starts with the parameter equal to diameter of the problem space it is not limited by their widths either. However it will have problems finding global minimum surrounded by large area of high values, because if it does not hit the small low area early, it won't get there after the parameter decreases.

So quantum annealing will usually give better results, but it might not depending on the specific problem.

| improve this answer | |
  • Thank you for reply! What part of that algorithm depends on quantum hardware and quantum gates? D-Wave using the same approach for quantum computing, and I want to know, what part of algorithm is executed by quantum computer? The client of BlackBox compiler defines and implements only objective function and it executing in regular computer. – BergP Apr 10 '13 at 13:25
  • 1
    @PavelKatunin: Quantum annealing is a normal algorithm for normal computers working on principle of Turing machine. It is only called "quantum" because it is inspired by quantum tunnelling. I have no idea which parts of it could be sped up using quantum hardware. – Jan Hudec Apr 10 '13 at 13:45
  • Thank you! My bad, I read the wrong information on the subject! :) – BergP Apr 10 '13 at 13:56
  • but in some sources phys.org/news/… there is information about D-Wave quantum computers used quantum annealing, have you any idea how? kurzweilai.net/d-wave-reveals, and in wiki page about quantum annealing there are some links on D-Wave site – BergP Apr 10 '13 at 14:21
  • 1
    @JanHudec: There is a company called D-Wave that has physically implemented QA using actual quantums. The nice thing about implementing this algorithm is that it doesn't matter if there is some noise in the system, since it is only a heuristic anyway. Controlling noise is one of the biggest hurdles in building a workable quantum computer. – Jörg W Mittag Apr 10 '13 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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