On the Complexity of Quantum ACC

Simple item page
dc.creatorGreen, F.
dc.creatorHomer, S.
dc.creatorPollett, C.
dc.date2000-02-21
dc.date2000-06-07
dc.date.accessioned2026-07-07T05:59:38Z
dc.date.available2026-07-07T05:59:38Z
dc.descriptionFor any $q > 1$, let $\MOD_q$ be a quantum gate that determines if the number of 1's in the input is divisible by $q$. We show that for any $q,t > 1$, $\MOD_q$ is equivalent to $\MOD_t$ (up to constant depth). Based on the case $q=2$, Moore \cite{moore99} has shown that quantum analogs of AC$^{(0)}$, ACC$[q]$, and ACC, denoted QAC$^{(0)}_{wf}$, QACC$[2]$, QACC respectively, define the same class of operators, leaving $q > 2$ as an open question. Our result resolves this question, proving that QAC$^{(0)}_{wf} =$ QACC$[q] = $ QACC for all $q$. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC and BQACC$_{\rats}$. We define a notion $\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)}$. To do this last proof, we show that TC$^{(0)}$ can perform iterated addition and multiplication in certain field extensions. We also introduce the notion of a polynomial-size tensor graph and show that families of such graphs can encode the amplitudes resulting from apply an arbitrary QACC operator to an initial state.
dc.description22 pages, 4 figures This version will appear in the July 2000 Computational Complexity conference. Section 4 has been significantly revised and many typos corrected
dc.identifierhttps://arxiv.org/abs/quant-ph/0002057
dc.identifierhttp://arxiv.org/abs/quant-ph/0002057
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/88755
dc.subjectQuantum Physics
dc.titleOn the Complexity of Quantum ACC
dc.typetext

Files

Collections

arXiv