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

International Conference on Advances in Computing, Communications and Informatics (ICACCI)

Reversible circuit optimization using modified toffoli templates

Mridula J Deshpande, H. V. Jayashree, V.K. Agrawal

Published Sep 1, 2017• 0 citations
Publisher

Abstract

Reversible gates are gaining popularity in the field of circuit synthesis due to their property of having lower power loss and reduced dissipation of power as heat. These low power design models need to have better optimization properties. In this paper, we have ventured into the template and rule based optimization process. While most reversible netlists are built using the standard Toffoli gates, the proposed Modified Toffoli Gate has been used to achieve optimization. In this paper, the quantum realization of mixed control Modified Toffoli Gate and negative control Modified Toffoli Gates are proposed. Few templates and rules for transforming the original Toffoli network to the Modified Toffoli network are also proposed. This optimization yields a better quantum cost and gate count when compared to that of it's Toffoli counterpart.

DOI
10.1109/icacci.2017.8125864

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

Fredkin/Toffoli templates for reversible logic synthesis

D. Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified-they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously.

International Conference on Computer Aided Design•May 13, 2004•23 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

Improved NCV Gate Realization of Arbitrary Size Toffoli Gates

Abhoy Kole, Kamalika Datta

The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers in recent years. The typical design flow for such circuits first carries out the step of synthesis in terms of reversible gates, and then maps (decomposes) each reversible gate into equivalent set of quantum gates (e.g. from the NCV library). Since its initial proposal in realizing a Toffoli gate using quantum gates, several structural modifications have been proposed in the literature in order to reduce the cost of the generated netlist. The most recently introduced approach produces improved NCV cascade successively by partitioning the control lines of the given Toffoli gate in all possible ways, and replacing intermediate Toffoli gates with optimized equivalent NCV cascades form a catalog. In this approach the complexity of decomposing large Toffoli gates is high. In the present paper an efficient heuristic for partitioning the control lines of a given Toffoli gate is proposed. This heuristic is used for decomposition of the Toffoli gate without using any NCV catalog, after applying a template based optimization step. The cost of resultant circuit is similar to or sometimes better than the one reported by previous approaches.

International Conference on VLSI Design•Jan 1, 2017•11 citations

Post synthesis optimization of reversible logic functions with extended template matching

H. V. Jayashree, V.K. Agrawal, N Shishir Bharadwaj

Research affinity towards Reversible Computing is increasing day to day due to its lower energy dissipation computing capability. To evaluate any reversible function it is necessary to build the system with reversible gates. In view of this there are many new reversible logic gates proposed by many authors. Quantum cost of few reversible gates are unpublished. Simplified version of transformation technique to synthesize new reversible gates with Fredkin and Toffoli gates network are presented in this paper. Post synthesis optimization with the new set of templates are carried out to reduce the Quantum cost.

International Conference on Circuits, Control, Communication and Computing (I4C)•Nov 1, 2014•1 citation

Rule-based Optimization of Reversible Toffoli Circuits

Xueyu Cheng

Optimization of reversible circuits is one of key problems of reversible logic synthesis.To solve the problem of high algorithm complexity and poor scalability of reversible Toffoli circuits,the paper analyzed and summarized relationship between adjacent Toffoli gates,proposed and proven the moving and simplification rules of sub-sequence of reversible circuit cascaded by Toffoli gates,and gave the optimization algorithm based on these rules.The algorithm examines the circuit bidirectionally according to the moving rules,searches the sub-sequence satisfying simplification rules,performs corresponding optimization,and the process is repeated until the circuit does' t change.The algorithm is irrelevant to the number of input lines,does' t need to store extra information,is suitable to different Toffoli circuit synthesis methods,and its algorithm complexity is O(s3),which is superior to O(n!t2s3)of generally used template optimization technique.Results of examples and experiments on all 3-bit reversible functions show that the number of gates and the control bits can be reduced effectively and the cost of reversible circuit is decreased.

•Jan 1, 2013•0 citations
Reversible gates are gaining popularity in the field of circuit synthesis due to their property of having lower power loss and reduced dissipation of power as heat. These low power design models need to have better optimization properties. In this paper, we have ventured into the template and rule based optimization process. While most reversible netlists are built using the standard Toffoli gates, the proposed Modified Toffoli Gate has been used to achieve optimization. In this paper, the quantum realization of mixed control Modified Toffoli Gate and negative control Modified Toffoli Gates are proposed. Few templates and rules for transforming the original Toffoli network to the Modified Toffoli network are also proposed. This optimization yields a better quantum cost and gate count when compared to that of it's Toffoli counterpart.
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.
Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified-they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously.
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.
The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers in recent years. The typical design flow for such circuits first carries out the step of synthesis in terms of reversible gates, and then maps (decomposes) each reversible gate into equivalent set of quantum gates (e.g. from the NCV library). Since its initial proposal in realizing a Toffoli gate using quantum gates, several structural modifications have been proposed in the literature in order to reduce the cost of the generated netlist. The most recently introduced approach produces improved NCV cascade successively by partitioning the control lines of the given Toffoli gate in all possible ways, and replacing intermediate Toffoli gates with optimized equivalent NCV cascades form a catalog. In this approach the complexity of decomposing large Toffoli gates is high. In the present paper an efficient heuristic for partitioning the control lines of a given Toffoli gate is proposed. This heuristic is used for decomposition of the Toffoli gate without using any NCV catalog, after applying a template based optimization step. The cost of resultant circuit is similar to or sometimes better than the one reported by previous approaches.
Research affinity towards Reversible Computing is increasing day to day due to its lower energy dissipation computing capability. To evaluate any reversible function it is necessary to build the system with reversible gates. In view of this there are many new reversible logic gates proposed by many authors. Quantum cost of few reversible gates are unpublished. Simplified version of transformation technique to synthesize new reversible gates with Fredkin and Toffoli gates network are presented in this paper. Post synthesis optimization with the new set of templates are carried out to reduce the Quantum cost.
Optimization of reversible circuits is one of key problems of reversible logic synthesis.To solve the problem of high algorithm complexity and poor scalability of reversible Toffoli circuits,the paper analyzed and summarized relationship between adjacent Toffoli gates,proposed and proven the moving and simplification rules of sub-sequence of reversible circuit cascaded by Toffoli gates,and gave the optimization algorithm based on these rules.The algorithm examines the circuit bidirectionally according to the moving rules,searches the sub-sequence satisfying simplification rules,performs corresponding optimization,and the process is repeated until the circuit does' t change.The algorithm is irrelevant to the number of input lines,does' t need to store extra information,is suitable to different Toffoli circuit synthesis methods,and its algorithm complexity is O(s3),which is superior to O(n!t2s3)of generally used template optimization technique.Results of examples and experiments on all 3-bit reversible functions show that the number of gates and the control bits can be reduced effectively and the cost of reversible circuit is decreased.