dorsal/arxiv
View SchemaReversible Logic Circuit Synthesis
| Authors | Vivek V. Shende, Aditya K. Prasad, Igor L. Markov, John P. Hayes |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0207001 |
| URL | https://arxiv.org/abs/quant-ph/0207001 |
| Journal | V. V. Shende, A. K. Prasad, I. L. Markov and J. P. Hayes, ``Synthesis of Reversible Logic Circuits'', IEEE Trans. on CAD, vol 22(6), June 2003, pp. 710-722. |
Abstract
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. We study circuit decompositions of reversible circuits where gates of the same type are next to each other. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.
{
"annotation_id": "c77f27f5-04b9-42bf-843e-1853c2497a8e",
"date_created": "2026-03-02T18:01:52.922000Z",
"date_modified": "2026-03-02T18:01:52.922000Z",
"file_hash": "add30380788356741c1f5686aab68951d03a14a699c904edcbe199d12123b996",
"private": false,
"record": {
"abstract": "Reversible or information-lossless circuits have applications in digital\nsignal processing, communication, computer graphics and cryptography. They are\nalso a fundamental requirement in the emerging field of quantum computation. We\ninvestigate the synthesis of reversible circuits that employ a minimum number\nof gates and contain no redundant input-output line-pairs (temporary storage\nchannels). We prove constructively that every even permutation can be\nimplemented without temporary storage using NOT, CNOT and TOFFOLI gates. We\ndescribe an algorithm for the synthesis of optimal circuits and study the\nreversible functions on three wires, reporting distributions of circuit sizes.\nWe study circuit decompositions of reversible circuits where gates of the same\ntype are next to each other. Finally, in an application important to quantum\ncomputing, we synthesize oracle circuits for Grover\u0027s search algorithm, and\nshow a significant improvement over a previously proposed synthesis algorithm.",
"arxiv_id": "quant-ph/0207001",
"authors": [
"Vivek V. Shende",
"Aditya K. Prasad",
"Igor L. Markov",
"John P. Hayes"
],
"categories": [
"quant-ph"
],
"journal_ref": "V. V. Shende, A. K. Prasad, I. L. Markov and J. P. Hayes,\n ``Synthesis of Reversible Logic Circuits\u0027\u0027, IEEE Trans. on CAD, vol 22(6),\n June 2003, pp. 710-722.",
"title": "Reversible Logic Circuit Synthesis",
"url": "https://arxiv.org/abs/quant-ph/0207001"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "23a4c3b4-85c0-4c8f-9a07-447b7d6c6182",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}