More investigation of the Dwave quantum annealing system in regards to speedup and quantumness of its operation

1. Alex Selby has written his own specialist solver for one class of the McGeoch and Wang benchmarks that significantly outperforms the software (and D-Wave quantum annealing machine) tested by McGeoch and Wang on those benchmarks—and who provides the Python code.

Summary Preliminary conclusions

* FPTYTO ~= 10^5 faster than D-Wave (439 qubit) for Quadratic Assignment Problem (QAP)
* FPTYTO ~= 10^3 faster than D-Wave (439 qubit) for native Quadratic Unconstrained Binary Optimization (QUBO) problems in

FPTYTO is a very simple and short python program which starts with a random permutation, and tries transpositions until no more benefit is possible, then it repeats until it runs out of time. You have to reduce the running time of the python program to about 1 or 2 seconds to get a comparable result, so we can call that 10^3 times faster. Converting to C code adds another two orders of magnitude (Hannes Uppman for verifying this), that is 10^5 times faster overall. This is for a single core of a normal desktop computer.

New exhaust function that proves optimality added to qubo.c. In all of {0,1} [easy] cases (the same state variables that D-Wave used), the answers that were previously only heuristically generated here are now verified optimal.

Conversations with Prof McGeoch have now resulted in identification of the correct distribution for Qij. These instances seem to be intermediate between the cases termed {0,1} (easy) and those termed {−1,1} (hard).

There will need to be more proof and runtimes where the hard problems are solved to optimal solutions Alex Selby’s software.

DWave’s 512 qubit system is 3 to 5 times faster than the Dwave 439 qubit system.

2. In a recent preprint (arXiv:1305.4904) entitled Classical signature of quantum annealing” Smolin and Smith point out that a bimodal distribution presented in (arXiv:1304.4595) for the success probability in the D-Wave device does not in itself provide sufficient evidence for quantum annealing, by presenting a classical model that also exhibits bimodality. Here we analyze their model and in addition present a similar model derived from the semi-classical limit of quantum spin dynamics, which also exhibits a bimodal distribution. We find that in both cases the correlations between the success probabilities of these classical models and the D-Wave device are weak compared to the correlations between a simulated quantum annealer and the D-Wave device. Indeed, the evidence for quantum annealing presented in arXiv:1304.4595 is not limited to the bimodality, but relies in addition on the success probability correlations between the D-Wave device and the simulated quantum annealer. The Smolin-Smith model and our semi-classical spin model both fail this correlation test.

To summarize, Smolin and Smith are correct to point out that it is insufficient to compare the modality of histograms in order to infer that the D-Wave device performs quantum annealing. Indeed, the claim made to this effect in is based on additional evidence, in particular a strong positive correlation between the success probabilities of instances for the D-Wave device and a simulated quantum annealer, a test which the semi-classical
spin models presented here and in fail.

The question of why SQA and semi-classical spin models correlate so differently with the D-Wave device is obviously important and interesting. We note that while SQA captures decoherence in the instantaneous energy eigenbasis of the system, so that each energy eigenstate| in particular the ground state|is itself a coherent superposition of computational basis states, semi-classical spin models assume that each qubit decoheres locally, thus removing all coherence from the ground state. We conjecture that the fact that the D-Wave machine succeeds with high probability on certain instances which the semi-classical models finds hard, can be understood in terms of this difference.