Power of Small Quantum Circuits"
December 9, 2005
If quantum computational
circuits are ever built, they will be relatively
small and built from simple quantum gates. The
power and limits of resource-bound quantum circuits
is examined and compared to their classical
In particular it is shown
- several of the most interesting quantum algorithms
can be carried out using relatively small depth
and width quantum circuits. This includes, for
example, the efficient computation of the QFT.
- even constant-depth classical
circuits are stronger than their classical counterparts.
In particular such circuits can compute the
parity function, a function which cannot be
computed as efficiently classically.
- testing whether a constant
depth quantum circuit has non-zero acceptance
probability is a provably computationally difficult
problem. It is hard for the polynomial time