# How many states can a n qubit quantum computer store?

A classical computer composed of '0' or '1' transistors stores $2^n$ states.

Is it true that a quantum computer composed of '0' or '1' or '0 & 1' qubits stores $3^n$ states?

-
Colin's answer is right. If you have a classical computer with 4 bits, it has 16 possible states, but can only hold 1 of those states at a time. If it were a quantum computer, it could hold all 16 states at the same time, and each state has a complex amplitude reflecting its probability of being observed. That's the superposition. –  Mike Dunlavey Dec 20 '12 at 2:24
A key difference between classical and quantum computers is speed: we can use some much faster algorithms on quantum computers. "the search for the factors of very large integers... with a quantum computer... we can perform the test on all numbers simultaneously and thus only a single test is needed to find the right answer." quoted from scientificamerican.com/… –  raindrop Jan 14 '13 at 21:00
add comment

## 1 Answer

No, it is not true. A quantum computer stores the same $2^n$ states that the classical computer stores. The difference is that the quantum computer stores a linear superposition of those states, where the classical computer can only store one of those states at a time. What you refer to as '0 & 1' qubits are actually linear superpositions of the two basis qubits 0 and 1.

-
A classical computer can also store a superposition of all $2^n$ states if you are thinking in terms of probability distributions. So the difference between quantum and classical is more subtle, and is a matter of ongoing debate and research. –  Dan Stahlke Dec 20 '12 at 13:19
add comment