The Quantum Pontiff

Rumors

Higgs rumor spreads to Slate.com. Me, I want to start a rumor that a Manhattan project for quantum computing has already built a large scale quantum computer (now wouldn’t that make a certain company which has built a small special purpose analog classical computer mad.)

Annealing to Zen-Budha Ground State

Okay, so talking about D-wave is certainly not good for my Zen-Budha nature. Not good at all! So let’s talk about something related to D-wave but only tangentially so that I can get that Zen-Budha nature back.

One issue that comes up a lot in discussion about D-wave is simulated annealing. Wikipedia does a nice job defining simulating annealing. The basic idea is to mimic cooling in a physical system. Suppose you have a space of different configurations and some sort of energy function on this space. You’re goal is to find the lowest energy configuration because then you will be the coolest physicist on the block…and of course at the same time you might be solving some very hard computational problem. At a given step in the simulated annealing algorithm, you are in a given configuration and then you take a step in a neighborhood of this configuration. The probability of your particular change depends on a parameter T which is roughly the temperature. The simplest update rule is something like Metropolis Monte Carlo: if the energy is decreased, then always accept the change but if the energy is increased, accept this change with a probability . Of course more complex update rules are possible, but you get the idea. Then as a function of time you decrease the temperature and roughly freeze out the system. Hopefully when the temperature has reached zero you will either be at the global minimum energy or will have seen the global optimal energy. Okay, so a cool strategy for finding a global optimum. (Okay, okay, that will be my last temperature joke!)

But if there is one thing you learn when you begin to learn about classical algorithms it is that oftentimes what is good for solving one problem can be bad for solving other problems. Take, for example the maximum matching problem. A matching of a graph is a set of edges which do not share common vertices. The maximum matching problem is to find a matching with the largest number of edges. There is a classical algorithm for finding the maximum matching which runs in a time proportional to the number of edges times the square root of the number of vertices (due to Micali and V. Vazirani). In other words the running time of this algorithm is polynomial.

Now what happens if we run simulated annealing on this problem? Well of course simulated annealing is a meta-algorithm…there is a lot I haven’t specified. But just take a fairly generic and straightforward way of implementing simulated annealing for this problem. Then it was shown by Sasaki and Hajek that there exist bad instances for this approach. In other words simulated annealing fails to find the maximum matching in a time polynomial in the size of the graph. Doh! On the other hand, simulated annealing does find a “close” maximum matching for suitably small temperatures. This later fact is interesting, but what is more interesting to me is the fact that the simulated annealing algorithm fails where a classical polynomial time algorithm is known to exist.

So why does this all matter in the big scheme of things? Because one of the claims made by those who believe in D-wave is that their quantum system will outperform classical simulated annealing. But what does it mean to outperform classical simulated annealing if classical simulated annealing itself isn’t even the best classical algorithm? There is no simple answer to this question as far as I know, but it does give me pause everytime I see simulated annealing compared to some quantum version of this annealing.

PCP Slinging Journalists

So many times scientists are very harsh on science journalists. Thus it is refreshing to see this article in the MIT Technology Review by Jason Pontin on D-Wave’s recent Orion quantum computer. The article includes an interview with D-Wave’s Geordie Rose by Pontin which is rather refreshing mostly for the fact that Pontin pulls out the PCP theorem on Geordie (Gunslinging computer scientists come equiped with the PCP theorem strapped to their belts. Only recently were the schematics for how to build this gun made accessible to mere mortals like us physicists.) The article seems rather fair to me, airing both Geordie’s views as well as asking the hard questions, includes criticisms from Scott and Umesh Vazirani, as well as a more moderate view from Seth Llloyd. Whether you are satisfied with the answers Geordie gives, of course, is a different matter! For example, me I don’t think that the current setup they have scales if they continue with the same setup they have here (energy gap goes like one over problem size, I might buy that thermalizing helps a bit, but am extremely skeptical when the energy from the environment will swamp the energy spectrum), but this is different from believing that it’s not possible to modify the path they are taking to actually scale their system.

