I wanted to write on tensors etc., but a few very fresh inputs concerning the D-Wave device have appeared, all barely within the past 24 hours or less.
First, it was Prof. David Poulin commenting at Prof. Scott Aaronson’s blog once again [^], alerting some new work from Prof. Troyer. Unlike in his last comment (on the same post, when he thought that it was not a QC), Poulin has now come closer towards (or has started) supporting the position that the D-Wave device is a QC:
“…the problem instances that are easy for the D-wave device can sometimes be hard for the SS model. This is interesting new evidence supporting the quantum nature of the D-wave device.”
Next, a very valuable comment by one Bill Kaminsky appeared on Aaronson’s blog, very neatly explaining the Smolin and Smith model [^], and then contrasting it with the new result by Troyer. [Guess this Bill Kaminsky is the same as one William Kaminsky, who, in turn, is a PhD student in QIS at MIT. (… Just a Google search, that’s all!)] … Incidentally, more explanatory material concerning the adiabatic quantum optimization, quantum annealing, and classical annealing, written by Kaminsky, had already been put up last week at Henning Dekant’s blog; see here [^].
Finally, while idly thinking about all these things, even as idly browsing Prof. Poulin’s home page, I just idly happened to hit the “New on quant-ph” link [^] at its bottom, and thereby landed at the arXiv site; and once there, I noticed a new paper by Troyer (and (eight!) pals): [^].
Essentially, what Troyer et al. now say is that the D-Wave device does something that the classical devices apparently don’t, and so, the D-Wave device must be quantum! … If not all the classical devices, then at least the two devices: one, considered by they themselves, and the other, considered by Smolin and Smith. The D-Wave device behaves unlike both.
Further, Troyer et al. offer the following conjecture to account for the difference between the D-Wave chip and the [semi-]classical models:
“…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.”
So, looks like, it is a quantum computer, after all. … At least, for this week!
* * *
Clearly, more studies required. So, here are a few questions to the QC research community:
What needs to be done to study the above conjecture more closely? Would some simple and special-purpose simulations that directly allow for a parametric control of the degrees of decoherence, help at least to illustrate (if not to fully support) the above conjecture? Such simulations could be highly simplified (say involving just a linear graph) but, still, sufficiently complete so as to be able to isolate, study, and possibly help settle, this issue.
How do you square off the quantum-ness of the D-Wave chip, and the “absence” of a speed-up, as discussed on Aaronson’s blog?
What measures would you suggest to capture the “percentage quantum-ness” of a QC? of an adiabatic quantum device such as D-Wave’s?
On these measures, how quantum are the current two D-Wave chips (D-Wave One and Two)? What is your estimate?
* * *
May be, more, later. (Who knows, it might once again collapse back to being a simple classical computer, next Monday!)
[May be I will come back (right today) and edit this post a bit, so as to make the write-up a bit more streamlined.]