ECCC-Report TR99-032https://eccc.weizmann.ac.il/report/1999/032Comments and Revisions published for TR99-032en-usTue, 07 Sep 1999 22:03:29 +0200
Paper TR99-032
| Quantum Circuits: Fanout, Parity, and Counting |
Cristopher Moore
https://eccc.weizmann.ac.il/report/1999/032We 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.
Tue, 07 Sep 1999 22:03:29 +0200https://eccc.weizmann.ac.il/report/1999/032