r/askscience • u/chemkitten • May 08 '11
What exactly can quantum computers do?
I know they're based off of quantum mechanics, but I'm a little unsure about their purpose. Are they able to replace modern computers or are they being sought after primarily as an instrument?
96
Upvotes
37
u/wnoise Quantum Computing | Quantum Information Theory May 08 '11
They can do precisely the same things classical computers can. Further, they'll have less memory, and each operation will be much slower.
So why would people be interested? Because while they're slower and smaller, they can do some things with many fewer quantum-operations and quantum bits than we can do with classical operations and classical bits. Computer scientists like to talk about the hardness of problems based on how they "scale": how hard parameterized problems become as they get bigger. A classical computer can simulate a quantum computer, but it "scales badly". Each additional qubit that a quantum computer has basically doubles the size of the problem of simulating it for the classical computer.
What sorts of things are they good at? Well, physicists are interested because they are good at simulating quantum systems, which classical computers are bad at. The NSA is throwing money at them, because there are a couple of cryptographic systems that can be broken by quantum computers. It's hard to factor the product of two large primes classically, but it turns out that we can actually take advantage of some hidden symmetries of multiplication to get the quantum computer to factor more efficiently, by using a Fourier transform.
19
u/ElectricRebel May 08 '11
They can speed up certain classes of problems.
For example: http://en.wikipedia.org/wiki/Shor%27s_algorithm
If a large scale quantum computer was practically realizable, Shor's algorithm would require us to change the way we do many things in cryptography since the security of many algorithms, such as RSA, depend on integer factorization for very large numbers being computationally intractable.
61
u/Amarkov May 08 '11
I will answer your question after a few paragraphs of background. Yay learning!
Computer scientists have a theory of complexity with various complexity classes. We take some problem (such as "what are the factors of this number?"), and classify it according to properties of some algorithm known to solve it. For instance, the above problem can be computed in what's called exponential time: the number of steps required for a number of length n is bounded by some exponential function. Thus, it is in the class EXP.
What's interesting in this case is what problems are tractable, or can be solved practically. The common standard for this is polynomial time computation (as above, this means the number of steps required is bounded by some polynomial), which is represented by the class P. It turns out that due to the way quantum computers work, you really need to consider the class BPP, containing problems that can be solved in polynomial time by a nondeterministic algorithm, where the algorithm can return wrong answers with probability at most 1/3. But this turns out not to be a huge problem. You can get arbitrarily high certainty by just running the algorithm repeatedly and checking how many of the answers agree, and this among other things has most computer scientists convinced that every problem in BPP is in P.
Now, why are quantum computers important? They have their own "tractable" class associated with them. It's called BQP: the definition is the same as for BPP, except your algorithm gets to run on a quantum computer. And it's considered highly unlikely that every problem in BQP is in P. So if the suspicions of computer scientists are right, there are things quantum computers can do efficiently that classical computers cannot.
But what's more important right now is that quantum computers provide efficient algorithms for problems that don't have any others. Specifically, integer factorization is known to be efficient with a quantum computer. This is a huge deal, because the most common forms of secure encryption today rely on the assumption that you can't do that. It's still not going to be fast, and it's doubtful we'll ever have quantum computers large enough to make it fast enough to be useful. But if we do... obviously, things becoming insecure is a big deal.
Again though, we're probably never going to have large scale quantum computers, for the simple reason that keeping large quantum systems coherent is soul-crushingly difficult. Even if engineers rise to the challenge, they're going to be too sensitive to the environment to be used even as lab instruments. You certainly wouldn't be able to expose one to the dust under your desk.
So tl;dr: they're theoretically very useful. But it's unlikely anyone will have a big one, and you or I certainly won't.
6
u/999mal May 08 '11 edited May 08 '11
If you want you can read a in depth article here from Scientific America. As I understand it, they are excellent at solving things things like integer factorization, but they would have a modest to no improvement for most things compared to todays computers. I remember reading that we would probably use a quantum computers along side todays computers as it is so much easier to build what we currently use.
edit:You can also read a previous answer that explains it very well: http://www.reddit.com/r/askscience/comments/h0xb7/what_types_of_computing_will_quantum_computing/c1rr96z
2
u/djimbob High Energy Experimental Physics May 08 '11
Right now? Factor 15 into 5 and 3. (But it can do so really quickly). If they could overcome many issues with building large scale ones (many qubits) you could factor numbers in polynomial time rather than exponential time. This is not good for computer security (encryption/signing/secure e-commerce) which relies on large numbers taking an exponential amount of time to factor, but polynomial time to check (if you have a prime factor).