dorsal/arxiv
View SchemaCounting, Fanout, and the Complexity of Quantum ACC
| Authors | Frederic Green, Steven Homer, Cristopher Moore, Christopher Pollett |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0106017 |
| URL | https://arxiv.org/abs/quant-ph/0106017 |
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[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$.
{
"annotation_id": "9e21ae8f-b439-494c-858a-5c96306f71e1",
"date_created": "2026-03-02T18:01:45.516000Z",
"date_modified": "2026-03-02T18:01:45.516000Z",
"file_hash": "72ee00758f411c2c242be2ae4752f3b4ca4fb6e2c5acb6606a4b110b0b070bd9",
"private": false,
"record": {
"abstract": "We propose definitions of $\\QAC^0$, the quantum analog of the classical class\n$\\AC^0$ of constant-depth circuits with AND and OR gates of arbitrary fan-in,\nand $\\QACC[q]$, the analog of the class $\\ACC[q]$ where $\\Mod_q$ gates are also\nallowed. We prove that parity or fanout allows us to construct quantum $\\MOD_q$\ngates in constant depth for any $q$, so $\\QACC[2] = \\QACC$. More generally, we\nshow that for any $q,p \u003e 1$, $\\MOD_q$ is equivalent to $\\MOD_p$ (up to constant\ndepth). This implies that $\\QAC^0$ with unbounded fanout gates, denoted\n$\\QACwf^0$, is the same as $\\QACC[q]$ and $\\QACC$ for all $q$. Since $\\ACC[p]\n\\ne \\ACC[q]$ whenever $p$ and $q$ are distinct primes, $\\QACC[q]$ is strictly\nmore powerful than its classical counterpart, as is $\\QAC^0$ when fanout is\nallowed. This adds to the growing list of quantum complexity classes which are\nprovably more powerful than their classical counterparts.\n We also develop techniques for proving upper bounds for $\\QACC^0$ in terms of\nrelated language classes. We define classes of languages $\\EQACC$, $\\NQACC$ and\n$\\BQACC_{\\rats}$. We define a notion of $\\log$-planar $\\QACC$ operators and\nshow the appropriately restricted versions of $\\EQACC$ and $\\NQACC$ are\ncontained in $\\P/\\poly$. We also define a notion of $\\log$-gate restricted\n$\\QACC$ operators and show the appropriately restricted versions of $\\EQACC$\nand $\\NQACC$ are contained in $\\TC^0$.",
"arxiv_id": "quant-ph/0106017",
"authors": [
"Frederic Green",
"Steven Homer",
"Cristopher Moore",
"Christopher Pollett"
],
"categories": [
"quant-ph"
],
"title": "Counting, Fanout, and the Complexity of Quantum ACC",
"url": "https://arxiv.org/abs/quant-ph/0106017"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "45ed63fb-bf27-4e3d-bfb4-16b1d6b7a330",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}