Scientists Dubious of Quantum Computing Claims 107
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'.
How to verify their claims? (Score:2, Interesting)
I'm legitimately curious. Such a device has never been built, how do these guys prove they have one? They say themselves they aren't certain if it's quantum-ing up the sudoku.
Good blog responses (Score:5, Interesting)
Marketing department at work... (Score:3, Interesting)
You could pick any device that returns different numbers at different times. It could be a microphone, a geiger counter, a clock og a quantum device
Now pick the quantum device, and call the whole device a "Quantum computer"
This is normal in marketing departments. The only unusual thing here is that they got the engineering department to go with them.
I've been saying for ages it's a scam (Score:5, Interesting)
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.)
Article makes things seems worse (Score:2, Interesting)
Also, while the article claims it might not be a "true quantum computer", it never really says how that's different from a "computer that uses quantum mechanics to solve certain problems", and given its audience, can't possibly expect its readers to know. To me, this just sounds like journalists looking for something to hype about.
Re:Sudoku (Score:2, Interesting)
Re:He kind of has a point... (Score:5, Interesting)
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.
Reply button missing (Score:5, Interesting)
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?
Re:Well DUH (Score:1, Interesting)
Link 1 http://video.google.com/videoplay?docid=8033280380 582597891&hl=en/ [google.com]
Link 2 http://video.google.com/videoplay?docid=-687784917 8932916346&hl=en/ [google.com]
Misconceptions about NP-Completeness (Score:5, Interesting)
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.
They didn't hire me so they must know something (Score:4, Interesting)
Re:He kind of has a point... (Score:4, Interesting)
You have your reducibility direction mixed up: even really easy problems (like sorting, or outputting "2") are reducible to SAT. It's the hard problems that SAT reduces to.
Not that this matters, because quantum computing is very unlikely to be able to solve NP-complete problems. It does seem to help with very structured problems like factoring, though. No, factoring is (almost definitely) not NP-complete.
Further, show it being done in polynomial-time with respect to the problem size.
Polynomial-time is an asymptotic notion. It can't be verified for a particular problem size (or finite set of problem sizes). It is purely an analytical concept, not an experimental/testable one.
Re:They didn't hire me so they must know something (Score:3, Interesting)
I've done a lot of smoke and mirror shows myself, and this demo did not smell funny at all.
The headline "Scientists Dubious of Quantum Claims" is rather sensationalist for what they're actually saying in the article.
Can you really fault them for not wanting to move a computer that has to be housed in a special chamber, cooled to near absolute zero, and be havily shielded from any outside interference?
Besides, judging by the questions people asked, not a single person in the audience could have verified that it was a computer and not a big refrigerator.
What I saw were a group of really smart people who are onto something real, and need to drum up enthusiasm for a later release of their product.
Their machine appeared to do what they claimed it did, and while it is quite easy to fake it, I didn't get such an impression at the demo.