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 Journal of Electronics and Telecommunications

Designing of Reversible Functions in Classical and Quantum Domains

Romaniuk, Ryszard S., Skorupski, Andrzej

Published Jun 20, 2024• 0 citations
OpenAlex

Abstract

First sections of the paper contain someconsiderations relevant to the reversibility of quantum gates. TheSolovay-Kitayev theorem shows that using proper set ofquantum gates one can build a quantum version of the nondeterministicTuring machine. On the other hand theGottesmann-Knill theorem shows the possibility to simulate thequantum machine consisting of only Clifford/Pauli group ofgates. This paper presents also an original method of designingthe reversible functions. This method is intended for the mostpopular gate set with three types of gates CNT (Control, NOTand Toffoli). The presented algorithm leads to cascade withminimal number CNT gates. This solution is called optimalreversible circuits. The paper is organized as follows. Section 5recalls basic concepts of reversible logic. Section 6 contain shortdescription of CNT set of the reversible gates. In Section 7 ispresented form of result of designing as the cascade of gates.Section 8 describes the algorithm and section 9 simple example.

Related papers

Designing of Reversible Functions in Classical and Quantum Domains

Andrzej Skorupski, Ryszard S. Romaniuk

First sections of the paper contain some considerations relevant to the reversibility of quantum gates. The Solovay-Kitayev theorem shows that using proper set of quantum gates one can build a quantum version of the nondeterministic Turing machine. On the other hand the Gottesmann-Knill theorem shows the possibility to simulate the quantum machine consisting of only Clifford/Pauli group of gates. This paper presents also an original method of designing the reversible functions. This method is intended for the most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm leads to cascade with minimal number CNT gates. This solution is called optimal reversible circuits. The paper is organized as follows. Section 5 recalls basic concepts of reversible logic. Section 6 contain short description of CNT set of the reversible gates. In Section 7 is presented form of result of designing as the cascade of gates. Section 8 describes the algorithm and section 9 simple example.

International Journal of Electronics and Telecommunications•Jun 25, 2024•0 citations

Graphical Method of Reversible Circuits Synthesis

Andrzej Skorupski

Abstract This paper presents a new approach to designing reversible circuits. Reversible circuits can decrease energy dissipation theoretically to zero. This feature is a base to build quantum computers. The main problem of reversible logic is designing optimal reversible circuits i.e. circuits with minimal gates number implementing the given reversible function. There are many types of reversible gates. Most popular library is a set of three types of gates so called CNT (Control, NOT and Toffoli). The method presented in this paper is based only on the Toffoli gates. A graphical representation of the reversible function called s-maps is introduced in the paper. This representation allows to find optimal reversible circuits. The paper is organized as follows. Section 1 recalls basic concepts of reversible logic. In Section 2 a graphical representation of the reversible functions is presented. Section 3 describes the algorithm whereby all optimal solutions of the given function could be obtained.

International Journal of Electronics and Telecommunications•Aug 28, 2017•2 citations

The Transforming Method Between Two Reversible Functions

Andrzej Skorupski, K. Gracki

This paper presents an original method of designing some special reversible circuits. This method is intended for the most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm is based on two types of cascades with these reversible gates. The problem of transformation between two reversible functions is solved. This method allows to find optimal reversible circuits. The paper is organized as follows. Section 1 and 2 recalls basic concepts of reversible logic. Especially the two types of cascades of reversible function are presented. In Section 3 there is introduced a problem of analysis of the cascades. Section 4 describes the method of synthesis of the optimal cascade for transformation of the given reversible function into another one.

International Journal of Electronics and Telecommunications•Feb 20, 2019•0 citations

Reversible gates and circuits descriptions

Krzystof Gracki

