Bounds on the Power of Constant-Depth Quantum Circuits
| dc.creator | Fenner, Stephen | |
| dc.creator | Green, Frederic | |
| dc.creator | Homer, Steven | |
| dc.creator | Zhang, Yong | |
| dc.date | 2003-12-28 | |
| dc.date | 2003-12-30 | |
| dc.date.accessioned | 2026-07-07T06:08:42Z | |
| dc.date.available | 2026-07-07T06:08:42Z | |
| dc.description | 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). | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0312209 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0312209 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/91721 | |
| dc.subject | Quantum Physics | |
| dc.title | Bounds on the Power of Constant-Depth Quantum Circuits | |
| dc.type | text |