Heresy

It’s a special rite of passage as an academic to see your field, your passion — that thing to which you devote the best of your twenties — steeped in controversy.  Some disciplines, of course, feel this particularly more harshly than others.

One would think that my field, quantum information, would suffer less from this problem considering its status as a niche, speculative technology that’s been in slow but steady development for the better part of three decades.

But one would be wrong.

As a brief aside, let us review some technical terms:

Quantum computers are often benchmarked by their number of “qubits,” which is a shortening of quantum bit.  If you happen to be reading an academic article on quantum computing or quantum information, there’s usually an additional word salad of qualifiers describing what exactly these qubits are, and how they are implemented.  For simplicity, I will say they are like a bit — that little 0-or-1 that your computer uses for, well, computing, and will defer to people that have put far more energy into explaining exactly what qubits are in more detail.

Much of the power of quantum computers comes from the process of entanglement — an impressively misunderstood, and unsurprisingly confusing concept that most people without a physics degree probably haven’t ever seen in an academic setting.  Again, I defer, but the important idea is that the process of controllably entangling qubits is very difficult, but that this process is integral to their operation — a quantum computer that doesn’t have entangled qubits is not a quantum computer — it is simply a computer with very expensive bits.

With a state-of-the-art quantum computer that has somewhere around seven qubits, you can factor the number 21 into 7 and 3 (not that this wasn’t an impressive technical achievement!).  And for the past couple of years, we haven’t been able to entangle much more than around seven qubits with each other (not for lack of trying!).

With a 512 qubit quantum computer, you could crack the RSA encryption algorithm with ease, trivializing essentially all encryption used on the modern internet (now that it appears the NSA has unfettered access to this information anyway and people don’t seem too bothered, I may need to pick a new favorite example for demonstrating what quantum computers can do).

Better example: We would no longer need to do experimental chemistry if we had a large enough quantum computer, because such a quantum computer could efficiently simulate any chemical reaction we would want to study to arbitrary fidelity.  512 qubits would probably be “large enough.”

The important idea here is that the power of quantum computers scale quickly in the number of qubits available for use (faster than an equivalent classical computer’s scaling in bits).  This works best with an example:

Suppose you want to count the number of little spikes on some hedgehogs.  You’re pretty impatient, and hedgehogs are generally terrified of you for reasons that should be clear shortly.

Catching them in your hands just isn’t feasible, but you’re a pretty good shot, so you go and fetch your tranquilizer gun and proceed to go hunting.  Despite the protestations and agility of your spined prey, you manage to shoot and count the spines on about 1 hedgehog every 5 minutes.  You decide this is too slow, so you call your friends over (who conveniently also own tranquilizer guns).  Thus, for each additional hunter, you can bag an additional hedgehog every 5 minutes.

Suzie wanders nearby and, with a sneer at your barbaric ways, pulls out her Quantum Blanket.  At first, it seems like she can only capture 1 hedgehog every 5 minutes in her blanket, but for each additional friend that comes to aid her, they can stretch the blanket’s area to twice its size before.  Thus, with one additional friend, they can catch 2 hedgehogs every 5 minutes, with two friends, 4 hedgehogs, with 3 friends, 8 hedgehogs, 4 friends, 16 hedgehogs, and so on.

So, Suzie’s Quantum blanket allows her to catch a number of hedgehogs exponential in the number of friends helping her, whereas you can only catch a number of hedgehogs linear in the number of friends helping you (also, tranquilizer guns are expensive).

Now, this article was about some controversy before we became distracted with hedgehogs, so enter the company D-Wave, which recently sold a “512 Qubit Quantum Computer” to a NASA/Google consortium for several million dollars (with a previous sale to a Lockheed/USC group for a similar number of millions of dollars).  This is a bit strange, because last I checked, the spectroscopists down the hall from me were still blowing apart chemicals with lasers, and don’t seem too bothered about their impending obviation.

