Yay, probabilistic computing.
You have a 99.5% chance that your PayPal transaction has succeeded. A bit like using a NoSQL database.
You have a 99.5% chance that your PayPal transaction has succeeded. A bit like using a NoSQL database.
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]
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.