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

Procedia Computer Science

Efficient Three Variables Reversible Logic Synthesis Using Mixed-polarity Toffoli Gate

Chua Shin Cheng, Ashutosh Kumar Singh, Lenin Gopal

Published Jan 1, 2015• 16 citations
Publisher

Abstract

In this paper, we present an efficient reversible logic synthesis algorithm that uses Toffoli and mixed-polarity based Toffoli gate. In this paper, we propose an algorithm to synthesizereversible function in their positive-polarity Reed Muller (PPRM) expansion and usethe Hamming Distance (HD) approach to select suitable transformation path. Once a transformation path is defined, suitable gates for substitution are selected through the gate matching factor and reduction is performed. The algorithm does not generate any extra lines and thus keeping the synthesized function in its simplest form. The algorithm target on efficient way to synthesize three variables based reversible function into a cascade of Toffoli and mixed-polarity based Toffoli gate in term of quantum cost and gate count. Experimental results showthat the proposed algorithm is efficient in terms of the realization of all three variable based reversible functions.

DOI
10.1016/j.procs.2015.10.035

Related papers

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 30, 2006•371 citations

Synthesis of Reversible and Quantum Circuit Using ROCBDD and Mixed-Polarity Toffoli Gate

Hieu Nguyen, Linh Hoang Tran

In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.

IEEE Access•Jan 1, 2021•5 citations

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

Toffoli network synthesis with templates

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

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the above synthesis approach. We present a basic method and, based on that, a bidirectional synthesis algorithm which produces a network of Toffoli gates realizing a given reversible specification. An asymptotically optimal modification of the basic synthesis algorithm employing generalized mEXOR gates is also presented. Transformations are then applied using template matching. The basis for a template is a network of gates that realizes the identity function. If a sequence of gates in the synthesized network matches a sequence comprised of more than half the gates in a template, then a transformation using the remaining gates in the template can be applied resulting in a reduction in the gate count for the synthesized network. All templates with up to six gates are described in this paper. Experimental results including an exhaustive examination of all 3-variable reversible functions and a collection of benchmark problems are presented. The paper concludes with suggestions for further research.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 24, 2005•228 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
In this paper, we present an efficient reversible logic synthesis algorithm that uses Toffoli and mixed-polarity based Toffoli gate. In this paper, we propose an algorithm to synthesizereversible function in their positive-polarity Reed Muller (PPRM) expansion and usethe Hamming Distance (HD) approach to select suitable transformation path. Once a transformation path is defined, suitable gates for substitution are selected through the gate matching factor and reduction is performed. The algorithm does not generate any extra lines and thus keeping the synthesized function in its simplest form. The algorithm target on efficient way to synthesize three variables based reversible function into a cascade of Toffoli and mixed-polarity based Toffoli gate in term of quantum cost and gate count. Experimental results showthat the proposed algorithm is efficient in terms of the realization of all three variable based reversible functions.
Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25
In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.
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.
Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the above synthesis approach. We present a basic method and, based on that, a bidirectional synthesis algorithm which produces a network of Toffoli gates realizing a given reversible specification. An asymptotically optimal modification of the basic synthesis algorithm employing generalized mEXOR gates is also presented. Transformations are then applied using template matching. The basis for a template is a network of gates that realizes the identity function. If a sequence of gates in the synthesized network matches a sequence comprised of more than half the gates in a template, then a transformation using the remaining gates in the template can be applied resulting in a reduction in the gate count for the synthesized network. All templates with up to six gates are described in this paper. Experimental results including an exhaustive examination of all 3-variable reversible functions and a collection of benchmark problems are presented. The paper concludes with suggestions for further research.
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.