Two posts over at Quantum Algorithms, one on D-Wave Systems and another one on a supposed algorithm for solving NP-complete problems efficiently on a quantum computer.
When I was a graduate student at Berkeley, when a paper came out claiming that quantum computers could solve NP-complete problems, we would all race to see who could figure out where the problem in the paper was. I usually don’t like to write blog articles about papers like the one commented upon in Quantum Algorithms (for the preprint, see here), but I’m not about to get a blogger username to just comment on the site cus I’m lazy, so I thought I’d just stick my comments here. As far as I can tell the paper is incorrect. In particular if you examine Figure 3, the circuit described does not perform as described. If I understand correctly, the state after the oracle gate is [tex]${1 over 2^n} sum_{x,y=0}^{2^n-1}(-1)^{f(x)}|y>|x>$[/tex]. The author then applies a unitary gate between the y and x registers and then a measurement of the qubits. This is supposed to allow one to identify a place where [tex]$f(x)=1$[/tex], but as far as I can tell, one only gets an exponentially small information about such a location if there is only one marked item.
The other article on Quantum Algorithms points to an article in the MIT Technology Review about the Vancouver based D-Wave systems. Here the hyperbole is even more mysterious:
Vancouver startup D-Wave Systems, however, aims to build a quantum computer within three years. It won’t be a fully functional quantum computer of the sort long envisioned; but D-Wave is on track to produce a special-purpose, “noisy” piece of quantum hardware that could solve many of the physical-simulation problems that stump today’s computers, says David Meyer, a mathematician working on quantum algorithms at the University of California, San Diego.
The difference between D-Wave’s system and other quantum computer designs is the particular properties of quantum mechanics that they exploit. Other systems rely on a property called entanglement, which says that any two particles that have interacted in the past, even if now spatially separated, may still influence each other’s states. But that interdependence is easily disrupted by the particles’ interactions with their environment. In contrast, D-Wave’s design takes advantage of the far more robust property of quantum physics known as quantum tunneling, which allows particles to “magically” hop from one location to another.
It sounds to me, from the article, that the proposal is a quantum computer which implements a quantum adiabatic algorithm. The question of whether adiabatic quantum algorithms can be more efficient than classical algorithm is, from what I know, fairly controversial (see, for example, here.) I would have a hard time telling a venture capitalist to put money in something quite so controversial, but hey, what do I know, I’m just a lowsy academic nerd and a chicken. If they can sell solutions to hard problem instances and actually succeed, then what do I know! And they will be rich!
Update: Suresh says I’m lazy. And I am. So looking again at quant-ph/0506137, the main problem is already apparent in equation (5). There the author has miscontrued the tensor product. If we take the output of this circuit seriously, the initial state [tex]$|00rangle$[/tex] is transformed into [tex]$0$[/tex]. Not the state zero. The amplitude for the first qubit in this formula is zero.
My apologies. I didn’t mean that you were lazy, but that your comment was (literally) the equivalent of swatting at a slow moving fly 🙂
Hope I didn’t offend.
That’s a good idea. There are various such things for the P vs NP proofs.
Aram — I interpreted the stuff about speedup of NP-complete problems as being a use of Grover’s algorithm. Interpreted this way that comment is merely incomplete and probably somewhat misleading, but not total rubbish.
So what is the noise about adiabatic algorithms being more robust against “control errors”?
I thought only toplogical effects are robust to control imperfections (path deviations) and adiabatic methods are not really topological…
By the way, I have heard that D Wave’s CEO (or ?) is a very smart guy who is very good (and famous) in making money using science. You can interpret this sentence as you wish but the marxist in me is already shouting “foul!”
No, no. No offense at all. I was lazy. Perhaps its just that I’ve seen so many of these papers over the years. Maybe I should write a checklist of what you should go through before you announce that NP is in BQP 😉
you know that adiabatic QC is equivalent to standard QC, right? (that’s in fact the title of the linked article.)
this technology review article is terrible. please permit me to briefly rant.
1. adiabatic QCs almost certainly still evolve through highly entangled states – if they didn’t, then we would have P=BQP, thanks to the above article and simulation methods like guifre’s.
2. adiabatic QCs still need to worry about decoherence. they probably have a FT threshold, but it’s bullshit to say that they are “far more robust.” FTQC on adiabatic QCs is an interesting problem – i think that the only error rate that can be provably tolerated is currently 1/poly(n), but i bet it could be improved to a constant.
3. this excerpt speaks for itself.
D-Wave’s first computer won’t be able to accomplish the most widely touted payoff of quantum computing: factoring… It will, however, be ideally suited to solving problems like the infamous traveling-salesman problem,… In searching for its own optimal energy state, D-Wave’s chip performs exactly this type of calculation automatically, in seconds.
i wonder what the error bars on their “solutions” will look like…
It seems to me that Eqs (5) and (15) (it has a similar problem) are not crucial to any of the proposed algorithms. But they are indicative of a general misinterpretation of tensor products. For example, the operation of the oracle in the circuit in Fig. 1 is inconsistent with Eq. (20), which really requires a type of controlled Q_f. This inconsistency occurs again between Fig. 3 and the first line of Eq. (28) (also the right hand side is not even normalized). If the oracle in Fig. 3 is just I tensor Q_f, then one can consider the reduced density operator for a pair of qubits connected by one of the C gates. It does depend on associated bit of the marked item’s location but these terms scale as 1/2^n. It’s not really clear what any of the oracle unitaries are in these algorithms.
Sad and ominous FOR BOTH the Academics and D-Wave Systems that there such animosity, mistrust, and lack of communication between them.
Aram: sure I know adiabatic is equivalent to standard quantum computation. The point is that I just don’t believe that they are using that construction on their superconducting system. It sounds to me like either the standard adiabatic approach to solving hard problems or the Grover speedup as Michael suggests.
ok, so maybe not technically false, just highly misleading marketing-speak. likewise “in seconds” doesn’t say how many seconds, or with what fidelity…
and it’s true that not all 2-local hamiltonians are equally powerful. inductively coupled superconducting loops have fixed ZZ interactions and then a global X field can be turned on, right? i guess i was wrong about this being enough for universal computation, but it sure seems close.
I have no animosity toward D-Wave systems. I am glad that they are pushing forward and I believe they are very brave. Mistrust is not quite the correct word either. As a community, I feel uncomfortable when quantum computers are portrayed in ways that “stretch” the truth. As Michael and Aram’s comments point out, exactly how far they are stretching is a matter of interpretation. So it’s not that I mistrust them, it’s that I have the same feeling when I see something about all the universes simultaneously computing the answer on a quantum computer. Well not quite that bad, but a similar feeling.
The lack of communication is, indeed, a bit sad, but I’m not sure how true it is. Certainly I know little about D-Wave, but others in quantum information science may no more. In particular those who work in superconducting implementations surely know more than I do. But certainly D-wave has no obligation to let everyone in the world know what they are doing: they are a business in the early stages of development, and perhaps sharing with academia is not something they wish to do. Certainly many companies which are developing new technologies cut their ties to academia precisely because they believe they have a technology which will work and they don’t need any of the academics telling them what to do.
i didn’t mean to entirely blame d-wave for the article – most of the responsibility is the reporter’s, and yes, of course companies are going to hype their products without giving technical details.
i wonder if they’re using something along the lines of quant-ph/0403090?
anyway, i think i just have high expectations for technology review, because of the MIT connection, so am constantly being disappointed whenever they do an article about something i know about.
One thing that you should “go through” before announcing that NP is in BQP is a non-relativizing proof, because a random oracle places NP outside of BQP. Indeed that result is based on the theorem that Grover’s algorithm is optimal. Apprently de Vries didn’t know or didn’t care that he contradicted an accepted theorem.
Version 2 of the quant-ph/0506137 preprint has been posted, and the claims are substantially scaled back :-). Looks like peer review works.
Version 2 also appears to have problems. The claim that a faster search algorithm than Grover’s is presented for four elements would seem to be incorrect. The author claims that since Grover’s algorithm is O(sqrt(N)), then it requires 2 time steps for N=4. He then presents a method for doing it in one time step. Grover’s algorithm only takes one iteration for N=4, so it seems there is no improvement in his algorithm.