Is there any rigorous proof that Quantum Annealing (QA) is of any benefit (e.g. in terms of time to optimal solution, convergence rate, etc.) for a specific problem? Or any empirical evidence for the same?

I can find QUBO-based QA implementation for basically every computational problem from all of the major complexity classes, but what I can’t find is any scientifically reliable and peer-reviewed publication where state-of-the-art classical algorithms are outperformed (theoretically or empirically).

Is this due to me or is there simply none?


1 Answer 1


Currently, there is no proof that QA offers any advantage. According to Preskill (see below) there is even a little hope that it will be ever found. Therefore, QA algorithms (QAOA and VQE) or D-Wave annealers are currently considered to be heuristics offering some advantage in some cases, for example:

On the other hand, there are some sceptics (see for example The pitfalls of planar spin-glass benchmarks) arguing that QA provides no advantage at all and that tests of QA are adapted to special cases which detter objectivness of the test.

To get critical assessment of QA abilities (i.e. no overly pessimistic and not overly optimistic), you would recommend reading Preskill's article Quantum Computing in the NISQ era and beyond, particularly chapters 6.1 and 6.3


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.