| Prev: Reversible Computations | Up: Contents | Next: Factorisation Of Numbers |
The potential of quantum circuits is easy for all to see. It offers the promise of an exponential speed up over classical machines for a certain group of problems. The problems known to date to have fast quantum algorithms are listed below.
Researchers are currently looking in to the classes of algorithms of quantum computers. The computational class BPP is widely regarded as the class of efficiently solvable problems on a classical computer. The class BQP is the analogue for quantum computers. It is not known whether BPP º BQP, and indeed it is not possible to solve this conclusively without answering the major open problem P º PSPACE? There is some evidence though that BPP ¹ BQP [Bernstein and Varirani, 1993], and thus that quantum computers do offer a real speed up over their classical counterparts.
There have been proofs published [Bennet et al, 1996] which show that quantum computers cannot solve the class NP with more than a quadratic speed up over their classical counterparts. This is less than the exponential increase that we would desire, though it still offers dramatic increases in speed.
The possible advantages of quantum computers balanced the disadvantages in building the device. Remember that a measurement on a superpositioned value will lead to decoherence, and that the resultant universes after decoherence will never again interfere with each other. The output to a quantum circuit depends on quantum interference, thus performing a measurement on a quantum circuit will result in the output to the circuit being incorrect. What then is a measurement? We can simply think of a measurement as being an interaction of the superpositioned particle with some other particle. Thus a stray molecule colliding with the superposition particle or light shining on the particle could be enough to destroy the computation. This means that the creation of a quantum circuit consisting of many thousands of gates would be fiendishly difficult. The creation of just two quantum bits by Chris Monroe and his team from the National Institute of Standards and Technology involved the trapping of an ion in a magnetic field and then cooling it to near absolute zero.
Further problems stem from the fact that trying to copy a quantum bit would inherently involve a measurement of the bit. The copying of data is inherent in classical error correction systems, and it would seem that quantum computers would require error correction far more than classical computers ever would.
Yet there is hope. P. W. Shor recently invented an error correction mechanism that involves using an extra eight bits of redundant data for every bit in the circuit. Researchers at IBM, Los Alamos and Oxford then managed to reduce this down to an extra four bits. The error correcting mechanism works by encoding five qubits from a single input bit. If a measurement is later carried out on a single bit then this does not give away enough information to reveal the contents of the other four bits. The error can then be later corrected. The down side to this is of course that it requires the quantum circuit to consist of far more gates than before.
Hope also comes from Shor's work on the reliability of large quantum systems. Von Neuman in "Synthesis of Reliable Systems from Unreliable Parts" showed that one does not need components which are more reliable in order to run a longer classical computation - one just needs to slow the computation down to allow for error correction. Original detractors of computers had believed that to increase a computation length by x times one would require components which were x times more reliable. Shor has not managed to duplicate this result for quantum circuits, however he has managed to show that increasing the length of a quantum computation by x times requires a constant increase in the reliability of the components, not a factor of x.
Moore's Law states that microprocessors will double in the number of gates every eighteen months. Today, nearly thirty years later, this law is still holding strong. Yet even Moore himself believes that we will not be able to carry on at such a rate for another thirty years. In the future we will need to design a radically different technology if we are to continue growing our computer's performance at such an exponential rate. Perhaps quantum computation is the technology to achieve that goal.
Nobody really believes that we will have mass-produced quantum processors on our desktop any time soon. The physical difficulties of manufacturing a reliable large quantum device are far beyond are current technical expertise. But perhaps we should remind ourselves that the possibility of creating computer gates of 1 micron in size would have been described by many as physically impossible just fifty years ago, yet today one can stop off at a local computer store and casually buy a six million gate microprocessor with gates of just 0.35 microns in size for less than a hundred dollars. What once seemed impossible is now reality. Perhaps the techniques will be found to mass-produce quantum microprocessors within the next fifty years.
Even the detractors of quantum computation are willing to acknowledge one thing. The discussion and research in to this field has served to remind us that mathematics is not an abstract art. Instead it is firmly based in the reality of the Universe. The theories of quantum computers have served to remind us that computation is a physical process, bound by the laws of physics. Hence to achieve the maximum computational speed one must fully exploit the laws of nature.
| Prev: Reversible Computations | Up: Contents | Next: Factorisation Of Numbers |
This web page (c) 2000 Jon Marshall. Last updated 1st June 2000