Update: Here is the New York Times version of the article, where, sadly the PCP theorem has been removed. Sad, I mean all the latte-sipping Volvo-driving lefties I know can speak elegantly in an instancet about the PCP theorem and approximation algorithms.

Skepticism….Check. Axes….Ummm…

Bah (posted without long line of four letter words I would really like to print but am forced, by my good nature and good upbringing, to avoid printing on this family friendly blog.):

“Businesses aren’t too fascinated about the details of quantum mechanics, but academics have their own axes to grind. I can assure you that our VCs look at us a lot closer than the government looks at the academics who win research grants,” Martin said.

Note to D-wave. We aren’t skeptical that you built a device. We are skeptical that your path forward will ever work (some more skpetical than others…me I’m an optimist!) and we are even more skeptical of your statements trying to sell quantum devices by advertising unsubstantiated computational power. I also know VCs who looked closely at your company and said something very similar to what those lazy no good bum academics are saying.

They Built….a Brain!

The mystery of what exactly was built up north has been resolved. They built a brain:

Within Holistic Quantum Relativity lies the realm of the human mind and the observable universe running like Quantum Computers: this technological synthesis offers the possibility of solving what computer science calls “NP-complete” problems. Last week D-Wave Systems, a privately-held Canadian firm Headquartered near Vancouver, BC, demonstrated what it calls the world’s first commercially viable Quantum Computer at the Computer History Museum in Mountain View, California. These are problems which are impossible or nearly impossible to calculate on a classical digital computer. Picking out a single pattern from a collection of patterns, such as one’s mother, father, or child, from a photo of people, is easy for the human mind, but beyond the reach of a conventional desk-top computer!

Factoring Bacteria

No sooner do I attack biologists as the common mortal enemy of computer scientists and physicists in my last post when along comes quant-ph/0702203. Yet another nomination, in that great cosmic contest: “best paper title ever!” (said with the comic book guy accent, of course.) quant-ph/0702203:

Purple bacteria and quantum Fourier transform
Author: Samir Lipovaca

Abstract: The LH-II of purple bacteria Rhodospirillum (Rs.) molischianum and Rhodopseudomonas (Rps.) acidophila adopts a highly symmetrical ring shape, with a radius of about 7 nm. In the case of Rps. acidophila the ring has a ninefold symmetry axis, and in LH-II from Rs. molischianum the ring has an eightfold symmetry axis. These rings are found to exibit two bands of excitons. A simplified mathematical description of the exciton states is given in Hu, X. & Schulten, K. (1997) Physics Today 50, 28-34. Using this description, we will show, by suitable labeling of the lowest energy (Qy) excited states of individual BChls, that the resulting exciton states are the quantum Fourier transform of the BChls excited states. For Rs. molischianum ring exciton states will be modeled as the four qubit quantum Fourier transform and the explicit circuit will be derived. Exciton states for Rps. acidophila ring cannot be modeled with an integer number of qubits. Both quantum Fourier transforms are instances of the hidden subgroup problem and this opens up a possibility that both purple bacteria implement an efficient quantum circuit for light harvesting.

Boy are we going to have mud on our face when we discover that Bacteria have beaten even D-wave towards the construction of a useful quantum computer

D-wave Scattering

Da Optimizer makes it into Nature (news@nature.com) with comments on D-wave. See, Nature publishes CS researchers! Scott expresses the concern most researchers in quantum computing have with the hype:

“If it fizzles out,” he says, “people might say that quantum computing as a whole is just bunk.”

[For a picture of real D-wave scattering, see here.]

All D-wave, All the Time…P and S-wave’s Getting Jealous

Hoisted from DaOptimizer’s comments, YouTube videos of d-wave’s announcement. Also, Lieven Vandersypen (who factored 15, which sounds simple, but if you think the factoring experiment done on IBM’s NMR machine was simple, then you haven’t seen their pulse sequence!) weighs in on D-wave here.

D-wave In D-news

Lots of blogging and press picking up on D-wave and Orion so I thought I’d collect a few here. The offical press release is here. I’d love to hear from anyone who has attended.

