Quantum Circuits with Unbounded Fan-out
<|reference_start|>Quantum Circuits with Unbounded Fan-out: 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 QNCf^0) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[q], 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, arithmetical operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.<|reference_end|>
@article{hoyer2002quantum,
    title={Quantum Circuits with Unbounded Fan-out},
    author={Peter Hoyer (U Calgary) and Robert Spalek (CWI)},
    journal={Theory of Computing, 1(5):81-103, 2005},
    year={2002},
    doi={10.4086/toc.2005.v001a005},
    archivePrefix={arXiv},
    eprint={quant-ph/0208043},
    primaryClass={quant-ph cs.CC}
}