Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR99-032 | 7th July 1999 00:00

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

TR99-032
Authors: Cristopher Moore
Publication: 7th September 1999 22:03
Keywords:

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.

ISSN 1433-8092 | Imprint