Some Scientists Question Whether Quantum Computer Really Is Quantum

gbrumfiel writes "Last week, Google and NASA announced a partnership to buy a new quantum computer from Canadian firm D-Wave Systems. But NPR news reports that many scientists are still questioning whether new machine really is quantum. Long-time critic and computer scientist Scott Aaronson has a long post detailing the current state of affairs. At issue is whether the 512 quantum bits at the processor's core are 'entangled' together. Measuring that entanglement directly destroys it, so D-Wave has had a hard time convincing skeptics. As with all things quantum mechanical, the devil is in the details. Still it may not matter: D-Wave's machine appears to be far faster at solving certain kinds of problems (PDF), regardless of how it works."

Re:If it works - it works

[Anonymous Coward]

You really need to RTFA. It's slower than an optimized implementation of the same thing on a classical computer (and one that costs a lot less than $10m).

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:If it works - it works

[Certhas]

Indeed, the summary is misleading.

Citing from Aaronsons blog:

Among the many interesting comments below, see especially this one by Alex Selby, who says he’s written his own specialist solver for one class of the McGeoch and Wang benchmarks that significantly outperforms the software (and D-Wave machine) tested by McGeoch and Wang on those benchmarks—and who provides the Python code so you can try it yourself.

and

As I said above, at the time McGeoch and Wang’s paper was released to the media (though maybe not at the time it was written?), the “highly tuned implementation” of simulated annealing that they ask for had already been written and tested, and the result was that it outperformed the D-Wave machine on all instance sizes tested. In other words, their comparison to CPLEX had already been superseded by a much more informative comparison—one that gave the “opposite” result—before it ever became public. For obvious reasons, most press reports have simply ignored this fact.

In other words, if it works, it works, except that it doesn't.

Re:it is and it isnt

[JoshuaZ]

This is the sort of thing where it helps to read Scott's post. He specifically discusses the primary claim here:

Namely, the same USC paper that reported the quantum annealing behavior of the D-Wave One, also showed no speed advantage whatsoever for quantum annealing over classical simulated annealing. In more detail, Matthias Troyer’s group spent a few months carefully studying the D-Wave problem—after which, they were able to write optimized simulated annealing code that solves the D-Wave problem on a normal, off-the-shelf classical computer, about 15 times faster than the D-Wave machine itself solves the D-Wave problem! Of course, if you wanted even more classical speedup than that, then you could simply add more processors to your classical computer, for only a tiny fraction of the ~$10 million that a D-Wave One would set you back.

Re:Not General Purpose

[JoshuaZ]

There are a lot of problems wit this idea. Among other issues, quantum computers, even general purposes quantum computers, cannot as far as it is known solve any NP-hard problem in polynomial time. It is strongly suspected by people in the field that BQP (roughly speaking the set of problems easily solvable on a quantum computer http://en.wikipedia.org/wiki/BQP [wikipedia.org]) does not contain NP. There are also a variety of problems which are conjectured to be intermediate between P and NP which do not have known BQP algorithms. The set of things where a quantum computer can provide a lot of speed up is as of right now, highly specialized. That said, the long-term plan isn't that far off of what you are talking about, using general purpose classical machines to do most computations and only call the quantum computer when one has a problem of a specific type that substantially benefits from it (either from a drop into polynomial time from worse than polynomial time, or just a massive polynomial speedup).

Re:Stupid Question of the Day!!!!

[JoshuaZ]

he reason I ask is that a while back on /. I was educated about the nature of Base-10 computing. Prior to this, I'd spent my entire life thinking that Base-10 WAS mathematics, and I'd had no reason to assume or even imagine that there could be any other type of mathematics than Base-10. Base-10 was the pinnacle of mathematics to me. Then I find out that Base-10 is probably the most efficient to date for our society, but that it is not the only way to count; and that Pi is only Pi because of Base-10.

No. Pi will be the same regardless of base. The digits of Pi will be different if you write it in a different base, but this is simply a representation, not a change in what the number is. If you do calculations involving Pi in one base and do the same thing with another base and then convert the answer from one to the other you will get the same thing.

Your general question is a good one. In fact, one of the major things people want to use quantum computers for is to do simulations of quantum systems, which they can do, but which are extremely inefficient (both in terms of time and memory) on a classical computer. So people are looking at problems which are practically not doable on a classical computer. At the same time though, we know that a quantum computer can be simulated on a classical computer with massive resource overhead (essentially exponential slowdown), so we know that anything you can do on a quantum computer you can do on a classical computer if one is patient enough.

Re:D-Wave's Dirty Little Secret

[flayzernax]

One is a bunch of mathematical equations modeling a universe.

Math is not real. The models are not real. They are virtual.

Not saying that quantum mechanics doesn't have some robust models. But it is not "real" in an empirical sense. It is also not complete.