Title: Bounds on the Power of Constant-Depth Quantum Circuits
Authors: S. Fenner, F. Green, S. Homer, Y. Zhang
Date: Jan 12, 2004
Abstract:
We show that if a language is recognized within certain error bounds
by constant-depth quantum circuits over a finite family of gates, then
it is computable in (classical) polynomial time. In particular, our
results imply EQNC^0 is contained in P, where EQNC^0 is the
constant-depth analog of the class EQP. On the other hand, we adapt
and extend ideas of Terhal and DiVincenzo (quant-ph/0205133) to show
that, for any family F of quantum gates including Hadamard and CNOT
gates, computing the acceptance probabilities of depth-five circuits
over F is just as hard as computing these probabilities for circuits
over F. In particular, this implies that NQNC^0 is hard for the
polynomial time hierarchy, where NQNC^0 is the constant-depth analog
of the class NQP. This essentially refutes a conjecture of Green et
al. that NQACC is contained in TC^0 (quant-ph/0106017).