Is there any rigorous proof that Quantum Annealing provides a quantum advantage?

Question

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?

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:

• Towards Prediction of Financial Crashes with a D-Wave Quantum Computer
• Formulating and Solving Routing Problems on Quantum Computers

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