Quantum Lower Bounds for Fanout
Date
2004-01-12
DOI
Authors
Fang, M.
Fenner, S.
Green, F.
Homer, S.
Zhang, Y.
Version
OA Version
Citation
Abstract
We prove several new lower bounds for constant depth quantum circuits. The main result is that parity (and hence fanout) requires log depth circuits, when the circuits are composed of single qubit and arbitrary size Toffoli gates, and when they use only constantly many ancillae. Under this constraint, this bound is close to optimal. In the case of a non-constant number of ancillae, we give a tradeoff between the number of ancillae and the required depth.