Counting, Fanout, and the Complexity of Quantum ACC

Details Counting, Fanout, and the Complexity of Quantum ACC Counting, Fanout, and the Complexity of Quantum ACC

2001-06-04

arxiv.org/abs/quant-ph/0106017v1

Physics

Quantum Physics

Scientific paper

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[q]$, the analog of the class $\ACC[q]$ where $\Mod_q$ gates are also allowed. We prove that parity or fanout allows us to construct quantum $\MOD_q$ gates in constant depth for any $q$, so $\QACC[2] = \QACC$. More generally, we show that for any $q,p > 1$, $\MOD_q$ is equivalent to $\MOD_p$ (up to constant depth). This implies that $\QAC^0$ with unbounded fanout gates, denoted $\QACwf^0$, is the same as $\QACC[q]$ and $\QACC$ for all $q$. Since $\ACC[p] \ne \ACC[q]$ whenever $p$ and $q$ are distinct primes, $\QACC[q]$ is strictly more powerful than its classical counterpart, as is $\QAC^0$ when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts. We also develop techniques for proving upper bounds for $\QACC^0$ in terms of related language classes. We define classes of languages $\EQACC$, $\NQACC$ and $\BQACC_{\rats}$. We define a notion of $\log$-planar $\QACC$ operators and show the appropriately restricted versions of $\EQACC$ and $\NQACC$ are contained in $\P/\poly$. We also define a notion of $\log$-gate restricted $\QACC$ operators and show the appropriately restricted versions of $\EQACC$ and $\NQACC$ are contained in $\TC^0$.

Affiliated with

Also associated with

No associations

Rating

Counting, Fanout, and the Complexity of Quantum ACC does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting, Fanout, and the Complexity of Quantum ACC, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting, Fanout, and the Complexity of Quantum ACC will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-406537