Theory of Computing
-------------------
Title     : Quantum Fan-out is Powerful
Authors   : Peter Hoyer and Robert Spalek
Volume    : 1
Number    : 5
Pages     : 81-103
URL       : http://www.theoryofcomputing.org/articles/v001a005

Abstract
--------
We demonstrate that the unbounded fan-out gate is very powerful.
Constant-depth polynomial-size quantum circuits with bounded fan-in and
unbounded fan-out over a fixed basis (denoted by $\QNCwf^0$) can approximate
with polynomially small error the following gates: parity, mod[q], And,
Or, majority, threshold[t], exact[t], and Counting.  Classically, we need
logarithmic depth even if we can use unbounded fan-in gates.  If we allow
arbitrary one-qubit gates instead of a fixed basis, then these circuits can
also be made exact in log-star depth.  Sorting, arithmetic operations, phase
estimation, and the quantum Fourier transform with arbitrary moduli can also
be approximated in constant depth.