Progress through Mechanics:
The Quantum Computer


Copyright ©2004, Robert M. and Mary Haythornthwaite Foundation

C. Barbier
Graduate Student at the University of Virginia
Charlottesville, VA
barbier@virginia.edu

Winner of the Robert M. and Mary Haythornthwaite Foundation
Founders Prize and Grant, 2004-2005

Since their conception, computers have inexorably increased their speed and storage capacity. If these trends continue to follow Moore's law, whereby the size of a transistor is predicted to be halved every eighteen months, electronic circuits on a microprocessor may be on an atomic scale in twenty years. The concept of a quantum computer, a computer able to perform memory and process tasks at the atomic level, is already a major driver for many research efforts worldwide, both in academia and industry. If rendered practicable, computing at the atomic scale will revolutionize the information technology industry and thus transform society: the beneficial impacts in the fields of health and medicine, energy, transportation, safety and security and the environment are potentially enormous.

A quantum computer differs from its classical counterpart mainly by the information that it can express. Today's computers work by manipulating bits, which represent one of two states identified by 0 and 1. In contrast, quantum information is encoded with quantum bits (or qubits) that can process more than two states: 1, 0 and superposition of these states. Thus, a quantum computer is not limited to linear processes and, consequently, can perform tasks beyond those of current computers. The existence of superposition states in the qubit provides a new dimension to the concept of computing. For instance, a quantum computer - in contrast to a classical computer - is capable of generating a real random bit. It is also clear that a quantum computer does not strictly follow binary logic. Not only can a quantum computer emulate classical logical gates, but it can possibly implement new logic gates. This expanded range of logic gates can be used to notably improve the information processing power during computing. Nevertheless, the most interesting feature of a quantum computer is quantum parallelism. Because of superposition states in qubits, a quantum processor can perform calculations using all possible input values simultaneously. So, with only one calculation, all the possible outputs can be computed. Because of this, a quantum computer has the potential to be 106 times more powerful than current supercomputers and, as a consequence, could simulate complex mechanical behaviors ranging from quantum systems to models describing the movements of electrons within crystals. Because of its potential economic and social impact, governments, universities, national research labs and industries worldwide are investing heavily in quantum computation research.

To realize the full potential of quantum computers, new algorithms must be designed that will exploit quantum parallelism fully. Such algorithms have already been expressed mathematically and are considerably more efficient than those used for digital computers. For example, Peter Shor of Bell Labs [1][2] has demonstrated the capacity of a quantum computer to quickly factor a large number, a very challenging problem for current supercomputers. With Shors' algorithm, a quantum computer can, in principle, factor a 1,000 digit number in about 20 minutes, whereas the same exercise on a current computer would take 1024 years. This is of great interest for cryptography since the codes used for encryption are based on the inability of today's computer to decipher encrypted information. Similarly, Lov Grover [3] has written an algorithm that will speed up any kind of database search, particularly for unsorted data. In order to find a specific item in an unsorted database of N entries, typically, N/2 queries on average are needed to find it, whereas Grover's algorithm, using quantum parallelism, requires only N1/2. Thus, the effect of the speedup is especially drastic as N becomes large.

Presently, the main obstacle to implementing a quantum computer is the degradation of superposition states with time (decoherence), which essentially leads to loss of stored information and causes a failure in the computation. In addition, the environment can interact with a qubit and cause collapse of the wave-function, destroying the quantum information stored in the superposition. To avoid decoherence, research has been directed mainly in two directions: a) Develop systems with minimal interaction or entanglement with the environment. (Trapped ions, Nuclear Magnetic Resonance (NMR), quantum dots, and cavity quantum electrodynamics (QED) are currently the main technologies being used to build quantum computers.); b) Develop algorithms for reducing errors due to decoherence. Shor and Steane [4][5] have shown that error-correcting routines - or quantum stabilizer codes - based on quantum logic, could effectively reduce decoherence and errors in a quantum computer.

Although quantum computers with seven qubits have already been built [6], many more qubits are necessary to simulate multidimensional and complex physical-chemical problems. However, recent advances give hope that quantum computers will emerge earlier than expected. Lately, Duke and Purdue university researchers [7] have managed to incorporate "quantum dots" (a small device containing free electrons inside a semiconductor) on a transistor. This new kind of transistor is not only very small, but also capable of quantum computing. Another great advancement has been made by Blinov et al. [8] at the University of Michigan with the observation of a "flying qubit". The information on the state of a single trapped ion was read by measuring the polarization of the photon that the ion emits spontaneously. This system could possibly be used as a communication link inside a quantum network. With current computers approaching physical performance limits, quantum computers promise a new and unprecedented level of computing power. Because of the limitations on speed and memory in current computers, it is impractical to calculate in any detail multivariable, multidimensional, highly non-linear problems such as arise in relation to, for example, turbulent fluid motions, the folding and unfolding of large protein molecules, and the molecular dynamics of chemically reacting systems. Even if quantum computing is still in its infancy, it very much heralds a new era in computing.

[1] Shor P., "Algorithms for quantum computation: discrete log and factoring", Proceedings of the 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM), pp. 124-134, 1994
[2] Shor P., "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", Society for Industrial and Applied Mathematics Journal on Computing, vol. 26, 5, pp. 1484-1509, 1997 (expanded version of [1])
[3] Grover L., "A fast quantum mechanical algorithm for database search", Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (Philadelphia, Pennsylvania), pp. 212-219, 1996
[4] P. Shor, "Scheme for reducing decoherence in computer memory", Physical Review, vol. A52, pp. R2493-R2496, 1995
[5] Steane A. M., "Error correcting codes in quantum theory", Physical Review Letters, vol. 78, pp. 2252, 1996
[6] Vandersypen L. M. K., Steffen M., Breyta G., Yannoni C. S., Sherwood M. H., Chuang I. L."Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance", Nature, vol. 414, pp. 883-887, 2001
[7] Chen J. C., Chang A. M., Melloch M.R., "Transition between Quantum States in a Parallel-Coupled Double Quantum Dot", Physical Review Letters, vol. 92, number 17, 2004
[8] Blinov B.B., Moehring D.L., Duan L.-M., Monroe C., "Observation of entanglement between a single trapped atom and a single photon", Nature, vol. 428, pp. 153-157, 2004



Comments and Suggestions to mechanics@soemail.rutgers.edu