This paper presents basic methods of reversible circuit description. To design reversible circuit a set of gates has to be chosen. Most popular libraries are composed of three types of gates so called CNT gates (Control, NOT and Toffoli). The gate indexing method presented in this paper is based on the CNT gates set. It introduces a uniform indexing of the gates used during synthesis process of reversible circuits. The paper is organized as follows. Section 1 recalls basic concepts of reversible logic. In Section 2 and 3 a graphical representation of the reversible gates and circuits is described. Section 4 describes proposed uniform NCT gates indexing. The presented gate indexing method provides gate numbering scheme independent of lines number of the designed circuit. The solution for a circuit consisting of smaller number of lines is a subset of solution for a larger circuit.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 7, 2017•0 citations

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
First sections of the paper contain someconsiderations relevant to the reversibility of quantum gates. TheSolovay-Kitayev theorem shows that using proper set ofquantum gates one can build a quantum version of the nondeterministicTuring machine. On the other hand theGottesmann-Knill theorem shows the possibility to simulate thequantum machine consisting of only Clifford/Pauli group ofgates. This paper presents also an original method of designingthe reversible functions. This method is intended for the mostpopular gate set with three types of gates CNT (Control, NOTand Toffoli). The presented algorithm leads to cascade withminimal number CNT gates. This solution is called optimalreversible circuits. The paper is organized as follows. Section 5recalls basic concepts of reversible logic. Section 6 contain shortdescription of CNT set of the reversible gates. In Section 7 ispresented form of result of designing as the cascade of gates.Section 8 describes the algorithm and section 9 simple example.
First sections of the paper contain some considerations relevant to the reversibility of quantum gates. The Solovay-Kitayev theorem shows that using proper set of quantum gates one can build a quantum version of the nondeterministic Turing machine. On the other hand the Gottesmann-Knill theorem shows the possibility to simulate the quantum machine consisting of only Clifford/Pauli group of gates. This paper presents also an original method of designing the reversible functions. This method is intended for the most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm leads to cascade with minimal number CNT gates. This solution is called optimal reversible circuits. The paper is organized as follows. Section 5 recalls basic concepts of reversible logic. Section 6 contain short description of CNT set of the reversible gates. In Section 7 is presented form of result of designing as the cascade of gates. Section 8 describes the algorithm and section 9 simple example.
Abstract This paper presents a new approach to designing reversible circuits. Reversible circuits can decrease energy dissipation theoretically to zero. This feature is a base to build quantum computers. The main problem of reversible logic is designing optimal reversible circuits i.e. circuits with minimal gates number implementing the given reversible function. There are many types of reversible gates. Most popular library is a set of three types of gates so called CNT (Control, NOT and Toffoli). The method presented in this paper is based only on the Toffoli gates. A graphical representation of the reversible function called s-maps is introduced in the paper. This representation allows to find optimal reversible circuits. The paper is organized as follows. Section 1 recalls basic concepts of reversible logic. In Section 2 a graphical representation of the reversible functions is presented. Section 3 describes the algorithm whereby all optimal solutions of the given function could be obtained.
This paper presents an original method of designing some special reversible circuits. This method is intended for the most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm is based on two types of cascades with these reversible gates. The problem of transformation between two reversible functions is solved. This method allows to find optimal reversible circuits. The paper is organized as follows. Section 1 and 2 recalls basic concepts of reversible logic. Especially the two types of cascades of reversible function are presented. In Section 3 there is introduced a problem of analysis of the cascades. Section 4 describes the method of synthesis of the optimal cascade for transformation of the given reversible function into another one.
This paper presents basic methods of reversible circuit description. To design reversible circuit a set of gates has to be chosen. Most popular libraries are composed of three types of gates so called CNT gates (Control, NOT and Toffoli). The gate indexing method presented in this paper is based on the CNT gates set. It introduces a uniform indexing of the gates used during synthesis process of reversible circuits. The paper is organized as follows. Section 1 recalls basic concepts of reversible logic. In Section 2 and 3 a graphical representation of the reversible gates and circuits is described. Section 4 describes proposed uniform NCT gates indexing. The presented gate indexing method provides gate numbering scheme independent of lines number of the designed circuit. The solution for a circuit consisting of smaller number of lines is a subset of solution for a larger circuit.
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.