Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR99-032 | 7th July 1999 00:00

Quantum Circuits: Fanout, Parity, and Counting


Authors: Cristopher Moore
Publication: 7th September 1999 22:03
Downloads: 1358


We propose definitions of $\QAC^0$, the quantum analog of the
classical class $\AC^0$ of constant-depth circuits with AND and OR
gates of arbitrary fan-in, and $\QACC^0[q]$, the analog of the class
$\ACC^0[q]$ where $\Mod_q$ gates are also allowed. We show that it is
possible to make a `cat' state on $n$ qubits in constant depth if and
only if we can construct a parity or $\Mod_2$ gate in constant depth;
therefore, any circuit class that can fan out a qubit to $n$ copies in
constant depth also includes $\QACC^0[2]$. In addition, we prove the
somewhat surprising result that parity or fanout allows us to
construct $\Mod_q$ gates in constant depth for any $q$, so $\QACC^0[2]
= \QACC^0$. Since $\ACC^0[p] \ne \ACC^0[q]$ whenever $p$ and $q$ are
distinct primes, $\QACC^0[2]$ is strictly more powerful than its
classical counterpart, as is $\QAC^0$ when fanout is allowed.

ISSN 1433-8092 | Imprint