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.