A major impetus for the
recent activity in quantum computation is a
small number of quantum algorithms, which have
been developed, that (in principle) exhibit
an advantage of quantum computation over classical
computation. These examples raise questions
concerning the power and limits of quantum computation.
One aspect of this topic is the development
of the general theory of efficient quantum |

The two standard models
for quantum computing, quantum Turing machines
and quantum circuits, will be considered. We
show how efficient computations using these
models can be related computations of standard
(probabilistic) Turing machines. Using this
correspondence, we consider natural classes
of quantum algorithms and discuss their efficiency.
We do this by providing a classification for
quantum algorithms and measuring the efficiency
of these algorithms using traditional complexity
measures. |