Volume 1 (2005) Article 5 pp. 81-103

Quantum Fan-out is Powerful

by Peter Høyer and Robert Špalek

Received: October 26, 2004
Published: August 3, 2005
DOI: 10.4086/toc.2005.v001a005

Download article from ToC site:
[PS (1189K)]    [PS.GZ (459K)]    [PS.ZIP (459K)]
[PDF (305K)]    [DVI (193K)]    [ZIP (245K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: quantum computing, quantum circuits, fan-out, quantum Fourier transform, constant depth circuits, threshold circuits
Categories: quantum, Fourier transform, circuits, circuit complexity, complexity theory
ACM Classification: F.2.1, F.2.2
AMS Classification: 68Q15, 81P68

Abstract: [Plain Text Version]

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 QNCwf0) 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.