Scott has talked to the USC authors [when they visited MIT] of a paper which found quantum annealing in 100 qubits but did not find a speedup over classical systems for the 128 qubit processor.
There were eight authors and Scott went with the most pessimistic of two of the authors that he spoke with. Matthias Troyer had doubts about DWave. Danny Lidar believed quantum speedups were possible.
Aaronson’s doubts and Matthias Troyer doubts via Aaronson
* The almost flat solutions times from smaller to larger problems is due to smaller problems not being run as fast as they could be. Run the D-Wave machine as fast as it can run for small n (small qubit numbers), and the difference in the slopes disappears, with only the constant-factor advantage for simulated annealing remaining. In short, there seems to be no evidence, at present, that the D-Wave machine is going to overtake simulated annealing for any instance size.
* calibration errors seem entirely sufficient to explain the variation in performance, with no need to posit any special class of instances (however small) on which the D-Wave machine dramatically outperforms QMC.
* the USC experiment was only one experiment with one set of instances.
NBF – Aaronson thinks the Amherst / Simon Fraser paper (showing 3000 to 10,000 times speedup in some cases) is wrong. He thinks that CPlex can and should be tuned for a “fair comparison”. Aaronson did not look at the Google tests which showed up to a 50,000 times speedup.
So does Google not have people smart enough to do a proper speed test comparison of the Dwave quantum computer versus classical computers. Google has had researchers using the Dwave systems for about 4 years and they have some pretty good people at tuning classical algorithms.
Dwave CTO Rose Responds
Troyer hasn’t even had access yet to the [512 qubit] system Cathy benchmarked (the Vesuvius – based system). Yes Rainier could be beat by dedicated solvers — it was really slow! Vesuvius can’t (at least for certain types of problems). Another is he thinks we only benchmarked against cplex (not true) and he thinks cplex is just an exact solver (not true). These types of gross misunderstanding permeate the whole thing.
Aaronson on Danny Lidar – another co-author of the USC paper
Danny Lidar is another coauthor on the USC paper, and also recently visited MIT to speak. Lidar and Troyer seem to agree on the basic facts—yet Lidar noticeably differed from Troyer, in trying to give each fact the most “pro-D-Wave spin” it could possibly support. Lidar chose to speak at our quantum group meeting, not about the D-Wave vs. simulated annealing performance comparison (which he doesn’t dispute), but about a proposal of his for incorporating quantum error-correction into the D-Wave device. He presented this proposal, not a reductio ad absurdum of D-Wave’s entire philosophy, but rather as a wonderful, positive opportunity to get a quantum speedup using D-Wave’s approach.
512 Qubit systems available for outside research
So 20% of both of the 512 qubit systems (Lockheed-USC and the Google-NASA-Space University) are available for outside researchers. There had been some availability of cloud based access to some Dwave systems. There is definitely system access possible for Troyer at USC and Aaronson to get on 512 qubit systems and run more definitive speed tests.
Aaronson can also develop more tuned and higher performing optimizers for classical systems. There seems like there would be a market for them.