Slashdot Mirror
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."
So they know where the D-Wave system is, but they cannot definitively measure whether it is actually a quantum computer or not...
A real quantum computer both is and isn't at the same time.
Pretty good is actually pretty bad.
Their computer works not by quantum entanglement but by magic.
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
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).
You may say that now, but wait until PETA find out about the number of cats and flasks of cyanide their prototype gets through every month...
The problem is that it's not faster, and while there's a study that concludes it is, the blog post specifically invalidates this:
About the paper claiming it's faster:
Don't think of it as a flame---it's more like an argument that does 3d6 fire damage
the machine is really just a quantum annealer. you still need real computers to do your solving for things like computational quantum thermodynamics but where the D-Wave comes in, its really just there to assist the solver cluster with a more terse or efficient algorythm. Not bashing it, seeing as some of their jobs run months or years if the D-Wave manages to carve 20-30% off the time of a solver run, then you just saved ~80 days of work.
as to naysayers who think D-Wave isnt in a true quantum state, heres a research paper on the matter http://arxiv.org/abs/1304.4595
Simulations of quantum versus classical annealers show that a classical one has a fairly uniform probability of solving a problem correctly; a quantum device should instead have a low probability of success at solving hard problems, and a high probability of success solving easy ones. This is what D-Wave is shown to do.
disclosure: i work for a large engineering firm that handles computational fluid thermodynamic and finite element analysis simulation as a service. Id be speechless to have one of these ajacent to my datacenter.
Good people go to bed earlier.
But doesn't this suggest that arrays of narrow domain analog computers of this type might be constructed in such a way as to produce a *really* fast general purpose supercomputer? For example, sorting routines are built into most software frameworks. Could we not hybridize a system wherein np hard problems are called from the framework that transfers the sort to an quantum adiabatic solver and returns an answer?
Please do not read this sig. Thank you.
Scott's blog post and the comment thread there are really worth reading. Entanglement isn't the only issue. A major part of this also is whether the process that the D-Wave machine is doing is anything that is even faster (either in practice or asymptotically) than a classical computer. Right now, the answer for the first is clearly no. Scott describes mildly optimized systems which have been shown to effectively outperform D-Wave at its own problem. The second question- of asymptotic performance is a little trickier but the answer looks like "probably not". It is also worth noting that the D-Wave machines do a very specific optimization problem, of unclear usefulness, and cannot be used at all for many of things that we think of as what one wants a quantum computer for, like Shor's algorithm http://en.wikipedia.org/wiki/Shor's_algorithm to factor integers.
In fairness to D-Wave though if one thinks of this as essentially a research machine, then not doing as well as conventional systems isn't that much of mark against it any more than very early cars being slower than horses. However, D-Wave is trying to sell these machines commercially. And Scott expresses worry that there's going to be a serious backlash against quantum computing as a whole when the the D-Wave hype bubble bursts. Apparently, D-Wave has now gotten about 100 million in funding, so at least, this is an extremely suboptimal allocation to resources when much more promising academic quantum computer research projects are getting much less money.
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.
Whether this thing turns out to be the real McCoy (dammit Jim, I'm a quantum annealer) or not, one thing D-Wave has done is proven that there are customers who will pay $10M to be on the cutting edge of quantum computing for a few years. This should help boost investment and entrepreneurship in other companies. Eventually, one of them will revolutionize everything.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
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) 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).
Anything can be pushed to the limits of what we know, and on occasion, things work, but not for the reasons you think it did. This is sufficiently close to the cutting edge that it may be operating correctly, but that we only think we understand why.
F'rinstance, for years, we thought about electricity as a liquid. Voltage equaled pressure. Amps equaled volume. The math worked. Nature wiggled it's eyebrows suggestively.
BUT, electricity is NOT a liquid. It works the way it does for completely different reasons. It just took a while for us to figure that out. Yet, even before we understood this, we build practical machinery.
Please do not read this sig. Thank you.
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.