Scott Aaronson called me a Chinese restraraunt placemat in his The Orion Quantum Computer Anti-Hype FAQ (Update (3:17pm 2/13/07): Scott’s post now contains an update by the great Lawrence Ip, who now works for Google.) Doug Natelson, who gave an excellent talk here at UW a few weeks ago, poses three questions about the D-wave demo. Peter Rhode is every bit the skeptic and beats out Doug Natelson with four points. Ars-technica’s Chris Lee takes a shot at explaining adiabatic quantum computation and uses the word deathmatch here. You can find a bad quantum computing joke at the end of this blog post. I find
this post amusing, if for nothing more than bringing politics into quantum computing. Coherence* remains the prettiest quantum computing website and has a choice Seth Lloyd comment “I’ll be a bit of a skeptic until I see what they have done. I’m happy these guys are doing it. But the proof of the pudding is in the eating.”

More mainstreamish media produces some truely incredible hype. One of my favorites is at physorg.com where we find the title a “New supercomputer to be unveiled” along with the choice gibberish “A Canadian firm is claiming to have taken a quantum leap in technology by producing a computer that can perform 64,000 calculations at once.” I flipped a coin 16 times today, can I get some venture capital? Personally I like Gizmodo’s title: “D-Wave Quantum Computer to Span Multiple Universes Next Tuesday?” They also use the word sugerdaddy. If you want more reasons to be angry about hype or at bad journalism, go over to a wired gadget blog where you’ll find

There are certain classes of problems that can’t be solved with digital computers,” said Herb Martin, the firm’s CEO, over a decidedly-noisy digital cell phone. “Digital computers are good at running programs; quantum computers are good at handling massive sets of variables.”

Turing is certainly turning in his grave over that first sentence and, since Peter Shor is alive and well, I wonder if he is spinning today?

And don’t even get me started on this EETimes article. Choice:

Nondeterministic polynomial (NP) problems are the most difficult to solve on conventional computers because each variable adds yet another dimension to its possible solutions.

No, no, no! So many no’s I can’t even write it down. First of all NP problems include problems in P, so they definitely aren’t the most difficult to solve on a conventional computer. Second, the essentence of NP-complete problems is NOT just that you have an exponential search space. You’d think a Electrical Engineering rag would have taken some computer science courses? Then, of course EETimes only digs their grave deeper:

Quantum computers, on the other hand, can evaluate all possible solutions simultaneously and find the optimal solution, often in just a few clock cycles, thereby not only vastly speeding up the time taken to find the solution but also finding the most optimal result.

Okay, at that point I’ll admit I had to stop reading cus my brain was about to explode.

Oh, and whatever you do, don’t search for “first quantum computer” if you’ve ever performed a quantum computing experiment (that includes a lot of MIT Physics majors? Ack, is NMR quantum computation really quantum computation?) You might get a little miffed at all the years you spent in grad school doing what you thought were small quantum computer experiments.

Orion Into The Future

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

rose.blog

A new quantum computing blog! Geordie Rose, Founder and Chief Technology Officer of D-Wave (the British Columbia company questing to build a quantum computer) now has a blog called rose.blog. Geordie certainly named the blog after his last name, but when I read that title, I hear “Rosebud” and want to go sledding.

$-Wave

Okay, we will officially call this week “D-wave week.” According to an article here (update: for a link that may work for all browsers, see here), D-wave just secured another round of financing, to the tune of $14,000,000.

D-Wave News

D-Wave Systems, those crazy Vancouverites trying to build a quantum computer, have a new CEO:

VANCOUVER, BRITISH COLUMBIA, May 9 /CNW/ - D-Wave, developer of the world’s most advanced computers, has appointed Silicon Valley technology executive and entrepreneur Herbert J. Martin as chief executive officer.

Which makes me dream of the day when I will be able to include in my grant proposal a request for dollars to buy a quantum computer.

Hyperbole Wednesdays

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 . 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 , 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 is transformed into . Not the state zero. The amplitude for the first qubit in this formula is zero.