The Quantum Pontiff

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.)

A highly readable book I picked up a few years ago is Principles of Quantum Electronics by Dietrich Marcuse. One of the fun parts about this book is that it beigins discussion of quantizing electronmagnetism by starting with the quantization of simple LC circuits. Of course, Marcuse, writes

It is true that the quantum theory of the LC circuit must be regarded as more correct than the classical theory, but the difference between the results of classical and quantum theory are unobservable by experiments with LC circuits.

This was written in 1970. What is interesting, of course, in our modern day of cool quantum experiments, is whether this is true today. In many ways, it does remain true, but there is a notable exception and that is in superconducing circuits. Very interesting, and readable works on this (with a focus on decoherence) are cond-mat/0308025 and cond-math/0408588 (works by Guido Burkard, Roger Koch, and David DiVincenzo.) So if a quantized theory of quantum circuits can be used to describe some superconducting quantum systems can we also do things like couple these to electromagnetic fields which are themselves quantized?
Well the answer is yes! And a group at Yale has been doing some excellent experiments in this direction. Here is a Nature paper just published about coupling superconducting circuits to microwaves transmission lines (Nature 445, 515-518, “Resolving photon number states in a superconducting circuit”, D. I. Schuster, A. A. Houck, J. A. Schreier, A. Wallraff, J. M. Gambetta, A. Blais, L. Frunzio, J. Majer, B. Johnson, M. H. Devoret, S. M. Girvin and R. J. Schoelkopf) Previos work had shown how to get this coupling into the “strong coupling regime” where a single photon can be absorbed and emitted multiple times, whereas in this work they show how to get into a “strongly disapative regime” where the a single photon can have a large effect on the superconducting circuit without ever being absorbed. This allows the authors to perform experiments where they measure the photon number of the microwave field. Pretty cool! They call experiments like this circuit quantum electrodynamics. A new field is born.
So what consequences are there for quantum computerists? Well certainly this gives a possible method for a bus in some of the superconducting quantum systems. It should also allow for the preparation on nonclassical states of the microwave field, something which might have potential impact on quantum communication like protocols for quantum computing. But this is all in the future. Right now it’s just cool to sit back and read about the experiment!

When I was an undergraduate at Caltech visiting Harvard for the summer I stumbled upon Volume 21 of the International Journal of Theoretical Physics (1982). What was special about this volume of this journal was that it was dedicated to papers on the subject of physics and computation (I believe it was associated with the PhysComp conference?) Now for as long as I can remember I have been interested in physics and computers. Indeed one of the first programs I ever wrote was a gravitational simulator on my TRS-80 Color Computer (my first attempt failed because I didn’t know trig and ended up doing a small angle approximation for resolving vectors…strange orbits those.) Anyway, back to Volume 21. It contained a huge number of papers that I found totally and amazingly interesting. Among my favorites was the plenary talk by Feynman in which he discusses “Simulating Physics with Computers.” This paper is a classic where Feynman discusses the question of whether quantum systems can be probabilistically simulated by a classcal computer. The talk includes a discussion of Bell’s theorem without a single reference to John Bell, Feynman chastizing a questioner for misusing the word “quantizing”, and finally Feynman stating one of my favorite Feynman quotes

The program that Fredkin is always pushing, about trying to find a computer simulation of physics, seem to me an excellent program to follow out. He and I have had wonderful, intense, and interminable arguments, and my argument is always that the real use of it would be with quantum mechanics, and therefore full attention and acceptance of the quantum mechanical phenomena-the challenge of explaining quantum mechanical phenomena-has to be put into the argument, and therefore these phenomena have to be understood ver well in analyzing the situation. And I’m not happy with all the analyses that go with just the classical theory, because nature isn’t classical dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical, and by golly it’s a wonderful problem, becuase it doesn’t look so easy.

(That, by the way, is how he ends the paper. Talk about a way to finish!)
Another paper I found fascinating in the volume was a paper by Marvin Minsky in which he points out how cellular automata can give rise to relativistic and quantum like effects. In retrospect I dont see as much amazing about this paper, but it was refreshing to see things we regard as purely physics emerging from simple computational models.
But the final paper, and which to this day I will go back and read, was “The Computer and the Universe” by John Wheeler. Of course this being a Wheeler paper, the paper was something of a poetic romp…but remember I was a literature major so I just ate that style up! But the most important thing I found in that paper was a description by Wheeler of the doctoral thesis of Wootters. Wootters result, is I think, one of the most interesting result in the foundations of quantum theory that you’ve never heard of (unless you’ve read one of the versions of the computation and physics treatise that Wheeler has published.) Further it is one of those results which is hard to find in the literature.
So what is this result that I speak of? What Wootters considers is the following setup. Suppose a transmitter has a machine with a dial which can point in any direction in a plane. I.e. the transmitter has a dial which is an angle between zero and three hundred and sixty degrees. Now this transmitter flips a switch and off goes something…we don’t know what…but at the other end of the line, a receiver sits with another device. This device does one simple thing: it receives that something from the transmitter and then either does or does not turn on a red light. In other words this other device is a measurment aparatus which has two measurment outcomes. Now of course those of you who know quantum theory will recognize the experiment I just described, but you be quiet, I don’t want to hear from you…I want to think, more generally, about this experimental setup.
So we have transmitter with an angle and a reciever with a yes/no measurement. Now yes/no measurements are interesting. Suppose that you do one hundred yes/no measurements and find that yes occurs thirty times. You will conclude that the probability of the yes outcome is then roughly thirty percent. But probabilities are finicky and with one hundred yes/no measurements you can’t be certain that the probability is thirty percent. It could very well be twenty five percent or thirty two percent. Now take this observation and apply it to the setup we have above. Suppose that the transmitter really really wants to tell you the angle he has his device set up at. But the receiver is only getting yes/no measurements. What probability of yes/no measurements should this setup have, such that the the receiver gains the most information about the angle being sent? Or expressed another way, suppose that a large, but finite, number of different angles are being set on the transmitter. If for each of these angles we get to choose a probability distribution, then this probability distribution will have some ability to distinguish from other probability distributions. Suppose that we want to maximizes the number of distinguishable settings for the transmitter. What probability distribution should occur (i.e. what probability of yes should there be as a function of the angle)?
And the answer? The answer is [tex]$p_{yes}(theta)=cos^2left({n theta over 2} right)$[/tex] where [tex]$n$[/tex] is an integer and [tex]$theta[/tex] is the angle. Look familiar? Yep thats the quantum mechanical expression for a setup where you send a spin $n/2$ particle with its amplitude in a plane, and then you measure along one of the directions in that plane. In other words quantum theory, in this formulation, is set up so that the yes/no distribution maximizes the amount of information we learn about the angle [tex]$theta$[/tex]! Amazing!
You can find all of this in Wootters’s 1980 thesis. A copy of which I first laid my hands on because Patrick Hayden had a copy, and which I subsequently lost, but now have on loan for the next two weeks! Now, of course, there are caviots about all of this and you should read Wootters’s thesis, which I do highly recommend. But what an interesting result. Why haven’t we all heard of it?