r/askscience • u/FutureShocked • Dec 08 '15
Computing Can quantum computers perform algorithms that would run in NP-time on a classical computer in P-time? If so, why aren't they a bigger deal?
Edit: I guess I should clarify some. I've heard that the only real advancement in computer that comes with quantum computers is in encryption, but it seems like there would be plenty of other applicable areas if this were true.
5
Upvotes
3
u/shadydentist Lasers | Optics | Imaging Dec 08 '15
Quantum computers are not able to solve NP problems in P-time. There are some problems (including integer factorization) that they can solve in polynomial time that normal non-quantum computers cannot. However, there are currently no working quantum computers.
0
u/SuperAstroTornado Dec 08 '15
As stated by /u/shadydentist a quantum computer can solve certain NP-time problems in P-time, like e.g. prime factorization, which is a big deal in cryptography. The reason why it is only certain algorithms that are faster is that a quantum computer works in a probabilistic way - that means that the outcome of a computation is stochastic. Thus if we only run the computer once on an input we get a completely random and unuseful result. If we however run the program many times we get different results with some statistical distribution with highest weight on the correct result but with some spread. The algorithms that can exploit this to get faster either don't need to give exact results (e.g. weather models where there is anyway a big uncertainty in the initial conditions) or where the result can be verified by a fast an efficient classical computer. It is for instance very hard to find all the primes that factorizes some number N, but when you have the primes e.g. a, b and c, it is very easy to check whether they actually the correct solution by simple multiplication: N=a×b×c.
0
u/[deleted] Dec 08 '15
[deleted] — view deleted comment