Hans Robinson, assistant professor of physics at Virginia Polytechnic Institute and State University, explains.
It is easy to think of computation as something abstract that takes place in the realm of ideas, rather than in the physical world. After all, a computer program makes reference to the laws of mathematics, not to the laws of physics. But in the final analysis, any actual computation must be done by a physical system, exploiting the laws of physics to manipulate information that is represented by the state of some device, such as the directions of magnetization at some particular spots on a hard drive or the conductivity of a specific set of transistors inside a computer's memory chip. Because each bit of information can take on two values, different physical states are chosen to correspond to "0" or "1" respectively.
In a quantum computer, the information is represented by physical states that are sufficiently microscopic and isolated so that they obey the laws of quantum mechanics. The spin of a single electron or the configuration of an individual ion, for example, are two among many possible candidates for storing such a quantum bit (or qubit) of information. The jury is still out on which system is optimal, so for the sake of this discussion imagine a computer in which the information is stored in the form of coins placed on a tabletop, with heads ("1") and tails ("0") being the two possible states of each bit. Then convert the tabletop into a quantum computer by substituting quantum coins for which heads and tails are quantum mechanical states.
A normal coin can be placed on a table to show either heads or tails, reflecting the fact that the bit it represents must be valued at either 1 or 0. In contrast, the laws of quantum mechanics allow our quantum coins to show both heads and tails at once (just like Schrödinger's famous cat could be both dead and alive at the same time inside a sealed box), to whatever degree we choose. This ability comes with the important provision that when we actually measure the orientation of a coin, it will make the choice between the two states. For instance, it is possible to prepare a coin in a state that is 75 percent heads and 25 percent tails. The coin would remain in this state until someone measures it, which makes the coin randomly choose between heads and tails, with heads being three times likelier than tails. This randomness is not caused by a lack of knowledge of the coin. The coin really chooses a definite state only when looked at, and, until that happens, its state is completely described by a single number: the degree to which it is showing heads, or 75 percent. It may seem very strange that the mere act of looking at a coin would change its state. The phenomenon arises from the extreme fragility of quantum states. Any and all interactions with their environment have a profound effect, and measurement inevitably requires interaction. A quantum coin is in fact liable to collapse onto a pure heads or tails state if any information at all about it is, even in principle, available to the outside world. A quantum computer must therefore maintain a very strict isolation of its constituent qubits in order to function.
If we expand our view to two quantum coins, there are clearly four possible results of measuring their state: both heads (1,1), both tails (0,0), and two combinations of one heads and one tails (0,1 and 1,0). Quantum mechanics allows us to assign any weight we want to each combination, as long as the total adds up to 100 percent. It follows that three numbers are needed to completely describe the two coins (the fourth is constrained because the total must add up to 100 percent). Similarly, we need seven numbers for three coins, 15 numbers for four, 31 for five, and so on. The complexity of the quantum state quickly becomes incredibly large: to describe only 100 quantum coins requires 1,267,650,600,228,229,401,496,703,205,375 different numbers--many trillion times the storage capacity of all computers ever made.