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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Reversible gates and circuits descriptions

Krzystof Gracki

Published Aug 7, 2017• 0 citations
Publisher

Abstract

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.

DOI
10.1117/12.2280765

Related papers

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

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

Optimal and asymptotically optimal NCT reversible circuits by the gate types

Dmitri Maslov

We report optimal and asymptotically optimal reversible circuits composed of NOT, CNOT, and Toffoli (NCT) gates, keeping the count by the subsets of the gate types used. This study fine tunes the circuit complexity figures for the realization of reversible functions via reversible NCT circuits. An important consequence is a result on the limitation of the use of the T-count quantum circuit metric popular in applications.

Quantum Information and Computation•Oct 1, 2016•21 citations

Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis

Zhiqiang Li, Hanwu Chen, Guowu Yang +1 more

Owing to the exponential nature of the memory and run-time complexity, many methods can only synthesize 3-bit reversible circuits and cannot synthesize 4-bit reversible circuits well. We mainly absorb the ideas of our 3-bit synthesis algorithms based on hash table and present the efficient algorithms which can construct almost all optimal 4-bit reversible logic circuits with many types of gates and at mini-length cost based on constructing the shortest coding and the specific topological compression; thus, the lossless compression ratio of the space of n -bit circuits reaches near 2×n! . This paper presents the first work to create all 3120218828 optimal 4-bit reversible circuits with up to 8 gates for the CNT (Controlled-NOT gate, NOT gate, and Toffoli gate) library, and it can quickly achieve 16 steps through specific cascading created circuits.

Journal of Applied Mathematics•Jan 1, 2013•5 citations

Optimization of Reversible Circuits Using Toffoli Decompositions with Negative Controls

Mariam Gado, Ahmed Younes

The synthesis and optimization of quantum circuits are essential for the construction of quantum computers. This paper proposes two methods to reduce the quantum cost of 3-bit reversible circuits. The first method utilizes basic building blocks of gate pairs using different Toffoli decompositions. These gate pairs are used to reconstruct the quantum circuits where further optimization rules will be applied to synthesize the optimized circuit. The second method suggests using a new universal library, which provides better quantum cost when compared with previous work in both cost015 and cost115 metrics; this proposed new universal library “Negative NCT” uses gates that operate on the target qubit only when the control qubit’s state is zero. A combination of the proposed basic building blocks of pairs of gates and the proposed Negative NCT library is used in this work for synthesis and optimization, where the Negative NCT library showed better quantum cost after optimization compared with the NCT library despite having the same circuit size. The reversible circuits over three bits form a permutation group of size 40,320 (23!), which is a subset of the symmetric group, where the NCT library is considered as the generators of the permutation group.

Symmetry•Jun 7, 2021•9 citations
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.
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.
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.
Owing to the exponential nature of the memory and run-time complexity, many methods can only synthesize 3-bit reversible circuits and cannot synthesize 4-bit reversible circuits well. We mainly absorb the ideas of our 3-bit synthesis algorithms based on hash table and present the efficient algorithms which can construct almost all optimal 4-bit reversible logic circuits with many types of gates and at mini-length cost based on constructing the shortest coding and the specific topological compression; thus, the lossless compression ratio of the space of n -bit circuits reaches near 2×n! . This paper presents the first work to create all 3120218828 optimal 4-bit reversible circuits with up to 8 gates for the CNT (Controlled-NOT gate, NOT gate, and Toffoli gate) library, and it can quickly achieve 16 steps through specific cascading created circuits.
The synthesis and optimization of quantum circuits are essential for the construction of quantum computers. This paper proposes two methods to reduce the quantum cost of 3-bit reversible circuits. The first method utilizes basic building blocks of gate pairs using different Toffoli decompositions. These gate pairs are used to reconstruct the quantum circuits where further optimization rules will be applied to synthesize the optimized circuit. The second method suggests using a new universal library, which provides better quantum cost when compared with previous work in both cost015 and cost115 metrics; this proposed new universal library “Negative NCT” uses gates that operate on the target qubit only when the control qubit’s state is zero. A combination of the proposed basic building blocks of pairs of gates and the proposed Negative NCT library is used in this work for synthesis and optimization, where the Negative NCT library showed better quantum cost after optimization compared with the NCT library despite having the same circuit size. The reversible circuits over three bits form a permutation group of size 40,320 (23!), which is a subset of the symmetric group, where the NCT library is considered as the generators of the permutation group.