Slashdot Mirror
Scientists Dubious of Quantum Computing Claims
Dollaz wrote with a link to the International Business Times, which questions the authenticity of D-Wave's Quantum computing. We discussed the 'Sudoku playing' computer yesterday, but scientists in the field have expressed a lot of distrust of the company's findings. The machine was not available for inspection during or after the demo, and even if the technology was working as intended there is some doubt that it can be scaled. The article points out that "notwithstanding lofty claims in the company's press release about creating the world's first commercial quantum computer, D-Wave Chief Executive Herb Martin emphasized that the machine is not a true quantum computer and is instead a kind of special-purpose machine that uses some quantum mechanics to solve problems." Good to see people in the field questioning 'breakthroughs'.
The machine was not available for inspection during or after the demo, ...
... that's how a quantum mechanical system works -- you look at it, you change it. I can imagine these guys in peer review, "Look, this double-slit experiment of yours is really interesting and all, but we can't publish your results unless you record the photons going through EACH slot, on EACH time, otherwise, how do we know you're faking it?"
Yes
I kid, I kid. I think...
Apology to Ubuntu forum.
Time to check the cat.
Quantum computing researcher Scott Aaronson wrote some good anti-hype pieces about the D-Wave PR here and here, focusing on their incorrect marketing claims to be able to solve NP-complete problems in polynomial time. The first link also has an update with comments from Lawrence Ip of Google, who clarifies what the D-Wave people are really claiming.
Maybe it's not a true quantum "computer", but is that bad? The first electronic "problem solving machines" weren't true computers, either. That doesn't mean that this "custom" quantum machine isn't a useful step in the right direction...
So the first part of the scam is this: even if this device wasn't a quantum device at all it would still work to some extent because when you allow systems to cool they fall into lower energy states. If the 'quantum' aspect of things works then it might find that state faster, but without careful monitoring there's no way of telling if the 'quantumness' had anything to do with what it did. In fact, for large systems we know that it won't be very 'quantum' at all because it will interact with its environment and decohere. But it's a perfect strategy for designing a machine that you can claim is quantum, when it isn't. It stinks of scam.
Secondly: suppose you want to solve a challenging problem with this device. For example you want to search some space for a miniumum of some sort. For this machine to be effective the state space must be pretty large or else you could use a regular classical computer. Consider a billion state problem (quite small really for combinatorial problems). You have to be able to get a system to settle into the minimum energy state despite the fact that there are a billion states nearby all of which have almost the same energy. Just the tiniest input of energy and it'll jump up from that minimum. There is absolutely no way that they can search a large enough state space and still have the minimum energy state sufficiently far from other states.
BTW This device is quite different from what is conventionally meant by a 'quantum computer', it's more like a quantum, analog computer.
Real and useful 'digital' quantum computers are a long way off. I expect that the size of quantum computers will grow by a bit or so per year at the most. (When I say 'bit' I mean total memory, not the size of the bus.)
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
I think Aaronson has unfortunately done only half his homework. A 16 qit computer can't solve that problem (not fast anyway).
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
There are several things to note about the announcement. First, the emphasis was on selling that this computer can solve NP-Complete problems, something that it is, to say the least, not right. An adiabatic quantum computer, such as the one they claim they had, cannot "solve" NP-complete problems. It can at most give a quadratic improvement, at most. They didn't even showed that the did this. Solving a particular instance of an NP-complete problem (such as the 9x9 sudoku) does NOT mean that you can solve an NP-comp problem. Either they lied, or there were intenionally using language that was not very precise to give the wrong impression. So the things that they said they can do cannot be done.
What did they do? Nobody knows. They were very careful to evade the important question: what did they actually accomplish? They never mentioned qubit decoherence times, fidelity, nothing. These are things they can claim without compromising the trade secrets. They gave a lot of emphasis to saying that the computer is part a classical computer, and part a quantum computer, something that nobody really cares about. What is important is to spell out exactly what was the part of the problem the quantum computer solved.
The CTO has a blog, and he sounds very competent in it. I'm guessing that he just had a lot or pressure from the investors to show *something*. It was just a big show to get some Venture Capitals. Pretty graphics and tech demos are cool for getting fans for videogame consoles and getting VC only, not so much as to make scientific claims.
"There is no teacher but the enemy."-Mazer Rackham
Direct test for a quantum computer:i ty_problem)
Solve any problem polynomially reducable to SAT/3-SAT (http://en.wikipedia.org/wiki/Boolean_satisfiabil
without the use of heuristic algorithms. Further, show it being done in polynomial-time with respect to the problem size.
Naturally, the machine and program would also have to be subject to inspection to show that it wasn't just spitting out a canned response to a problem already worked on and answered by a team of supercomputers elsewhere....
Fortunately, checking the result won't take too long. The check should be calculable on a conventional computer in polynomial-time.
I went to the Vancouver demo of this yesterday and it is pretty clear why they couldn't have it available for inspection at an event like this. It is located in a specially shielded room in their lab to reduce signal noise with a cooling system that cools a portion of the computer down to 4mK (extremely close to absolute zero).
Besides, even if I or anyone else there was able to inspect it, do you really think that we could look at it and say "hey, I don't see any quantum effects"
This is an odd statement, because that's generally what people "in the field" do. The author says this as though it's unusual to see anybody questioning lofty claims. In fact, it's very common. The first slashdot article about this was met mostly with skepticism.
Note: Replying to this post, because I am not getting a "reply" button for the story itself. Anybody else experiencing this bug?
... and then they built the supercollider.
Depending on what you mean by "solve," I think you are a little mistaken on what it means for a problem to be NP-Complete. NP-Complete problems are actually relatively easy to solve. For example, take 3SAT, were you have a bunch of boolean variables, x[1] through x[n], and then a bunch of string of clauses ANDed together, as in (x[1] OR x[2] OR NOT x[3]) AND (x[24] OR NOT x[37] OR x[42]) ... To solve 3SAT you just have to tell me whether there exists some combination of variables such that the expression is true. You can just enumerate all 2^n possible combinations of variable assignments and see if any of them work out to be true. The problem is, it doesn't take very large values of n before it will take you longer than the time civilization has been around to try all the combinations. 3SAT is easy to solve, if you just want an answer. What's still an open question is whether we can come up with an algorithm that can solve it efficiently, where efficiently means in O(n^k) time for some k, rather than O(2^n).
For a problem that actually can't be solved, try the Halting Problem.
Now, the cool thing about NP-Complete problems is that any other problem that's known to be in NP (meaning we can solve them, just some instances will take a ridiculous amount of time to do so) can be efficiently transormed, meaning transformed in polynomial time, into an NP-Complete problem. This means if you can really solve general instances of Sudoku in polynomial time, you can take an instance of the 3SAT problem, efficiently transform it into an instance of Sudoku, then efficiently solve the Sudoku problem and then transform the answer into a solution to the 3SAT problem. If they have really built such a machine, this is a big deal.
I actually interviewed with these guys a few months back. I can tell you I was quite impressed with the facility and they came off as very bright. I also got a tour of the facility so I'll share what I know. The chip core is stored in a large tank roughly 2m tall and cooled to very very near absolute zero. That is then held inside what is in essence a very large faraday cage. All the refrigeration and electronic equipment is kept outside with only passive sensors allowed in the room wherever possible. Apparently electrical noise and stray heat has been a huge hurdle. From what I understood they saw themselves as building chips that would be housed on site and used remotely so it doesn't surprise me that they didn't have a setup that was available for public viewing. The company culture was essentially work till you drop and hope the stock options make you rich.