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

Devices for Integrated Circuit (DevIC)

Comprehensive quantum analysis of existing four variable reversible gates

Mahamuda Sultana, Munna Prasad, Puja Roy, Soumya Sarkar, Suranjan Das, Atal Chaudhuri

Published Mar 1, 2017• 4 citations
Publisher

Abstract

Throughout the last decade, reversible logic has been an emerging research topic. Over the years, a considerable number of application specific new reversible gates with varied characteristics have been proposed. Barring few, most of the gates lack fundamental quantum mapping in contemporary literature. This paper takes into account the four variable reversible gates those have been proposed and provides the Toffoli mapping using positive control lines. The authors optimize the designs using negative control lines wherever possible. The quantum cost, quantum gate count and two-qubit gate count required to implement those reversible gates have been provided which will set a benchmark for optimized gate choice for complex Boolean realizations. The authors also provide Hamming Distance based Complexity analysis.

DOI
10.1109/devic.2017.8073918

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•379 citations

In-depth Comparative Analysis of Reversible Gates for Designing Logic Circuits

Hari Mohan Gaur, Ashutosh Kumar Singh, Umesh Ghanekar

Reversible logic is expanding grounds with its applicability to various upcoming technologies and quantum computation. Numerous reversible gates has also been proposed for designing logic circuits apart of basic quantum controlled Toffoli and Fredkin gates. A comparative study and analysis of a range of reversible gates from the literature is presented in this paper to obtain an optimal solution for designing these circuits. The gates are synthesized and implemented to obtain equivalent quantum circuits and operating cost in terms of number of inputs, gate cost, quantum cost, garbage output and ancilla input. The comparison is done at two subsequent levels i.e. gates structural level and circuit design level, providing a better solution for designing logic circuits. It is calculated that, basic gates are 50% efficient at gate level and 33% at design level analysis in terms of gate cost, as compared to the most efficient gates proposed in the literature.

Procedia Computer Science•Jan 1, 2018•36 citations

Efficient Approaches for Designing Quantum Costs of Various Reversible Gates

M surekha

Over the last few decades, research in reversible logic has increasingly become very popular and it is gaining greater momentum in the present word.Reversible logic has started finding concert applications in quantum computing, optical computing, nano-technology based system, low-power CMOS design, VLSI design.The principal objective of this work is to argue for quantum implementation of various reversible logic gates by using C-NOT, Controlled-V and Controlled-V + gates.The present work presents parallel adder/subtractor (with over flow detection), as well as Binary coded decimal adder (BCD) in terms of number of gates, garbage outputs, quantum cost, delay and hardware complexity compared to existing design.

International Journal of Engineering Studies•Jun 30, 2017•21 citations

Fast Synthesis of Reversible Circuits Using a Sorting Algorithm and Optimization.

Ömercan Susam, Mustafa Altun

This paper studies synthesis and optimization of reversible circuits composed of Toffoli gates with negative and positive control lines. The proposed synthesis algorithm performs sorting among optimal implementations of certain functions - called as essential functions - to implement any reversible Boolean function. Essential functions comprise very small amount of all functions. For example, to implement 3 bit circuits, 28 essential functions out of all 40320 functions are needed. The proposed optimization algorithm considers both reversible and quantum circuit costs. First, reversible cost is reduced by considering adjacent gate pairs. Then, inner quantum structures of the gates are investigated and quantum optimization is performed. The proposed algorithms are evaluated on benchmark circuits in comparison with the results in the literature.

J. Multiple Valued Log. Soft Comput.•Jan 1, 2017•4 citations

A novel reversible two's complement gate (TCG) and its quantum mapping

Ayan Chaudhuri, Mahamuda Sultana, Diganta Sengupta +1 more