After a little bit of digging, one discovers that not everything is as it seems, despite what appears like a concerted media effort to tout the D-Wave system as something that it isn’t.  And this time, I’m not even going to blame the science journalists.  I absolutely love it when Quantum Information gets attention in the news because it’s such a niche field, and because journalists often do a fantastic job explaining the intricacies of qubits and entanglement in the short span of an article.  This time, they were at best misinformed, and at worst lied to.

D-Wave does not sell a commercial quantum computer, they sell what is called an adiabatic quantum annealing system.  This isn’t even the controversy, actually, (which we’ll get to in a moment) and many of the above articles remark on the difference (this was a controversy in the past, because D-Wave, for quite a while, wouldn’t let anyone actually test their system, but they’ve been more open recently).  What’s the difference?

Suppose instead of a quantum blanket, Suzie has a quantum annealing blanket.  And to be charitable, let’s say this blanket also doubles in size for each additional friend she has help her.  But when Suzie and her friends bring this blanket down upon their prey, the blanket settles very slowly — little hedgehogs scurrying about as bumps under this great quilt.  Eventually the blanket does settle, trapping some number of hedgehogs under it in cozy little pockets, but the amount of time it takes the blanket to settle increases as the size of the blanket increases.

One can imagine that if the time it takes for the blanket to settle grows too fast as the size of the blanket grows, it could very quickly defeat the purpose of having more friends to stretch the blanket — that is, you might be able to catch a whole bunch of hedgehogs, but I could just as easily, and more quickly, tranquilize the hedgehogs one by one.  And of course, we’re both always handily beaten by ye who wields a true quantum blanket, but such advanced needlework is lost to us as Suzie owns the only one in existence.

So, to justify using this big quantum annealing blanket to catch hedgehogs, you would want to know exactly how this amount of time scaled, i.e., how much longer it took to settle for larger blankets.

Suppose a company that sells quantum annealing blankets claims that their blankets are much better than those “classical” old-fashioned tranquilizer guns.

Suppose further an academic paper is published indirectly bolstering these claims — reporting that these quantum annealing blankets are 3600 times better than certain tranquilizer guns at catching certain types of hedgehogs.

Suppose even further that shortly after this paper is widely misinterpreted in the media, and after this quantum annealing blanket is widely reported as being a quantum blanket, another group demonstrates that a special purpose “classical” tranquilizing gun is actually anywhere from 7 to 12,000 times faster than the quantum annealing blanket at immobilizing hedgehogs (depending on the type of hedgehog), and can do so for approximately 1/10,000th the cost of a quantum annealing blanket.

Suppose even further that it’s still not entirely clear that this company’s quantum annealing blanket can actually catch any type of hedgehog faster than specialized but vastly cheaper “classical” tranquilizing guns.

I’d like to quote an interaction between a science journalist and a vice president of Lockheed that’s symptomatic of what’s wrong here:

There are skeptics who say that true quantum computing is still a generation away. Are you sure you spent millions on the real deal?

I think we are already in the era of quantum computing. For me the academic question of how quantum it is, and how entangled the “qubits” (quantum bits) are, really doesn’t concern me. What I am concerned with is how it can help me reduce costs, make better systems, and accelerate innovation.

This is an excellent question by the journalist, and an excellent politician’s answer by the Lockheed VP.

D-Wave’s quantum annealing system has qubits, and has entanglement, but it doesn’t have entanglement across all of the qubits.  This is perfectly fine.  Quantum annealing machines aren’t meant to be completely entangled — but this means they are manifestly less powerful than quantum computers.

An excellent “academic question” is to ask what sorts of problems the D-Wave system is actually good at solving better than its classical counterparts at solving, where “better” here means both “solves faster” and “scales better” than those classical counterparts.

A few weeks ago, over the course of several days, a heated mud-flinging contest erupted over the benchmarks I alluded to in the hedgehog allegory between a handful of heavy hitters in the field of Quantum Information on Scott Aaronson’s blog (if you only click on one link of this post, this would be the one to click on).  The whole saga is worth reading, but Scott’s initial post (comprised of updates over the course of the whole shebang) is probably the most important.

The conclusion, which essentially every academic quantum information theorist has come to, is that D-Wave’s machine probably doesn’t do anything faster than the best classical counterpart, but the jury is still out.

