dorsal/arxiv
View SchemaQuantum Circuits: Fanout, Parity, and Counting
| Authors | Cristopher Moore |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9903046 |
| URL | https://arxiv.org/abs/quant-ph/9903046 |
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^0[q], where n-ary 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] != ACC^0[q] whenever p and q are mutually prime, QACC^0[2] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed.
{
"annotation_id": "a5399b6b-7ae5-4eb8-8806-b9240c589717",
"date_created": "2026-03-02T18:02:45.191000Z",
"date_modified": "2026-03-02T18:02:45.191000Z",
"file_hash": "63f4ba06ba1fb556e7c7de37c6eef4b9d54259db409cddddfc18215832c9a5d4",
"private": false,
"record": {
"abstract": "We propose definitions of QAC^0, the quantum analog of the classical class\nAC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and\nQACC^0[q], where n-ary Mod-q gates are also allowed. We show that it is\npossible to make a `cat\u0027 state on n qubits in constant depth if and only if we\ncan construct a parity or Mod-2 gate in constant depth; therefore, any circuit\nclass that can fan out a qubit to n copies in constant depth also includes\nQACC^0[2]. In addition, we prove the somewhat surprising result that parity or\nfanout allows us to construct Mod-q gates in constant depth for any q, so\nQACC^0[2] = QACC^0. Since ACC^0[p] != ACC^0[q] whenever p and q are mutually\nprime, QACC^0[2] is strictly more powerful than its classical counterpart, as\nis QAC^0 when fanout is allowed.",
"arxiv_id": "quant-ph/9903046",
"authors": [
"Cristopher Moore"
],
"categories": [
"quant-ph"
],
"title": "Quantum Circuits: Fanout, Parity, and Counting",
"url": "https://arxiv.org/abs/quant-ph/9903046"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "7f74543e-905c-442d-a576-0572f3569fb0",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}