Stephen Fenner, University of South Carolina
Classical circuit complexity has been a rich source of lower bounds over the last 30 years. For example, the PARITY function of n bits cannot be computed by Boolean circuits of constant depth and polynomial size. This and related results have had many applications in non-circuit-based classical complexity. It is natural to ask similar questions about quantum circuits: Can we prove lower bounds against small-depth quantum circuits, particularly, circuits with sub-logarithmic and even constant depth? Just how powerful are small-depth quantum circuits anyway? For a constant-depth quantum circuit to compute anything nontrivial, it must use some operations that involve several qubits at once. There have been many results over the last decade on the power of various "large" quantum gates, the most important being the FAN-OUT gate, which copies the classical value of a qubit to several other qubits.
In this talk, we will survey many these results and some of the techniques used to prove them. We will also describe a new-found connection between the FAN-OUT gate and the 1-way quantum computation model of Raussendorf and Briegel.
This talk covers work of Browne, Cleve, Fang, Green, Homer, Hoyer, Kashefi, Moore, Perdrix, Pollett, Spalek, Watrous, and Zhang as well as the speaker.