Are Quantum Computers Just as Slow as Conventional Ones?

A new study claims that the D-Wave quantum computer is no faster than the PC on your desk, leading many to proclaim the technology as overhyped. Trouble is, the performance tests were too easy and not a true measure of what these machines are capable of doing.

The study, which now appears in Science, claims that the $15 million D-Wave Two is still no faster than normal computers; the machine failed to exhibit the expected "quantum speedup." An ETH Zurich team came to this conclusion after pitting the quantum machine against a conventional one. After the machines tackled a set of problems, it appeared that the D-Wave's quantum aspects didn't confer it any speed advantage.

The press reacted accordingly, calling it "sluggish," and "unimpressive." Some even questioned whether it's quantum computer at all.

But as the researchers themselves noted in the study,

Our results do not rule out the possibility of speedup for other classes of problems and illustrate the subtle nature of the quantum speedup question.

Indeed, this is the problem — and D-Wave is saying the same thing: the tests weren't indicative of the machine's true power. Seth Fletcher of Scientific American spoke to Colin Williams, director of business development for D-Wave, to get an explanation. Williams says that the paper "doesn't say anything fundamental about the scaling of quantum annealing." Moreover,

Troyer's group chose an inappropriate set of problems to perform this test. "The problem ensemble was too easy," he says. Given harder problems, he says, the D-Wave machine would have had a chance to distinguish itself. Williams points to a recent paper by Helmut Katzgraber for support, along with a blog post on benchmarking the D-Wave Two by the Google Quantum A.I. Lab team. Williams also says that problems of the sort outlined in a recent talk by Itay Hen of USC could point to better benchmarking problems.

Any outsider who wades into the D-Wave controversy probably wonders: Why, again, is it so hard to settle this debate? Troyer explained it well in an email, so I'll quote him at length:

It is particularly difficult here because they [D-Wave] use qubits with very short coherence times of the order of a few nanoseconds, while the total time to perform of one annealing run is 20 microseconds. The qubits are thus coherent for only a fraction of the total time, and this raises the question whether they are "coherent enough" or "quantum enough" to show a quantum speedup.

The situation is made even more complex in that we do not know theoretically if even perfectly coherent qubits would offer any advantage (quantum speedup) for the type of optimization problems that there [sic] are interested in. Thus, if one is unlucky, even perfect qubits might not offer any advantage, while if one is lucky one might see quantum speedup even with imperfect qubits with short coherence times.

Again, the point of quantum computers is not necessarily their speed — it's the nature of the problems they're capable of solving, which they'll be able to do with uncanny efficiency.

Read the rest of Fletcher's article at SciAm.

Image: D-Wave Systems.