First Evidence That Google's Quantum Computer May Not Be Quantum After All 224
KentuckyFC writes "In May last year, Google and NASA paid a reported $15 million for a quantum computer from the controversial Canadian start up D-Wave Systems. One question mark over the device is whether it really is quantum or just a conventional computer in disguise. That's harder to answer than it sounds, not least because any direct measurement of a quantum state destroys it. So physicists have to take an indirect approach. They assume the computer is a black box in which they can input data and receive an output. Given this input and output, the question is whether this computing behavior can be best reproduced by a classical or a quantum algorithm. Last summer, an international team of scientists compared a number of classical algorithms against an algorithm that relies on a process called quantum annealing. Their conclusion was that quantum annealing best reproduces the D-Wave computer's behavior, a result that was a huge boon for the company. Now a group from UC Berkeley and IBM's Watson Research Lab says it has a found a classical algorithm that explains the results just as well, or even better, than quantum annealing. In other words, the results from the D-Wave machine could just as easily be explained if it was entirely classical. That comes on the back of mounting evidence that the D-Wave computer may not cut the quantum mustard in other ways too. Could it be that Google and NASA have forked out millions for a classical calculator?"
Would D-Wave Take That Risk? (Score:5, Interesting)
Do we really think that D-Wave Systems would take that risk? They have to know that just about every major university and tech company will try to prove them wrong. Not to mention that Google will probably spend more to verify this purchase than they made on the purchase itself.
I don't know D-Wave Systems from Adam, but is this a risk they would take?
Re:Quantum Cash! (Score:5, Interesting)
Why buy something that isn't demonstratively faster than the old stuff
Research often requires baby steps. If you ignore every new idea whose first (or hundredth!) iteration isn't already better than what we have, you'll ignore every new idea.
Re:It makes me feel better (Score:5, Interesting)
LMOL...the difference is they're suppose to know.
The point is that no one knows. Yeah, everyone knows that the D-Wave device is a rather different approach than "traditional" quantum computers, but that doesn't mean it can't exploit the same effects... until the research determines that it doesn't.
It's also the case that even if it's not actually a quantum computer there may still be some way the concept can be extended to become a useful device, which may be discovered through experimentation. Or maybe it can't. Research is like that.
(Disclaimer: I'm a Google engineer, but don't work on anything remotely as interesting as quantum computing, and don't know much about it.)
Re:Would D-Wave Take That Risk? (Score:5, Interesting)
Chances are, they don't know themselves exactly how "quantum" the system is. It's unlikely to be an outright fraud --- there's something other than a Core 2 Duo on the inside faking quantum results --- but a system working on the hairy edge of current technical understanding. They've built something that has a bunch of cryogenic doodads and performs annealing, but the technical understanding isn't all there. That said, they have demonstrated signs of acting in bad faith --- being very cagey about offering real details, and performing poorly-done comparisons against sub-optimal classical systems. So, they know that even they don't know whether the system they have lives up to claims, and are acting like a for-profit corporation rather than researchers with integrity about it.
Re:Who cares? (Score:3, Interesting)
> Obviously, you don't have a use for a quantum computer if you can't find a way to determine if it's a
> quantum computer
This. How are they even programming this thing? As I understand it, a quantum computer doesn't just take your classical function and execute it faster; but instead would come at the problem via an algorithm designed to find the answer using algorithms that rely on quantum effects.
Is there any reason to believe a quantum computer algorithm, run through a classical system, should produce the correct answer?
I mean, i am sure the people testing this understand it at a deeper level than I do, but I am surprised that this is so hard to verify.
A quick overview (Score:5, Interesting)
Quantum effects are not hard to understand, they're just counter-intuitive to everyday experience. This site [lesswrong.com] has a good explanation of QM, and how it differs from normal experience.
The universe doesn't work in specifics until something is measured. It doesn't choose parameters for particles (spin, position, &c) at the outset and let things evolve like little billiard balls.
Instead, it uses probabilities which flow and interact with one another. These probabilities have both amplitude and phase, so that the interactions are wave-like as well as probability-like. For example, because of this wave-like interaction it's possible for two non-zero probability flows to completely cancel to zero.
The universe appears to calculate probabilities for all possible outcomes and only choose one when the measurement is made. When particles are entangled, you increase the number of possible outcomes. For each new particle that becomes entangled you increase the number of possible outcomes by a factor of two. Ten particles will have 2^10 = 1024 possible outcomes, and so on.
So to do math at the quantum level, you take a set of entangled particles and set up the measurement so that division with no remainder has probability one while division with any other remainder has probability zero. Then load your register with all the integers, let the probabilities interact, and take the measurement.
You have just performed division using all the integers at once.
If you can do this with a reasonably large register you can check all the factors of a composite number in linear time - the time it takes you to load sqrt(P) divisors into the register.
Easy peasy!
An interesting side-note is the idea of the universe keeping track of all possible outcomes until a measurement is made. If this works as predicted, the universe will have to keep track of 2^3000 possible outcomes, depending on the key length (3000 is the recommended RSA key length to be secure until 2030).
There are only ~10^80 = 2^240 atoms in the universe. If a quantum computer works as predicted, one wonders how and where the universe keeps track of all these states. At the very least, quantum computing is interesting because it will allow us to probe the limits of the universe in an entirely new domain.
Here's hoping we don't encounter a buffer overflow.
(Note: Some facts were harmed in the making of this explanation.)