3 ms·
It's more useful for problems in the NP-Complete set, where you can write an algorithm that should take a very long time to perform, but takes very little time
by sukuriant 16y ago
It's more useful for problems in the NP-Complete set, where you can write an algorithm that should take a very long time to perform, but takes very little time to check.
Take the 3-sat problem, for example. It takes a very long time for conventional algorithms to produce a correct answer; but, given a potential solution, it takes very little time to check for correctness. It's this area that quantum computers could shine in. Get a potential answer from the machine and check its accuracy very quickly. If wrong, try again.
[edit: if I misunderstand quantum computers, forgive me. This is just what I thought their allure was]
- gjm11 16y agoQuantum computers are not known to be able to solve NP-complete problems in polynomial time. (Assuming for the sake of argument that we can actually build them.) There are problems -- factorization, as others have already said, is the commonest example -- that (1) are not known to be solvable classically in a reasonable amount of time and (2) are known to be solvable by a quantum computer in a reasonable amount of time. But they aren't NP-complete problems.
- vmind 16y agoQuantum Computers are able to solve problems of complexity BQP in polynomial time. BQP is suspected to cover all problems in P, some in NP (but not NP-complete), and some outside of NP but in PSPACE. (http://en.wikipedia.org/wiki/BQP http://en.wikipedia.org/wiki/BQP)
- sukuriant 16y agoAh! That clears things up quite a bit. I'm surprised they're not able to work at the NP-C set. Is it because the probability of a right answer is so small?