dorsal/arxiv
View SchemaSynthesis of Quantum Logic Circuits
| Authors | Vivek V. Shende, Stephen S. Bullock, Igor L. Markov |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0406176 |
| URL | https://arxiv.org/abs/quant-ph/0406176 |
| DOI | 10.1109/TCAD.2005.855930 |
| Journal | IEEE Trans. on Computer-Aided Design, vol. 25, no. 6, June 2006, pp.1000 - 1010 |
Abstract
We discuss efficient quantum logic circuits which perform two tasks: (i) implementing generic quantum computations and (ii) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state-space of an n-qubit register is not finite and contains exponential superpositions of classical bit strings. Our proposed circuits are asymptotically optimal for respective tasks and improve published results by at least a factor of two. The circuits for generic quantum computation constructed by our algorithms are the most efficient known today in terms of the number of expensive gates (quantum controlled-NOTs). They are based on an analogue of the Shannon decomposition of Boolean functions and a new circuit block, quantum multiplexor, that generalizes several known constructions. A theoretical lower bound implies that our circuits cannot be improved by more than a factor of two. We additionally show how to accommodate the severe architectural limitation of using only nearest-neighbor gates that is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.
{
"annotation_id": "52885dfa-bc56-4d42-b37c-7a5372f8378d",
"date_created": "2026-03-02T18:02:09.062000Z",
"date_modified": "2026-03-02T18:02:09.062000Z",
"file_hash": "df94039456dbd90a7c3dca0ad5f1226ad3f4bec88a12264bc867415aa64cc6fc",
"private": false,
"record": {
"abstract": "We discuss efficient quantum logic circuits which perform two tasks: (i)\nimplementing generic quantum computations and (ii) initializing quantum\nregisters. In contrast to conventional computing, the latter task is nontrivial\nbecause the state-space of an n-qubit register is not finite and contains\nexponential superpositions of classical bit strings. Our proposed circuits are\nasymptotically optimal for respective tasks and improve published results by at\nleast a factor of two.\n The circuits for generic quantum computation constructed by our algorithms\nare the most efficient known today in terms of the number of expensive gates\n(quantum controlled-NOTs). They are based on an analogue of the Shannon\ndecomposition of Boolean functions and a new circuit block, quantum\nmultiplexor, that generalizes several known constructions. A theoretical lower\nbound implies that our circuits cannot be improved by more than a factor of\ntwo. We additionally show how to accommodate the severe architectural\nlimitation of using only nearest-neighbor gates that is representative of\ncurrent implementation technologies. This increases the number of gates by\nalmost an order of magnitude, but preserves the asymptotic optimality of gate\ncounts.",
"arxiv_id": "quant-ph/0406176",
"authors": [
"Vivek V. Shende",
"Stephen S. Bullock",
"Igor L. Markov"
],
"categories": [
"quant-ph"
],
"doi": "10.1109/TCAD.2005.855930",
"journal_ref": "IEEE Trans. on Computer-Aided Design, vol. 25, no. 6, June 2006,\n pp.1000 - 1010",
"title": "Synthesis of Quantum Logic Circuits",
"url": "https://arxiv.org/abs/quant-ph/0406176"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "542e3663-4795-44fc-8239-5c7f3012cff1",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}