quantum computer

▪ computer science

      device that employs properties described by quantum mechanics to enhance computations.

      As early as 1959 the American physicist and Nobel laureate Richard Feynman (Feynman, Richard P.) noted that, as electronic components begin to reach microscopic scales, effects predicted by quantum mechanics occur—which, he suggested, might be exploited in the design of more powerful computers. In particular, quantum researchers hope to harness a phenomenon known as superposition. In the quantum mechanical world, objects do not necessarily have clearly defined states, as demonstrated by the famous experiment in which a single photon of light passing through a screen with two small slits will produce a wavelike interference pattern, or superposition of all available paths. (See wave-particle duality.) However, when one slit is closed—or a detector is used to determine which slit the photon passed through—the interference pattern disappears. In consequence, a quantum system “exists” in all possible states before a measurement “collapses” the system into one state. Harnessing this phenomenon in a computer promises to expand computational power greatly. A traditional digital computer employs binary digits, or bits, that can be in one of two states, represented as 0 and 1; thus, for example, a 4-bit computer register can hold any one of 16 (2⁴) possible numbers. In contrast, a quantum bit (qubit) exists in a wavelike superposition of values from 0 to 1; thus, for example, a 4-qubit computer register can hold 16 different numbers simultaneously. In theory, a quantum computer can therefore operate on a great many values in parallel, so that a 30-qubit quantum computer would be comparable to a digital computer capable of performing 10 trillion floating-point operations per second (TFLOPS)—comparable to the speed of the fastest supercomputers.

      During the 1980s and '90s the theory of quantum computers advanced considerably beyond Feynman's early speculations. In 1985 David Deutsch of the University of Oxford described the construction of quantum logic gates for a universal quantum computer, and in 1994 Peter Shor of AT&T devised an algorithm to factor numbers with a quantum computer that would require as few as six qubits (although many more qubits would be necessary for factoring large numbers in a reasonable time). When a practical quantum computer is built, it will break current encryption schemes based on multiplying two large primes; in compensation, quantum mechanical effects offer a new method of secure communication known as quantum encryption. However, actually building a useful quantum computer has proved difficult. Although the potential of quantum computers is enormous, the requirements are equally stringent. A quantum computer must maintain coherence between its qubits (known as quantum entanglement) long enough to perform an algorithm; because of nearly inevitable interactions with the environment (decoherence), practical methods of detecting and correcting errors need to be devised; and, finally, since measuring a quantum system disturbs its state, reliable methods of extracting information must be developed.

      Plans for building quantum computers have been proposed; although several demonstrate the fundamental principles, none is beyond the experimental stage. Three of the most promising approaches are presented below: nuclear magnetic resonance (NMR), ion traps, and quantum dots.

      In 1998 Isaac Chuang of the Los Alamos National Laboratory, Neil Gershenfeld of the Massachusetts Institute of Technology (MIT), and Mark Kubinec of the University of California at Berkeley created the first quantum computer (2-qubit) that could be loaded with data and output a solution. Although their system was coherent for only a few nanoseconds and trivial from the perspective of solving meaningful problems, it demonstrated the principles of quantum computation. Rather than trying to isolate a few subatomic particles, they dissolved a large number of chloroform molecules (CHCL₃) in water at room temperature and applied a magnetic field to orient the spins of the carbon and hydrogen nuclei in the chloroform. (Because ordinary carbon has no magnetic spin, their solution used an isotope, carbon-13.) A spin parallel to the external magnetic field could then be interpreted as a 1 and an antiparallel spin as 0, and the hydrogen nuclei and carbon-13 nuclei could be treated collectively as a 2-qubit system. In addition to the external magnetic field, radio frequency pulses were applied to cause spin states to “flip,” thereby creating superimposed parallel and antiparallel states. Further pulses were applied to execute a simple algorithm and to examine the system's final state. This type of quantum computer can be extended by using molecules with more individually addressable nuclei. In fact, in March 2000 Emanuel Knill, Raymond Laflamme, and Rudy Martinez of Los Alamos and Ching-Hua Tseng of MIT announced that they had created a 7-qubit quantum computer using trans-crotonic acid. However, many researchers are skeptical about extending magnetic techniques much beyond 10 to 15 qubits because of diminishing coherence among the nuclei.

      Just one week before the announcement of a 7-qubit quantum computer, physicist David Wineland and colleagues at the U.S. National Institute for Standards and Technology (NIST) announced that they had created a 4-qubit quantum computer by entangling four ionized beryllium atoms using an electromagnetic “trap.” After confining the ions in a linear arrangement, a laser cooled the particles almost to absolute zero and synchronized their spin states. Finally, a laser was used to entangle the particles, creating a superposition of both spin-up and spin-down states simultaneously for all four ions. Again, this approach demonstrated basic principles of quantum computing, but scaling up the technique to practical dimensions remains problematic.

      Quantum computers based on semiconductor technology are yet another possibility. In a common approach a discrete number of free electrons (qubits) reside within extremely small regions, known as quantum dots, and in one of two spin states, interpreted as 0 and 1. Although prone to decoherence, such quantum computers build on well-established, solid-state techniques and offer the prospect of readily applying integrated circuit “scaling” technology. In addition, large ensembles of identical quantum dots could potentially be manufactured on a single silicon chip. The chip operates in an external magnetic field that controls electron spin states, while neighbouring electrons are weakly coupled (entangled) through quantum mechanical effects. An array of superimposed wire electrodes allows individual quantum dots to be addressed, algorithms executed, and results deduced. Such a system necessarily must be operated at temperatures near absolute zero to minimize environmental decoherence, but it has the potential to incorporate very large numbers of qubits.

William Coffeen Holton

Additional Reading

Julian Brown, Minds, Machines and the Multiverse: The Quest for the Quantum Computer (2000), is an accessible account of the history and basic science of quantum computers. Gerard J. Milburn, The Feynman Processor (1998), introduces the basic theory of quantum computing for the general reader. Colin P. Williams and Scott H. Clearwater, Explorations in Quantum Computing (1998), is a good introductory textbook, and Ultimate Zero and One: Computing at the Quantum Frontier (2000), is a popular exposition. David Deutsch, The Fabric of Reality (1997), explains quantum computing effects in terms of the many-world hypothesis—and treats the reader to a wide-ranging description of his “Theory of Everything.”Neil Gershenfeld and Isaac L. Chuang, “Quantum Computing with Molecules,” in Scientific American (June 1998), describes the authors' creation of the first quantum computer. Richard P. Feynman, “There's Plenty of Room at the Bottom,” in Richard P. Feynman, The Pleasure of Finding Things Out, ed. by Jeffrey Robbins (1999), pp. 117–139, contains the transcript of a talk given at an annual meeting of the American Physical Society on what has come to be known as nanotechnology. Richard P. Feynman, “Simulating Physics with Computers,” International Journal of Theoretical Physics, 21(6/7):467–488 (June 1982), discusses the inadequacy of conventional computers for simulating quantum mechanical objects. Peter W. Shor “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” in Shafi Goldwasser (ed.), Proceedings of the 35th Annual Symposium on Foundations of Computer Science (1994), pp. 124–134, is a worthwhile discussion.

* * *