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.
In case anyone is starting to look forward to the bright future of compact and handy quantum hard drives with the storage capacity of a trillion Libraries of Congresses, it is important to realize that almost none of the information in such a device would be accessible. Even though our 100 quantum coins in principle contain a stupendous amount of information, trying to read it would force each coin into a definite state of either heads or tails, yielding only 100 bits of information. In spite of this inconvenient fact, the complexity of the quantum state can still be exploited if we realize that it is possible to manipulate the coins without actually looking at their orientation. For instance, the acts of flipping a coin over or swapping the position of two coins are perfectly well-defined even if it is unclear which side of what coin is up. It even turns out that those two operations (flip and swap) are all that is required to perform any arbitrary computation with the coins, at least if we allow partial flips and swaps. For instance, a quarter flip of a coin that is 100 percent heads up would yield a coin showing 75 percent heads (and 25 percent tails). Another three-quarter flip is required to complete the flip and make the coin 100 percent tails. Because the 100 quantum coins can simultaneously represent all possible 100-bit numbers in their huge quantum state, the computation may be carried out on all those numbers in a single parallel computation. This built-in parallelism is the key to the power of quantum computers.
For example, a central problem in modern cryptography is the search for the factors of very large integers. In a normal computer, the most efficient approach essentially consists of dividing the integer by every number smaller than its squareroot to see which ones will factor it. As more digits are added to the integer, the time required for this test grows very rapidly. With a quantum computer, however, factorization is a snap, because we can perform the test on all numbers simultaneously and thus only a single test is needed to find the right answer.
Designing efficient quantum algorithms turns out to be very challenging and only a handful are currently known, most notably the factorization algorithm mentioned above. Constructing a working, full-scale quantum computer is an equally difficult problem, as the collective quantum states at its heart are extremely fragile and difficult to manipulate. This makes quantum computing one of the great intellectual challenges of our time, and this fascinating subject is likely to remain at the forefront of research for many years to come.
Rights & Permissions
