Update: 2/5/07 After some conversations, I’ve realized that there is, I think, a big algorithmic wrench in the endeavor described below. Due to this I’ve added some text to this post in italics to describe what I think this wrench is and why my skeptic meter is getting higher and higher.
I’ve been meaning to blog about this for a while, but haven’t gotten my lazy fingers to do any of the typing: D-wave has announced that they are going to be demoing their 16 qubit machine, called “Orion”, on Feb 13 and Feb 15. Cool pictures here, here, and a pretty dilution fridge here. D-Wave’s homepage has a pretty picture of the two locations their demonstrating at (well they are remotely demonstrating, I guess kind of hard to hall your lab down to California!)
Okay enough pictures! Onto the details. Sixteen qubits! ???
First the details. The system they set up claims to be an adiabatic quantum computer with sixteen qubits. It has a Hamiltonian which is made up of ising interactions plus a single qubit term which is along the direction of the ising interaction and a transverse field. The idea, of course, is to use this for adiabatic quantum algorithms. Finding the ground state of a two dimensional ising model with a magnetic field (where each of the field values of the ising terms of magnetic field terms is a problem instance) is NP-complete. So the idea, I guess is to start with all transverse magnetic field, and start in the ground state of this system, and then drag the system to the new groundstate of the Ising model on your sixteen qubits. Sounds fun. Now one thing to think about is 2 to the 16 is about 65 thousand. So a brute force search of the ground state will most certainly be feasible and beat out the D-wave computer. But who cares, right? I mean the proof of principle is more important! Indeed. And there are many things to think about from what we know about the system….some postivie and some negative.
Okay, since I’m generally a postivie guy, I’ll start out with the negatives. First of all, I understand, and certainly the D-wave people understand, that we do not think that quantum comptuers can solve NP-complete problems in polynomial time. We do believe however, that they can achieve polynomial speedups over the classical algorithm for brute force searching. So great, the question is whether this quadratic Grover type speedup is useful in practice. (Update: 2/5/07 Okay, so there appears to be a big problem with this, as far as I understand it. So if you have a Grover type search where there is one marked item, and you run a linear extrapolating adiabatic algoithm, you get no speedup. But if you slow down at just the right time, then you can get a quadratic speedup. Basically the idea is to slow down where the algorithm has it’s smallest gap. But now there is a problem: how do you know when to perform such a slowing down (a priori)? Further, how do you know what extrapolation to try? Finally, NP-complete does not mean only on solution, so what do you do with multiple solutions? As far as I know, for a system like the Ising model in a magnetic field in 2D, we have no idea how to realize the quadratic speedup because we cannot tell when to slow down! So color me extremely skeptical about using this sort of setup for quadratic speedups.) Now there are lots of interesting questions here. For example, you need to compare the quadratic speedup to the best known SAT solvers. Does Groverish search really help? (I could be wrong here, but my impression was that it is not known how to beat the best SAT solvers??? Help, experts correct me!) But the real problem I have is just one of PR. All this mention of NP-complete for their adiabatic quantum computer makes it sound distinctly like they are claiming that they can efficiently solve NP-complete problems. Don’t believe me? Well read the comments on the blog post linked above and you’ll see what I mean. Now, I know this is nitpicky, but I think when you’re dealing in a field which is highly highly highly susceptible to hype hype hype, you need to be extra careful. (Update 2/5/07: Indeed, given that we do not know how to even achieve this quadratic speedup for the type of setting this system, I don’t see why they can claim much relationship to quantum computing speedups at all?
Okay, so that’s kind of a low blow, just disagreeing with PR. I’m happy to admit it’s not something that is that important. The real question of course is: will this thing work? Is it a quantum computer? What fidelities do they achieve. Wowa..one thing at a time. (1) It will work. If it didn’t they’d be silly to demo it. And they are deadly serious (well deadly if you are an NP-complete problem )
Okay (2) Is it a quantum computer? First comment: adiabatic quantum computation (error free) is equivalent to the quantum circuit model (error free). So adiabatic quantum computers (error free) are quantum computers (error free) in the most traditional sense. If I were going to sell Orion to my investors, I’d sell this point over and over and over again. Of course, for those of you who read the parenthesis, you’ll know what I’m going to say next. We don’t know how to turn a system like the one they claim, with adaibatic controls only into a fault-tolerant machine. We have a few ideas (notably the work of Jordan et al which is very similar to the work of Kitaev and others have done…also early work by Childs et al.), but I don’t think we know how to build a fault-tolerant all-adiabatic quantum computer…yet! So should this matter? Well let me quote from a paper intro I’m writing right now
It is tempting to consider all physical systems as being information processing devices which manipulate through their dynamics the information labelled by the system’s different states. This view of computation, however, is severely naive because it leaves out consideration of whether it is practically possible to robustly store and fault-tolerantly manipulate the information encoded into the physical system in the presence of noise and imprecise control.
To me you do not have a computer until you have a fault-tolerant computer. So to the question of whether they have a quantum computer we can say: adiabatic quantum computers are quantum computers if we can figure out how to make them fault-tolerant.
Okay what about (3) the fidelities. This is where the real questions come in. At what temperature are they running their adiabatic quantum computer and how do these temperatures compare to the coupling strengths they have. More importantly, however, how do these temperatures compare to the gap in the adiabatic quantum algorithm (this will be smaller than the coupling terms!) This latter problem is one of the big problems for error correction in adiabatic quantum systems. Since the gaps for adiabatic quantum algorithms scale inversely as a polynomial in the problem size, you need to have your temperature scale in a similar way. Now of course, this isn’t totally true, becuase it is possible for a temperature bigger than the gap to be USEFUL in the adiabatic quantum algorithm (a sort of hybrid adiabatic-anealing computer.) However our understanding of this type of algorithm is far from complete and understanding how it, say, affects the quantum circuit simulations of quantum computers on an adiabatic machine is not, as far as I know, known.
Another thing to worry about in fidelities are the couplings themselves. How well are they controlled? If I want a certain energy coupling in my adiabatic quantum algorithm, how certain are you that this coupling is the correct one (say Ising ZZ) or is the correct strength. If that control isn’t strong enough you can cause a phase transition from the ground state you want to one you don’t want. Very bad.
Finally you might worry about the fidelities of two other components, the preparation and the readout.
Of course all these questions about fidelity are ones which hopefully dwave will settle by either publishing about their system, or convincing us all that they are doing legit things by building quantum computers that behave as expected (and eventually solve a SAT problem the NSA can’t solve…assuming the NSA doesn’t have a quantum computer already, of course! See there I go, mentioning SAT instances in the same sentences as quantum computation when I really should have mentioned factoring!)
Finally let me just say that I think the fact that D-wave is putting themselves out there and trying to push things is great. I worry about if they fail what this does for future quantum computing endeavors, but I love underdogs, so I have great sympathy for trying. (Update 2/5/07: But what should we make of the fact that it seems to me the algorithmic case for their method seems, at best, to be in grave doubt? For me, this is dubious territory to tread. While I won’t cry doom, I will cry that the case is very shakey.) I also love the fact that they are going for breadth versus depth. I want more qubits damnit, and if a crazy Canadian company is going to be the one to help me get those qubits, then I’m as happy as can be! (Update 2/5/07: I still like the fact that they are going with a lot of very very noisy qubits. In my mind this makes the endeavor like NMR+. Whether this plus is big enough to fashion a real quantum computer is the billion dollar question.)