dorsal/arxiv
View SchemaSome Notes on Parallel Quantum Computation
| Authors | Cristopher Moore, Martin Nilsson |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9804034 |
| URL | https://arxiv.org/abs/quant-ph/9804034 |
Abstract
We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates can be parallelized to logarithmic depth, while circuits composed of both cannot. Finally, while we note the Quantum Fourier Transform can be parallelized to linear depth, we exhibit a simple quantum circuit related to it that we believe cannot be parallelized to less than linear depth, and therefore might be used to prove that QNC < QP.
{
"annotation_id": "b3c8b29f-78ae-48a2-a8f4-cb6c5d7fbf6d",
"date_created": "2026-03-02T18:02:40.724000Z",
"date_modified": "2026-03-02T18:02:40.724000Z",
"file_hash": "4194ac5a15fdeb4484682a3721cd4b8b4204bea3af8c2182a5aab1806dd483f6",
"private": false,
"record": {
"abstract": "We exhibit some simple gadgets useful in designing shallow parallel circuits\nfor quantum algorithms. We prove that any quantum circuit composed entirely of\ncontrolled-not gates or of diagonal gates can be parallelized to logarithmic\ndepth, while circuits composed of both cannot. Finally, while we note the\nQuantum Fourier Transform can be parallelized to linear depth, we exhibit a\nsimple quantum circuit related to it that we believe cannot be parallelized to\nless than linear depth, and therefore might be used to prove that QNC \u003c QP.",
"arxiv_id": "quant-ph/9804034",
"authors": [
"Cristopher Moore",
"Martin Nilsson"
],
"categories": [
"quant-ph"
],
"title": "Some Notes on Parallel Quantum Computation",
"url": "https://arxiv.org/abs/quant-ph/9804034"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d9f45438-7cd5-4404-b5d7-dd0c62eabc0c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}