Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1105.5831

Reducing Quantum Cost in Reversible Toffoli Circuits

Marek Szyprowski, Paweł Kerntopf

Published May 29, 2011• 29 citations
arXivHTMLPDF

Abstract

Recently, reversible circuit synthesis has been intensively studied. One of the problems that has not been solved for a long time was exact minimization of gate count (GC) in 4-bit circuits. Finally, last year a tool of practical usage for finding optimal gate count Toffoli networks for any 4-variable function was developed. However, not much work has been done yet on exact minimization of quantum cost (QC) in 4-bit circuits. This paper presents an application of the above mentioned tool to reducing QC of 4-bit reversible circuits. It is shown that for benchmarks and for designs taken from recent publications it is possible to obtain savings in QC of up to 74% comparing with previously known circuits.

DOI
10.48550/arxiv.1105.5831

Related papers

A study of optimal 4-bit reversible circuit synthesis from mixed-polarity Toffoli gates

Marek Szyprowski, Paweł Kerntopf

Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (i.e. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Aug 1, 2012•9 citations

A Study of Optimal 4-bit Reversible Circuit Synthesis from Mixed-Polarity

Toffoli Gates, Marek Szyprowski, Pawel Kerntopfi

Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (Le. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.

•Jan 1, 2012•0 citations

A Synthesis Algorithm for 4-Bit Reversible Logic Circuits with Minimum Quantum Cost

Zhiqiang Li, Hanwu Chen, Xiaoyu Song B +1 more

This article presents an algorithm which can quickly find the exact minimum solution to almost all of 4-bit reversible functions. We assume minimization of quantum cost (MQC). This algorithm is designed in the most memory-efficient way, or it will quickly run out of memory. Therefore, we construct the shortest coding of permutations, the topological compression and flexible data structures for the memory savings. First, hash tables are used for all 8-gate 4-bit circuits with the minimization of gate count (MGC) by using the GT library (with NOT, CNOT, Toffoli and Toffoli-4 gates). Second, we merge and split the hash tables, thus generating a single longer hash table for high-performance. Third, we synthesize these circuits with MQC by using the GTP library (with GT, Peres, and Inverted Peres gates) based on the hash table. Finally, according to the comparison of the QC of circuits, the algorithm can quickly converge for any 4-bit reversible circuit with MQC. By synthesizing all benchmark functions, in comparison with Szyprowski and Kerntopf [2011], the running time and QC are reduced up to 99.95% and 18.2%, respectively.

ACM Journal on Emerging Technologies in Computing Systems•Dec 30, 2014•3 citations

An approach to quantum cost optimization in reversible circuits

Marek Szyprowski, Paweł Kerntopf

Recently, one of the main criteria used to evaluate reversible circuit designs is quantum cost. In this paper, an approach to reducing quantum cost of small-width reversible circuits is presented. Using our tool we have shown that for known benchmarks as well as designs taken from recent publications it is possible to obtain substantial savings in quantum cost (35% on average for 4-input benchmarks). It is also shown that quantum cost of 5-input circuits can be reduced using the same tool.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Aug 1, 2011•18 citations

A Quantum Cost 9 Reversible Full Adder with Single-Toffoli Complexity

GEORGE PAPAKONSTANTINOU

The minimization of Quantum Cost (QC), specifically the number of Toffoli gates, is a primary objective in the synthesis of reversible arithmetic circuits. For decades, the Peres Full Adder has been considered the benchmark for minimal realizations, requiring 2 Toffoli gates and a Quantum Cost of 12. In this note, we propose a novel reversible Full Adder circuit that utilizes only one Toffoli gate and four CNOT gates. The proposed design achieves a Quantum Cost of 9, representing a 25% reduction compared to the Peres structure, while maintaining a competitive logical depth of 4. We rigorously verify the logic and demonstrate that the reduction is achieved through the automated synthesis framework recently proposed by the authors.

•Jan 27, 2026•1 citation

SAT-based Exact Synthesis of Ternary Reversible Circuits using a Functionally Complete Gate Library

Abhoy Kole, Kamalika Datta, Indranil Sengupta +1 more

The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.

Euromicro Conference on Digital System Design (DSD)•Aug 1, 2022•1 citation
Recently, reversible circuit synthesis has been intensively studied. One of the problems that has not been solved for a long time was exact minimization of gate count (GC) in 4-bit circuits. Finally, last year a tool of practical usage for finding optimal gate count Toffoli networks for any 4-variable function was developed. However, not much work has been done yet on exact minimization of quantum cost (QC) in 4-bit circuits. This paper presents an application of the above mentioned tool to reducing QC of 4-bit reversible circuits. It is shown that for benchmarks and for designs taken from recent publications it is possible to obtain savings in QC of up to 74% comparing with previously known circuits.
Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (i.e. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.
Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (Le. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.
This article presents an algorithm which can quickly find the exact minimum solution to almost all of 4-bit reversible functions. We assume minimization of quantum cost (MQC). This algorithm is designed in the most memory-efficient way, or it will quickly run out of memory. Therefore, we construct the shortest coding of permutations, the topological compression and flexible data structures for the memory savings. First, hash tables are used for all 8-gate 4-bit circuits with the minimization of gate count (MGC) by using the GT library (with NOT, CNOT, Toffoli and Toffoli-4 gates). Second, we merge and split the hash tables, thus generating a single longer hash table for high-performance. Third, we synthesize these circuits with MQC by using the GTP library (with GT, Peres, and Inverted Peres gates) based on the hash table. Finally, according to the comparison of the QC of circuits, the algorithm can quickly converge for any 4-bit reversible circuit with MQC. By synthesizing all benchmark functions, in comparison with Szyprowski and Kerntopf [2011], the running time and QC are reduced up to 99.95% and 18.2%, respectively.
The minimization of Quantum Cost (QC), specifically the number of Toffoli gates, is a primary objective in the synthesis of reversible arithmetic circuits. For decades, the Peres Full Adder has been considered the benchmark for minimal realizations, requiring 2 Toffoli gates and a Quantum Cost of 12. In this note, we propose a novel reversible Full Adder circuit that utilizes only one Toffoli gate and four CNOT gates. The proposed design achieves a Quantum Cost of 9, representing a 25% reduction compared to the Peres structure, while maintaining a competitive logical depth of 4. We rigorously verify the logic and demonstrate that the reduction is achieved through the automated synthesis framework recently proposed by the authors.
The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.