dorsal/arxiv
View SchemaOn the Complexity of Quantum ACC
| Authors | F. Green, S. Homer, C. Pollett |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0002057 |
| URL | https://arxiv.org/abs/quant-ph/0002057 |
Abstract
For 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.
{
"annotation_id": "68065a54-cc1a-491a-9da1-6a3d9ff87e64",
"date_created": "2026-03-02T18:01:37.958000Z",
"date_modified": "2026-03-02T18:01:37.958000Z",
"file_hash": "1d0c500001c86bfaf5050928a01635539800ce0746cc09deefcfd4f401eedaba",
"private": false,
"record": {
"abstract": "For any $q \u003e 1$, let $\\MOD_q$ be a quantum gate that determines if the number\nof 1\u0027s in the input is divisible by $q$. We show that for any $q,t \u003e 1$,\n$\\MOD_q$ is equivalent to $\\MOD_t$ (up to constant depth). Based on the case\n$q=2$, Moore \\cite{moore99} has shown that quantum analogs of AC$^{(0)}$,\nACC$[q]$, and ACC, denoted QAC$^{(0)}_{wf}$, QACC$[2]$, QACC respectively,\ndefine the same class of operators, leaving $q \u003e 2$ as an open question. Our\nresult resolves this question, proving that QAC$^{(0)}_{wf} =$ QACC$[q] = $\nQACC for all $q$. We also develop techniques for proving upper bounds for QACC\nin terms of related language classes. We define classes of languages EQACC,\nNQACC and BQACC$_{\\rats}$. We define a notion $\\log$-planar QACC operators and\nshow the appropriately restricted versions of EQACC and NQACC are contained in\nP/poly. We also define a notion of $\\log$-gate restricted QACC operators and\nshow the appropriately restricted versions of EQACC and NQACC are contained in\nTC$^{(0)}$. To do this last proof, we show that TC$^{(0)}$ can perform iterated\naddition and multiplication in certain field extensions. We also introduce the\nnotion of a polynomial-size tensor graph and show that families of such graphs\ncan encode the amplitudes resulting from apply an arbitrary QACC operator to an\ninitial state.",
"arxiv_id": "quant-ph/0002057",
"authors": [
"F. Green",
"S. Homer",
"C. Pollett"
],
"categories": [
"quant-ph"
],
"title": "On the Complexity of Quantum ACC",
"url": "https://arxiv.org/abs/quant-ph/0002057"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c6e44800-0355-4c45-9455-d4787a397c61",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}