Abstract

As early as 1982 Richard P. Feynman suggested that it might be impossible to simulate quantum mechanical phenomena with a computer without an exponential slowdown in the efficiency of computation. He also proposed that this problem may be avoided by allowing the computer to run according to the laws of quantum mechanics, thus implicitely suggesting that a computer based on the quantum mechanical systems, a quantum computer, might have exponentially more computational efficiency than any classical one.

A quantum mechanical phenomenon that never occurs in classical physics and which actually makes quantum computation interesting and powerful, is the superposition of states, which, loosely speaking, means that instead of being totally in one single state, a particle can be "in between many states". Compare this to the elements of classical computer, bits. A bit takes values zero or one, but never anything between. In a quantum computer, one is able to store it both values simultaneously in one quantum bit, equally weighted or not. Moreover, in the classical computer one can store a number from zero to $2^n-1$ in a register of length $n$, whereas, in quantum computation, all the values could be stored simultaneously. The computation, which is performed via unitary transformations in the state vector space, then applies to all these values simultaneously. Thus the power of the quantum computation lies not in the absolute speed of the hypothetetical quantum computer but in the possibility to actually follow many computational path simultaneously, as a nondeterministic automaton does. Alas, the observation of the outcome will yield only one value destroying the rest irreversibly. However, using a procedure smart enough one could obtain some valuable information about the computation.

Keywords: Quantum computation, Unitary mapping, Superposition, Turing machine, Reversible computation, Computational complexity, Factoring

Full paper in PostScript format (1261 Kb) and in compressed PostScript format (315 Kb).