dorsal/arxiv
View SchemaAdaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
| Authors | Barbara M. Terhal, David P. DiVincenzo |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0205133 |
| URL | https://arxiv.org/abs/quant-ph/0205133 |
| Journal | Quant. Inf. Comp. Vol. 4 (No. 2), pages 134--145 (2004) |
Abstract
We present evidence that there exist quantum computations that can be carried out in constant depth, using 2-qubit gates, that cannot be simulated classically with high accuracy. We prove that if one can simulate these circuits classically efficiently then the complexity class BQP is contained in AM.
{
"annotation_id": "bdcbbe37-3bf7-419f-a97a-cb067c839acc",
"date_created": "2026-03-02T18:01:51.775000Z",
"date_modified": "2026-03-02T18:01:51.775000Z",
"file_hash": "ad06fc905f10e6eb2c7aae44b11f1503ce5649fc891da504c4dc4b0dc1253fc7",
"private": false,
"record": {
"abstract": "We present evidence that there exist quantum computations that can be carried\nout in constant depth, using 2-qubit gates, that cannot be simulated\nclassically with high accuracy. We prove that if one can simulate these\ncircuits classically efficiently then the complexity class BQP is contained in\nAM.",
"arxiv_id": "quant-ph/0205133",
"authors": [
"Barbara M. Terhal",
"David P. DiVincenzo"
],
"categories": [
"quant-ph",
"cs.CC"
],
"journal_ref": "Quant. Inf. Comp. Vol. 4 (No. 2), pages 134--145 (2004)",
"title": "Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games",
"url": "https://arxiv.org/abs/quant-ph/0205133"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "758653e1-1c18-4dec-a0b2-cf7e016f139b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}