Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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?

share|improve this question
2  
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

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.