dorsal/arxiv
View SchemaTechniques for the Synthesis of Reversible Toffoli Networks
| Authors | D. Maslov, D. M. Miller, G. W. Dueck |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0607166 |
| URL | https://arxiv.org/abs/quant-ph/0607166 |
| DOI | 10.1145/1278349.1278355 |
| Journal | ACM Transactions on Design Automation of Electronic Systems 12(4), Article 42, September 2007 |
Abstract
This paper presents novel techniques for the synthesis of reversible networks of Toffoli gates, as well as improvements to previous methods. Gate count and technology oriented cost metrics are used. Our synthesis techniques are independent of the cost metrics. Two new iterative synthesis procedure employing Reed-Muller spectra are introduced and shown to complement earlier synthesis approaches. The template simplification suggested in earlier work is enhanced through introduction of a faster and more efficient template application algorithm, updated (shorter) classification of the templates, and presentation of the new templates of sizes 7 and 9. A novel ``resynthesis'' approach is introduced wherein a sequence of gates is chosen from a network, and the reversible specification it realizes is resynthesized as an independent problem in hopes of reducing the network cost. Empirical results are presented to show that the methods are effective both in terms of the realization of all 3x3 reversible functions and larger reversible benchmark specifications.
{
"annotation_id": "89fd0f1b-add5-402c-9cca-7747f6203a39",
"date_created": "2026-03-02T18:02:27.558000Z",
"date_modified": "2026-03-02T18:02:27.558000Z",
"file_hash": "da2ce4fb1dd3f033768b5d6e0885b6da475160c623ae40d5c8343b8b9555b910",
"private": false,
"record": {
"abstract": "This paper presents novel techniques for the synthesis of reversible networks\nof Toffoli gates, as well as improvements to previous methods. Gate count and\ntechnology oriented cost metrics are used. Our synthesis techniques are\nindependent of the cost metrics. Two new iterative synthesis procedure\nemploying Reed-Muller spectra are introduced and shown to complement earlier\nsynthesis approaches. The template simplification suggested in earlier work is\nenhanced through introduction of a faster and more efficient template\napplication algorithm, updated (shorter) classification of the templates, and\npresentation of the new templates of sizes 7 and 9. A novel ``resynthesis\u0027\u0027\napproach is introduced wherein a sequence of gates is chosen from a network,\nand the reversible specification it realizes is resynthesized as an independent\nproblem in hopes of reducing the network cost. Empirical results are presented\nto show that the methods are effective both in terms of the realization of all\n3x3 reversible functions and larger reversible benchmark specifications.",
"arxiv_id": "quant-ph/0607166",
"authors": [
"D. Maslov",
"D. M. Miller",
"G. W. Dueck"
],
"categories": [
"quant-ph"
],
"doi": "10.1145/1278349.1278355",
"journal_ref": "ACM Transactions on Design Automation of Electronic Systems 12(4),\n Article 42, September 2007",
"title": "Techniques for the Synthesis of Reversible Toffoli Networks",
"url": "https://arxiv.org/abs/quant-ph/0607166"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b5a7e194-4047-4fc1-b44d-5d399a21f6e8",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}