Quantum Fanout is Powerful

Abstract

We demonstrate that the unbounded fan-out gate is very powerful.Constantdepth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNC 0 f ) 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.