dorsal/arxiv
View SchemaBounds on the Power of Constant-Depth Quantum Circuits
| Authors | Stephen Fenner, Frederic Green, Steven Homer, Yong Zhang |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0312209 |
| URL | https://arxiv.org/abs/quant-ph/0312209 |
Abstract
We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomial time. In particular, our results imply EQNC^0 is contained in P, where EQNC^0 is the constant-depth analog of the class EQP. On the other hand, we adapt and extend ideas of Terhal and DiVincenzo (quant-ph/0205133) to show that, for any family F of quantum gates including Hadamard and CNOT gates, computing the acceptance probabilities of depth-five circuits over F is just as hard as computing these probabilities for circuits over F. In particular, this implies that NQNC^0 = NQACC = NQP = coC=P where NQNC^0 is the constant-depth analog of the class NQP. This essentially refutes a conjecture of Green et al. that NQACC is contained in TC^0 (quant-ph/0106017).
{
"annotation_id": "30cccb31-780e-4655-b78f-9027034caad1",
"date_created": "2026-03-02T18:02:03.603000Z",
"date_modified": "2026-03-02T18:02:03.603000Z",
"file_hash": "7cd744500730baeb0a50920c078b5513be700754a870bfa8c23cbbc7bc5a28a8",
"private": false,
"record": {
"abstract": "We show that if a language is recognized within certain error bounds by\nconstant-depth quantum circuits over a finite family of gates, then it is\ncomputable in (classical) polynomial time. In particular, our results imply\nEQNC^0 is contained in P, where EQNC^0 is the constant-depth analog of the\nclass EQP. On the other hand, we adapt and extend ideas of Terhal and\nDiVincenzo (quant-ph/0205133) to show that, for any family F of quantum gates\nincluding Hadamard and CNOT gates, computing the acceptance probabilities of\ndepth-five circuits over F is just as hard as computing these probabilities for\ncircuits over F. In particular, this implies that NQNC^0 = NQACC = NQP = coC=P\nwhere NQNC^0 is the constant-depth analog of the class NQP. This essentially\nrefutes a conjecture of Green et al. that NQACC is contained in TC^0\n(quant-ph/0106017).",
"arxiv_id": "quant-ph/0312209",
"authors": [
"Stephen Fenner",
"Frederic Green",
"Steven Homer",
"Yong Zhang"
],
"categories": [
"quant-ph"
],
"title": "Bounds on the Power of Constant-Depth Quantum Circuits",
"url": "https://arxiv.org/abs/quant-ph/0312209"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "bb318ced-0c74-4e67-995e-0529547599bf",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}