Title: Small Depth Quantum Circuits

Author: Debajyoti Bera, Frederic Green, Steven Homer,

Date: May 24, 2007

Abstract:

Quantum circuits are a general and universal formulation of quantum
computation, and small quantum circuits are likely to be the model for
the first implementations of quantum computing.  Although the quantum
circuit model is quite different than the classical one, it has
nonetheless proven to be quite fruitful to look to classical circuit
models for insight and comparison.  Furthermore, very small (i.e.,
constant) depth classical circuits present us with computational
models for which we can prove interesting lower bounds. In this survey
we explore the computational power and limits of small depth quantum
circuits. We prove that several quantum circuit classes are
unexpectedly powerful and can perform computations strictly stronger
than their classical counterparts. We exhibit lower bounds for the
circuit depth of quantum circuits which compute parity or fanout.