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.