Test: Quantum Or Not, Controversial Computer No Faster Than Normal

sciencehabit writes The D-Wave computer, marketed as a groundbreaking quantum machine that runs circles around conventional computers, solves problems no faster than an ordinary rival, a new test shows. Some researchers call the test of the controversial device, described in Science, the fairest comparison yet. "...to test D-Wave’s machine, Matthias Troyer, a physicist at the Swiss Federal Institute of Technology, Zurich, and colleagues didn't just race it against an ordinary computer. Instead, they measured how the time needed to solve a problem increases with the problem's size. That's key because the whole idea behind quantum computing is that the time will grow much more slowly for a quantum computer than for an ordinary one. In particular, a full-fledged 'universal' quantum computer should be able to factor huge numbers ever faster than an ordinary computer as the size of the numbers grow." D-Wave argues that the computations used in the study were too easy to show what its novel chips can do.

Comments

The real question in my mind

[TFoo]

Is this a case where D-Wave was fraudulently trying to pass something off as quantum when they knew it wasn't, or did they really and truly not know. How could they not know?

Re:The real question in my mind

[vux984]

No. They are trying to measure the growth of the problem. So its not important which one is absolutely faster, but which one takes relatively more time as the problem becomes more difficult.

The conventional computer should take exponentially longer as the problem becomes mroe difficult. The quantum one should not.

In this test, both took exponentially longer. So either the d-wave doesn't work, or as the manufacturer has claimed, the problems were not setup to demonstrate the class of problems where the d-wave will show better performance relative to problem complexity growth than a conventional computer.

Seems odd to me though that they can't provide easily verified sample problem spaces where their device works better than a conventional PC as the problem gets 'bigger'.

Re:The real question in my mind

[Garfong]

In this test, both took exponentially longer. So either the d-wave doesn't work, or as the manufacturer has claimed, the problems were not setup to demonstrate the class of problems where the d-wave will show better performance relative to problem complexity growth than a conventional computer.

Or the maximum problem size handled by the machine is too small so see the sub-exponential growth. Complexity theory deals with performance on very large data sets, and, if I remember correctly, the D-wave machine is limited to a small problem size (max a hundred or so qbits)

Re:The real question in my mind

[marciot]

How could they not know?

Heisenberg's Uncertainty Principle: If they knew for a fact their claims were fraudulent, they would not know what their claims were. Since they in fact know that they are claiming to have a quantum computer, they cannot know whether the claim is fraudulent or not.

Re:The real question in my mind

[radish]

Which in turn would mean that for the problem space it's capable of operating within it's no faster than a normal computer. Which reduces down to "it's no faster than a normal computer".

Re:The real question in my mind

[HappyPsycho]

GP is actually correct. This is not even a full quantum computer.

"The D-Wave machine is not a universal quantum computer, however, but a more limited "quantum annealer."", which according to wikipedia seems to mean some sort of global minimum finder (given how to find all the local minimum solutions, find the lowest one).

With a mere 512 quibits available on the D-Wave device I'm more than willing to believe they may be still in the area of small inputs where an O(n) algorithm can still beat an O(log n) algorithm (e.g. http://cse.csusb.edu/dick/cs20... )

Re:The real question in my mind

[bill_mcgonigle]

Which reduces down to "it's no faster than a normal computer".

I'm not sure I get this argument. The guys selling this stuff have said for a while that their device is fast enough at quantum annealing to be useful for learning to program quantum computers, and that when their manufacturing ramps up they'll have many more qubits, and I think the implication is that the speed doesn't scale linearly. They were telling the Googles and the Lockheeds, 'look you need to invest in our product and services so you can be ready in the quantum computing space when the better hardware emerges'.

That it's not absolutely faster than a conventional computer at this point is interesting, academically, but not terribly relevant to their sales pitch, unless we can show that the problem at hand fits inside their limited qubit space and the types of algorithms its supposed to be able to handle at this point, and still does not do what's expected of it.

Also: did a tiny Canadian computer company produce a computer that's as fast (within the problem space) as a modern Xeon on their slim budget? That would almost seem revolutionary - AMD can't even do that with GlobalFoundary's fab on their side.

Maybe it is a scam, but this kind of analysis seems somewhat orthogonal to their claims. By all means, pop one open and find the i7 inside, and there won't be any question, but that's not really where we are today.

Re:The real question in my mind

[quax]

Do you know how to use a search engine?

Are you aware of scholar.google.com?

It's really not hard to find papers like this or this.

And yes, the Matthias Troyer who co-authored the first paper is the same guy who conducted the performance study that the /. blurb references.

That D-Wave performs quantum annealing can be regarded as settled. The only question that remains is how useful this may be.

Eight years ago everybody (myself included) thought D-Wave was a scam or just crazy. As new facts emerge smart people (such as Matthias) adjust their judgment.

What problems are Quantum Annealers good for?

[billstewart]

That's been the big question with D-Wave all along. What does it really do, how does it really work, what's it good for, is it real?

Everybody knows what a universal quantum computer is good for - running Shor's algorithm to do factoring and totally wrecking public-key cryptography, plus whatever other problems people care about in the real world. But general-purpose quantum computers so far can't keep enough qbits entangled together to factor numbers bigger than 21 = 3x7, and if anybody's figured out how to do significantly bigger than that, they're keeping it Really Well Hidden (either because they're a government, or because a government will want them to do stuff, or because a government will want them killed.)

Meanwhile, D-Wave has 512 qbits that they claim they'll be able to do something with, and maybe it'll have a chance of being cool or useful. And maybe if you kick in enough megabucks to get a non-disclosure agreement, you'll be able to get some information beyond vague quantumy handwaving. They are the only game in town, after all.

Re:Hope you enjoyed the decade, Geordie.

[quax]

It is not gate based universal quantum computing but special purpose quantum annealing.

If you accept this as a valid approach to quantum computing has certainly been the subject of much debate.

Rather then feeding the trolls ...

[quax]

.... maybe the slahdot stub should have had a link to hear from the horse's mouth?

In this interview Matthias Troyer puts his team's results into the correct context.

Hmm. A "fair" comparison isn't the right test.

[hey!]

What we need to know about is the existence or non-existence of unfair comparisons, i.e., problems that favor the putatively "quantum" computer.

Since I don't expect a quantum computer to be faster at everything, then finding a bunch of solutions to problems that aren't any faster on the "quantum computer" doesn't prove anything, even if the problems look like the kind of problems you'd hope would be quantum-computery. There's not much more you can do than point to the absence of evidence when the burden of proof isn't on you.

The burden of proof is on the vendor here, and standard of "proof" is conceptually simple at least: demonstrate that for some task this device offers any practical advantage whatsoever over the best available conventional technology. That could be in absolute performance against the best available tech(e.g. ASICs and supercomputers), in relative performance over similarly priced systems, or in some practical measure other than performance, such as power consumption. Any clearly identifiable and verifiable advantage counts as positive proof the vendor has something worth paying attention to.

Of course even comparable performance by a novel architecture on some class of problems is interesting, because of the huge advantages a mature technology enjoys. Performance of a new design even in the same ballpark as a mature design suggests future improvements might be in the works. But it's only a suggestion.