__
TR99-032 | 7th July 1999 00:00
__

#### Quantum Circuits: Fanout, Parity, and Counting

**Abstract:**
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.