Which means that the “academic question” of what the entanglement scheme in the D-Wave system actually gets you is the only question of any interest.  If you don’t care about this “academic question” (and there are tons of great reasons to care about this question!), then you’ve just hedged $10,000,000 on something that, to you, will be either a piece of exotic, but useful hardware, or a refrigerator.

The NASA/Google consortium seems to be addressing this question directly, but it’s slightly alarming that what they’re doing amounts to benchmarking the device for D-Wave, at a rather large cost.

Now, because nearly everything that could be said about this ordeal has already been said on Scott’s blog or elsewhere, I’ll close with a quote of Scott’s from the aforementioned mudflinging:

Suppose that … it eventually becomes clear that quantum annealing can be made to work on thousands of qubits, but that it’s a dead end as far as getting a quantum speedup is concerned.  Suppose the evidence piles up that simulated annealing on a conventional computer will continue to beat quantum annealing, if even the slightest effort is put into optimizing the classical annealing code.  If that happens, then I predict that the very same people now hyping D-Wave will turn around and—without the slightest acknowledgment of error on their part—declare that the entire field of quantum computing has now been unmasked as a mirage, a scam, and a chimera.  The same pointy-haired bosses who now flock toward quantum computing, will flock away from it just as quickly and as uncomprehendingly.  Academic QC programs will be decimated, despite the slow but genuine progress that they’d been making the entire time in a “parallel universe” from D-Wave.  People’s contempt for academia is such that, while a D-Wave success would be trumpeted as its alone, a D-Wave failure would be blamed on the entire QC community.

Slightly alarmist perhaps, but then again, I didn’t just spend $10,000,000 on something that might be no better than my laptop.

Leave a Reply

4 comments

  1. Mary Freeman

    Excellent! I love the hedgehogs analogies, although I’ve never seen one. I think they are imaginary like unicorns and Eskimos.

  2. “D-Wave does not sell a commercial quantum computer, they sell what is called an adiabatic quantum annealing system.”

    A big enough D-Wave can run standard quantum algorithms:

    http://epubs.siam.org/doi/abs/10.1137/080734479

    Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation

    “The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.”

  3. Daniel Freeman

    If a D-Wave were provably an adiabatic quantum computer, I would agree with you. But it actually hasn’t yet been demonstrated that it performs reversible adiabatic quantum evolution.

    As per the abstract from the USC paper (http://arxiv.org/pdf/1212.1739v1.pdf), the decoherence timescales of the superconducting flux qubits are an order of magnitude shorter than the adiabatic evolution timescale.

    That the authors see “signatures of Quantum Annealing” on much longer timescales is scientifically incredibly interesting, but it ****absolutely does not prove the d-wave is an adiabatic quantum computer****.

    The firm correspondence between adiabatic quantum computers and the gate model only holds if the qubits are entangled over the course of the adiabatic evolution (which is implicit in the paper you’ve quoted).

    Further, just making the D-Wave bigger naively absolutely won’t work, even according to one of the authors of the USC paper! From Scott:

    “Daniel Lidar emailed me to clarify his views about error-correction and the viability of D-Wave’s approach. He invited me to share his clarification with others—something that I’m delighted to do, since I agree with him wholeheartedly. Without further ado, here’s what Lidar says:

    I don’t believe D-Wave’s approach is scalable without error correction. I believe that the incorporation of error correction is a necessary condition in order to ever achieve a speedup with D-Wave’s machines, and I don’t believe D-Wave’s machines are any different from other types of quantum information processing in this regard. I have repeatedly made this point to D-Wave over several years, and I hope that in the future their designs will allow more flexibility in the incorporation of error correction.

    Lidar also clarified that he not only doesn’t dispute what Matthias Troyer told me about the lack of speedup of the D-Wave device compared to classical simulated annealing in their experiments, but “fully agrees, endorses, and approves” of it—and indeed, that he himself was part of the team that did the comparison.”

    In other words: even one of the USC authors doesn’t really think the D-Wave is providing a speedup, nor will naively scaling the number of qubits up help.