Quantum annealing - studies showing empirical evidence for better performance in comparison with classical computers

Question

Currently, it is not known wheter quantum anneling or algorithms like VQE and QAOA for general purpose quantum computers bring about any increase in computational power. However, there are some studies indicating that in some cases quantum annealing (and VQE and QAOA) shows better performance than simulated annealing and similar heuristics for QUBO on classical computer. To name some of these studies:

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

Could anybody please provide me with links to some other studies (no matter what kind of task being solved) concerning performace of quantum annealing (or QAOA and VQE algorithms)?

Answer 1

Here is one example: the Nature paper that D-Wave put out earlier this year. I have written a small bit below based on what I understood but I should caveat this by saying I am not a quantum annealing or condensed matter expert so my statements may not be exactly precise, but hopefully the gist of it makes sense.

TL;DR They show that quantum annealing is ~10 times faster in solving a toy optimization problem when compared with other classical algorithms. Although of great interest to theoretical physicists, this toy problem does not have any real-world use cases. Expanding this to solve real world problems is not at all obvious, but it’s a nice first example of real “advantage” of quantum annealing, or at least advantage till date. More details are available below and a talk on this paper by one of the authors at ICTP can be found here.

But I also upvoted this question because I would love to see more examples of concrete papers like this!

More in detail

1. A quick bit of context – in optimization problems, most of the time we don’t care to obtain the best solution but getting one that is close enough to the best solution in a much shorter time.
2. In this paper, they obtain a good approximate solution to a specific optimization problem (finding the ground-state of a spin-glass) using a quantum annealer and show with strong evidence that it can solve it faster than other state-of-the-art techniques
3. They use quantum annealing to solve many instances of small spin glass models (16 particles) and a large one (128 particles). They benchmark by 1) using already established but very slow methods to solve the problem exactly and then 2) using several approximation methods (including quantum annealing) to see how much time it takes them to get a good enough approximate solution. The results are a bit difficult to interpret but it seems like quantum annealing gets them to the same “good enough” solution 10-20x faster than classical methods
4. They also have more theoretical arguments for speedups. They plot the time it takes to perform (simulated and quantum) annealing for different levels of approximations. They then use fits and other theories to compute metrics like the Binder cumulant and KZ exponent and show that the time to solution scales as t^(-k) where k is bigger (0.7-1) for quantum annealing than for the other techniques (0.25-0.5). The details and methodologies of these arguments (which are a bit beyond my field of expertise)

Answer 2

I would be very hesitant to read DWave's published results as an indictment against classical solvers, many of which are not as hardcoded towards combinatorial optimization as DWave.

In comparisons against other hardware level solvers, DWave's annealers have had significant competition from non-quantum digital annealers, such as Fujitsu's ASIC for annealing as in https://arxiv.org/abs/2103.08464 and https://arxiv.org/abs/2203.02325. Really it seems that DWave's annealers only outperform on very contrived problems.

Previous analyses have discussed that DWave's typical venue of forward adiabatic annealing may not be enough for universal quantum computation, which may pass on the question of a potential quantum advantage.

For a good picture of adibatic quantum computation and optimization, this review is a great starting place. Of note would be the overview concerning the speed limit of quantum annealers found in the inverse of the cubic/square spectral gap of the evolution hamiltonian.

On the more general question of understanding the performance of various different quantum algorithms for optimization, we understand different paradigms that can even take advantage of both annealing and the QAOA, such as in Brady et al. This kind of thought, coupled with the Zhou-Lukin observation that the QAOA takes advantage of diabatic mechanisms in its evolution (by diabatic we mean that instead of how adiabatic quantum annealing tends to stay in the instantaneous ground state of the evolution hamiltonian, diabatic transitions are those in which the state of the system is in a superposition of various energy states of the hamiltonian), may lead us to finding annealing schedules far faster than the standard quantum annealing picture, as in this example where a problem hamiltonian that is very difficult for the DWave (and standard adiabatic anneals) is solved via a diabatic anneal in quick time. But these improved methods have not, to my knowledge, been implemented in hardware.