Since the publication of Shor's algorithm, research in all aspects of quantum computation and quantum information has become extremely active, and significant progress has been made by numerous research groups around the world. Further quantum algorithms with better performance than classical algorithms have been discovered, secure quantum communication protocols and quantum error-correcting codes have developed, and researchers have shown that quantum computers could be built using existing quantum technologies such as quantum optics and nuclear magnetic resonance (NMR), and they have constructed prototype quantum information-processing devices. At the time of writing, the most sophisticated such prototype uses seven spin-1/2 nuclei in a molecule as `quantum bits' (qubits) and manipulates them using room temperature liquid state NMR techniques. This device has been used to experimentally implement the simplest instance of Shor's algorithm, the factorization of the number 15 (whose prime factors are 3 and 5).
In a classical computer the basic unit of information is the bit, which is a two-state device that can represent the values 0 and 1. The quantum analogue of the bit is a two-state quantum system, such as an electron's spin or a photon's polarization, which has come to be known as a qubit. The difference between a qubit and a bit is that a qubit can exist not only in the states 0 and 1, but also in a mixture of both of them, called a superposition state. Furthermore, whereas a register of L bits can be in any one of 2L states, storing one of the numbers 0 to 2L-1, a register of L qubits can be in a superposition of all 2L states, storing all of the possible values simultaneously, and a function applied to a quantum register in a superposition state acts on all 2L values at the same time! This is known as quantum parallelism, and it is one of the key ingredients in the power of quantum computers, and the source of the exponential speedup exhibited by Shor's algorithm.
Unfortunately there is a catch that makes it non-trivial to exploit quantum parallelism, which is that when a quantum register in a superposition state is measured, the result obtained is only one of the 2L possible values, at random. However all is not lost, as the probabilities of measuring the different values do not have to be the same, and they can be manipulated by operating on a quantum register with quantum gates, which are the quantum analogue of logic gates. Quantum algorithms consist of sequences of quantum gate operations, optionally interspersed with measurements of some or all of the qubits in the quantum memory. It turns out that quantum algorithms exist that are able to exploit quantum parallelism, and to leave an output register in a superposition state where the probability of obtaining the value that is the answer to the problem is very close to one, thus giving an advantage over classical algorithms.
Not all quantum algorithms are able to provide such spectacular advantage over classical algorithms as Shor's algorithm. An important example is the algorithm for an unstructured database search that was published in 1996 by Lov Grover of Bell Labs. Imagine a phone directory containing N names arranged in completely random order. In order to find someone's phone number with a 50% probability, any classical algorithm would have to look at a minimum of N/2 names, but the number of steps needed by Grover's algorithm to obtain the desired phone number is only of order the square root of N. It has been proved that this algorithm is within a small constant factor of the fastest possible quantum mechanical algorithm to peform this task.
Last updated on
Feb 23 2006 at 22:49