Quantum computers no better than classical ones for NP-complete problems. | Hacker News Reader

Quantum computers no better than classical ones for NP-complete problems.

arstechnica.com

49 pointsamichail17 comments

This has almost certainly only been shown for a restricted class of adiabatic quantum computers. The full adiabatic quantum computing model is equivalent to ordinary quantum computing (http://arxiv.org/abs/quant-ph/0405098 ). If the linked article is literally correct, then that means quantum computers can efficiently solve NP-complete problems if and only if classical computers can efficiently solve NP-complete problems. That may be true, but I'd be very surprised if someone has proved it.

My guess: the paper under discussion probably shows that some particular adiabatic approach to solving NP-complete problems fails - most likely, some variant on the ideas in http://arxiv.org/abs/quant-ph/0001106. That's well and good, but a long way from proving that quantum computers are no better than classical at solving NP-complete problems. Variants on this result have been floating around for years - I first heard of one in 2000. This is probably an improvement on those early results.

Unfortunately, the link to the original paper is broken at present, so that's just a guess.

If such a result were proved, what would happen to the field of quantum computing?

Hard to say. My first instinct is probably not a whole lot. It's more or less conventional wisdom in the field that quantum computers are unlikely to be able to solve NP-complete problems in polynomial time. The argument for this conventional wisdom is heuristic (and certainly open to doubt, maybe most people are wrong), and it's in this paper: http://arxiv.org/abs/quant-ph/9701001 But in any case, it's one thing for something to be widely believed, and another thing to have hard evidence. People might respond quite dramatically to such evidence.

Quantum computers are known to solve some problems faster than classical computers. For example, see Shor's Algoroithm (http://en.wikipedia.org/wiki/Shors_algorithm) for factorization, which finds factors of a number in polynomial time on a quantum computer. This alone is an enormous breakthrough.

The question is whether Quantum Computer can solve NP problems in Polynomial time, which no one knows yet.

As disappointing as this result is, I'm glad that Ars seems to do science reporting with remarkable clarity.

Actually, as an Ars commenter explains, Ars did kind of a bad job explaining NP. NP is the class of problems with an easily verified proof for existence, not the class of all exponentially solvable problems as they seem to imply (EXPTIME). Example: Is a boolean formula satisfiable? Provided an assignment for its variables, it is easy to check if it is a satisfying assignment.

Explaining NP-complete to even a technically-educated audience is always tricky. Sometimes a somewhat misleading explanation is still going to get them closer to the important bits than a precise technical definition would.

I'd probably write: NP-complete refers to a special class of notoriously difficult problems. A solution to even one of them would lead to a solution to all of them, a development which could have radical real-world implications. (Insert good example here.)

I've had a lot of success explaining "easy to check a solution, but hard to come up with one" to people. It really doesn't matter whether people understand NP-complete and how polynomial reductions work. Just understanding what's included under NP is enough.

If I were writing this article, I'd explain NP as above, and then say "research now shows that there are many problems in NP on which quantum computers will offer no improvement."

I remember reading an example of "easy to check but hard to come up with" which is probably good for non-technical audiences. Its something like: You walk into a party and you want to know if you know anyone. To find out, you need to look at everyone and check. Alternatively, someone can point to someone and say "do you know John" and you can check that much faster.

However, I think that reductions are critical to understanding why we care about NP-complete problems so much. The best example I've been able to give of a reduction is "reducing" addition to subtraction.

someone already mentioned the NP bit, but I also don't think its that disappointing [or surprising]. There's plenty difficult problems outside of NP complete that a quantum computer could conceivably be quite handy at. e.g. shor's algorithm for factoring an integer into primes. or grover's search. or a universal quantum simulator (as mentioned)

I don't believe this. If this were true, it would imply that the decision version of the integer factorization problem is not NP-complete. That sounds too good to be true.

As far as I can tell, D-Wave's adiabatic quantum computer has never demonstrated polynomial-time factoring either. The result mentioned in ars technica (DOI link is down, and a scholar search didn't find it) might also invalidate the use of said computer for this purpose.

quantum computers are not KNOWN to be better than classical ones for NP-complete problems (although many believe that no form of computation available in this universe can solve NP-hard problems in polynomial times)

What a relief! :)

This article seems to say the ADAIABATIC quantum computers aren't better than classical ones. In other words other quantum computers might still be useful where D-WAVE's adiabatic approach will not?

The adiabatic quantum computer from D-WAVE has been criticized previously for not being a 'real' quantum computer.

From the article:

"Furthermore, all types of quantum computers have been shown to be mathematically identical, so if one won't work, none of them will."

This is vague, and does not say if it pertains to only QC's used on problems in NP, or in general.

As other posters have noted, the subject resists simplification. For more, see:

http://en.wikipedia.org/wiki/Quantum_computer#Relation_to_co...

http://qwiki.stanford.edu/wiki/Petting_Zoo#BQP

Quantum computers work just fine, they just can't solve NP-complete problems faster than a classical computer.

This is fine, since nobody except D-wave and their somewhat credulous investors (including folks who should have known better) ever really thought they would.

Reply on news.ycombinator.com