Fang, M.; Fenner, S.; Green, F.; Homer, S.; Zhang, Y.
(Boston University Computer Science Department, 2004-01-12)
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 ...