QUANTUM COMPUTING:
The Advantages of Superposition
Lov K. Grover
If a computer could be built from quantum elements, which can exist in superpositions of many states rather than the 1s and 0s of conventional binary logic, then important hard problems could be solved rapidly. One example is the prime number factorization problem at the heart of modern encryption: Given the product of two large primes, find the primes themselves. Another important problem is exhaustive search: Given an unstructured list of items, quickly find the one that satisfies a certain property. A pair of Research Commentaries in this issue discuss some important new results in which simple quantum computers have been constructed with liquids probed by nuclear magnetic resonance techniques. The first, by L. K. Grover of Bell Labs, describes the theoretical situation and the implementation of an algorithm that he designed for exhaustive search. The second, by J. A. Jones of Oxford University, UK, discusses the recent experimental approaches to quantum computing with nuclear magnetic resonance.
The author is at Bell Labs, Lucent Technologies, Murray Hill, NJ 07974, USA. E-mail: lkgrover{at}bell-labs.com
