The quantum Monte Carlo quantum annealing (QMC-QA1) or discrete-time simulated quantum annealing (SQA2) algorithm(s) performed better than the tested D-Wave device in recent studies:
We establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing: we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with 95% confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: simulated quantum annealing exhibits the best scaling by a significant margin.
Since both the D-Wave device and SQA outperform SA for certain problem instances, this gives the impression that SQA is a sort of quantum-inspired algorithm. The newer study testing the D-Wave 2000Q processor also finds that its performance correlates better with a proposed classical model labeled "spin-vector Monte Carlo (SVMC) algorithm" in that study than with SQA:
We use this to argue that a key reason for the quantum annealer’s slowdown relative to SQA is its sub-optimally high temperature, which causes it to behave more like SVMC. Thus, the strong performance of SQA on the logical-planted instance class suggests that this class is a good target or basis for the exploration of an eventual quantum speedup using QA hardware.
If we ignore the background D-Wave story, can we still conclude that SQA is a quantum-inspired optimization algorithm that outperforms classical simulated annealing (and maybe other optimization algorithms) for certain problems? It depends. If the goal is actually to find the ground state of some quantum system, then the answer is yes. But if the goal is to have a general purpose optimization algorithm similar to simulated annealing, then the answer is no.
- Martoňák, R., Santoro, G. E. & Tosatti, E. Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model. Phys. Rev. B 66, 094203 (2002). URL http://link.aps.org/doi/10.1103/PhysRevB.66.094203
- Santoro, G. E., Martoňák, R., Tosatti, E. & Car, R. Theory of quantum annealing of an Ising spin glass. Science 295, 2427–2430 (2002). URL http://dx.doi.org/10.1126/science.1068774.