dorsal/arxiv
View SchemaEfficient Synthesis of Linear Reversible Circuits
| Authors | K. N. Patel, I. L. Markov, J. P. Hayes |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0302002 |
| URL | https://arxiv.org/abs/quant-ph/0302002 |
| Journal | Quantum Information and Computation, vol. 8, no. 3-4, pp. 282-294, 2008 |
Abstract
In this paper we consider circuit synthesis for n-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with O(n^2) gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as O(n^2/log n) gates. We present an algorithm that is optimal up to a multiplicative constant, as well as Theta(log n) times faster than previous methods. While our results are primarily asymptotic, simulation results show that even for relatively small n our algorithm is faster and yields more efficient circuits than the standard method. Generically our algorithm can be interpreted as a matrix decomposition algorithm, yielding an asymptotically efficient decomposition of a binary matrix into a product of elementary matrices.
{
"annotation_id": "fc65c4d5-10c5-4f52-bd63-0d42332ca1b6",
"date_created": "2026-03-02T18:01:55.998000Z",
"date_modified": "2026-03-02T18:01:55.998000Z",
"file_hash": "24ffa3b61325f898fedbca31cb39ff50156123cf2da1c3e7d0b92acc28af600a",
"private": false,
"record": {
"abstract": "In this paper we consider circuit synthesis for n-wire linear reversible\ncircuits using the C-NOT gate library. These circuits are an important class of\nreversible circuits with applications to quantum computation. Previous\nalgorithms, based on Gaussian elimination and LU-decomposition, yield circuits\nwith O(n^2) gates in the worst-case. However, an information theoretic bound\nsuggests that it may be possible to reduce this to as few as O(n^2/log n)\ngates.\n We present an algorithm that is optimal up to a multiplicative constant, as\nwell as Theta(log n) times faster than previous methods. While our results are\nprimarily asymptotic, simulation results show that even for relatively small n\nour algorithm is faster and yields more efficient circuits than the standard\nmethod. Generically our algorithm can be interpreted as a matrix decomposition\nalgorithm, yielding an asymptotically efficient decomposition of a binary\nmatrix into a product of elementary matrices.",
"arxiv_id": "quant-ph/0302002",
"authors": [
"K. N. Patel",
"I. L. Markov",
"J. P. Hayes"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quantum Information and Computation, vol. 8, no. 3-4, pp. 282-294,\n 2008",
"title": "Efficient Synthesis of Linear Reversible Circuits",
"url": "https://arxiv.org/abs/quant-ph/0302002"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "ef01e384-f7a4-4a58-8bc8-d2dee32a3487",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}