Reversible Logic has been an emerging topic of research for the last decade and has witnessed a substantial amount of work related to synthesis algorithms, optimization techniques and Boolean circuits. Considerable amount of reversible binary arithmetic designs have been proposed. 2's complement addition forms a fundamental arithmetic operation. This present communication proposes a novel reversible Two's Complement Gate (TCG) which can directly constitute a reversible adder/subtractor design. We provide the Toffoli representation of the gate for its plausible quantum realization. We also provide the quantum metric analysis for evaluation of our proposed gate. The proposed gate has also been implemented using Quantum-Dot Cellular Automata. Comparison with an existing proposal in literature has been done and the TCG gate has been observed to excel over the counterpart.

Devices for Integrated Circuit (DevIC)•Mar 1, 2017•7 citations

Reducing Quantum Cost in Reversible Toffoli Circuits

Marek Szyprowski, Paweł Kerntopf

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.

arXiv:1105.5831•May 29, 2011•29 citations
Throughout the last decade, reversible logic has been an emerging research topic. Over the years, a considerable number of application specific new reversible gates with varied characteristics have been proposed. Barring few, most of the gates lack fundamental quantum mapping in contemporary literature. This paper takes into account the four variable reversible gates those have been proposed and provides the Toffoli mapping using positive control lines. The authors optimize the designs using negative control lines wherever possible. The quantum cost, quantum gate count and two-qubit gate count required to implement those reversible gates have been provided which will set a benchmark for optimized gate choice for complex Boolean realizations. The authors also provide Hamming Distance based Complexity analysis.
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
Reversible logic is expanding grounds with its applicability to various upcoming technologies and quantum computation. Numerous reversible gates has also been proposed for designing logic circuits apart of basic quantum controlled Toffoli and Fredkin gates. A comparative study and analysis of a range of reversible gates from the literature is presented in this paper to obtain an optimal solution for designing these circuits. The gates are synthesized and implemented to obtain equivalent quantum circuits and operating cost in terms of number of inputs, gate cost, quantum cost, garbage output and ancilla input. The comparison is done at two subsequent levels i.e. gates structural level and circuit design level, providing a better solution for designing logic circuits. It is calculated that, basic gates are 50% efficient at gate level and 33% at design level analysis in terms of gate cost, as compared to the most efficient gates proposed in the literature.
Over the last few decades, research in reversible logic has increasingly become very popular and it is gaining greater momentum in the present word.Reversible logic has started finding concert applications in quantum computing, optical computing, nano-technology based system, low-power CMOS design, VLSI design.The principal objective of this work is to argue for quantum implementation of various reversible logic gates by using C-NOT, Controlled-V and Controlled-V + gates.The present work presents parallel adder/subtractor (with over flow detection), as well as Binary coded decimal adder (BCD) in terms of number of gates, garbage outputs, quantum cost, delay and hardware complexity compared to existing design.
This paper studies synthesis and optimization of reversible circuits composed of Toffoli gates with negative and positive control lines. The proposed synthesis algorithm performs sorting among optimal implementations of certain functions - called as essential functions - to implement any reversible Boolean function. Essential functions comprise very small amount of all functions. For example, to implement 3 bit circuits, 28 essential functions out of all 40320 functions are needed. The proposed optimization algorithm considers both reversible and quantum circuit costs. First, reversible cost is reduced by considering adjacent gate pairs. Then, inner quantum structures of the gates are investigated and quantum optimization is performed. The proposed algorithms are evaluated on benchmark circuits in comparison with the results in the literature.
Reversible Logic has been an emerging topic of research for the last decade and has witnessed a substantial amount of work related to synthesis algorithms, optimization techniques and Boolean circuits. Considerable amount of reversible binary arithmetic designs have been proposed. 2's complement addition forms a fundamental arithmetic operation. This present communication proposes a novel reversible Two's Complement Gate (TCG) which can directly constitute a reversible adder/subtractor design. We provide the Toffoli representation of the gate for its plausible quantum realization. We also provide the quantum metric analysis for evaluation of our proposed gate. The proposed gate has also been implemented using Quantum-Dot Cellular Automata. Comparison with an existing proposal in literature has been done and the TCG gate has been observed to excel over the counterpart.
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.