Copyright 2001 by Michael A. Nielsen. All rights reserved to the author. This document may be freely reproduced for non-commercial purposes only, provided the document is reproduced in full and without alteration, including this notice.

It's a commonplace to observe the tremendous pace of change in the computer industry. For many decades computers have doubled in power every year or so, and this trend looks set to continue for at least the next decade. Given this enormous rate of change, it is perhaps surprising to learn that all existing computers work according to essentially the same set of principles, a set of principles enunciated by the mathematician Alan Turing in 1936, and worked out in more detail by the mathematician John von Neumann in the 1940s. These principles define a paradigm for computation ("classical computation") that has persisted essentially unchanged in the decades since Turing and von Neumann, despite the enormous technical improvements that enable far more capable devices to be produced now than was possible in the first half of the twentieth century.

Quantum computers are different. They work according to quantum mechanical principles that transcend the notions of Turing and von Neumann. These principles expand the range of operations that a quantum computer can perform beyond what is possible on a classical computer, giving us a new and likely more powerful paradigm for computation. To understand how a quantum computer operates it helps to understand the three main differences between classical and quantum computation.

The first difference is in the fundamental units of information processed by the two types of computers. A classical computer is built up from bits - physical systems which can be in one of two states that we identify with "0" or "1". A quantum computer is built up from qubits, physical systems which possess states analogous to the classical 0 or 1, but which can also be in states intermediate between 0 and 1. These intermediate states, known as superposition states, in some sense allow a single qubit to store much more information than is possible in an ordinary classical bit.

The second difference between quantum and classical computers is in the range of logical operations that may be performed within the computer. Classical computers operate according to binary logic, using logical gates such as the AND gate which take two bits as input and produce a bit as output. Quantum logic gates take one or more qubits as input and produce one or more qubits as output. Qubits have states corresponding to the classical 0 and 1, so quantum logic gates have no difficulty emulating classical logic gates. However, the existence of superposition states intermediate between 0 and 1 greatly expands the possible range of quantum logic gates. We can, for example, have quantum logic gates that take as input 0 and 1 and produce as their corresponding outputs different superposition states intermediate between 0 and 1, a gate with no classical analogue. This expanded range of quantum logic gates can be exploited to achieve greater information processing power in quantum computers.

The third difference between quantum and classical computers is in the process of determining the state of the computer. In a classical computer we can read out the state of all the bits in the computer at any time. Rather strangely, in a quantum computer it is in principle impossible to determine the exact state of the computer. That is, we can't determine exactly which superposition state is being stored in the qubits making up the computer. Rather, we can only obtain partial information about the state of the computer. Designing algorithms for quantum computers is thus a delicate balance between exploiting the expanded range of states and logical operations afforded by quantum computation and the restricted readout of information possible in the computer.

What can quantum computers do? Unfortunately, at the moment we have a very incomplete picture of the capabilities of quantum computers, but a few interesting facts are known. In particular, there are a few problems that are believed (but not rigorously proved!) to be very difficult to solve on a classical computer that should be relatively easy to solve on a quantum computer - assuming we ever solve the hard problem of actually building such a device! Two interesting examples of such problems are the problem of finding the prime factors of large numbers, and the problem of simulating quantum mechanical systems. Both these problems are enormously important for a wide range of practical reasons, and they are believed to be very hard to solve on classical computers, but researchers have found theoretical algorithms for quantum computers that are vastly more efficient than the best known classical algorithms.

FURTHER READING

Reading is arranged roughly in increasing order of difficulty.

M. A. Nielsen, "Introduction to quantum information theory", available on the web at http://xxx.lanl.gov/abs/quant-ph/0011064.

E. Knill and M. A. Nielsen, "Theory of quantum computation", available on the web at http://xxx.lanl.gov/abs/quant-ph/0010057.

D. Aharonov, "Quantum computation", available on the web at http://xxx.lanl.gov/abs/quant-ph/9812037.

A. Steane, "Quantum computing", available on the web at http://xxx.lanl.gov/abs/quant-ph/9708022.

M. A. Nielsen and I. L. Chuang, "Quantum computation and quantum information", Cambridge University Press, Cambridge (2000). See also http://www.squint.org/qci for an excerpt from the first chapter and ordering information.