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

The Transforming Method Between Two Reversible Functions

Andrzej Skorupski, K. Gracki

Published Feb 20, 2019• 0 citations
Publisher

Abstract

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.

DOI
10.24425/123562

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

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

Network Structure Cascade for Reversible Logic

Zhijin Guan, Xiaolin Qin, Yi-Qing Zhang +1 more

A reversible logic function maps each of the 2m input patterns to a unique output pattern. The network cascade structure problem is to realize a reversible function by a cascade of primitive reversible gates. We present a method that synthesizes a network with family of Toffoli gates. The cascade algorithm finds cascade of Toffoli gates with no backtracking and minimal look-ahead, and apply transformations that reduce the number of gates in the network. We have synthesized all three input and output reversible functions and compare our results to the other optimal results. We also present the results of applying our synthesis method to obtain networks for number of benchmark function.

International Conference on Natural Computation (ICNC)•Jan 1, 2007•2 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

A Novel Algorithm for Reversible Circuit Optimization

Yi-Tzu Lo, Shu–Yu Kuo, Guo-Jyun Zeng +2 more

Reversible circuit synthesis is an important field in quantum computing, low-power design, and reversible circuit. The problem of reversible circuit synthesis is complicated and hard to solve because the input of the reversible circuit will experience a huge increase when extended to multi-bit. In this paper, a novel algorithm of reversible circuit synthesis is proposed. With the satisfied priority of positions, we can efficiently select the position which should be satisfied, and each selected gate is generated to benefit the overall situation. Therefore, the proposed algorithm is able to optimize the reversible circuit with fewer gates and can be implemented in regard to multibit reversible circuit synthesis. In addition, the gate set we used contains only Toffoli, spanning all wires. This Toffoli gate is liable to be transformed into another gate set and is helpful for algorithm design. The experiment shows that the proposed algorithm, with efficient and optimal results, is superior to others.

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Oct 1, 2015•1 citation
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.
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 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.
A reversible logic function maps each of the 2m input patterns to a unique output pattern. The network cascade structure problem is to realize a reversible function by a cascade of primitive reversible gates. We present a method that synthesizes a network with family of Toffoli gates. The cascade algorithm finds cascade of Toffoli gates with no backtracking and minimal look-ahead, and apply transformations that reduce the number of gates in the network. We have synthesized all three input and output reversible functions and compare our results to the other optimal results. We also present the results of applying our synthesis method to obtain networks for number of benchmark function.
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.
Reversible circuit synthesis is an important field in quantum computing, low-power design, and reversible circuit. The problem of reversible circuit synthesis is complicated and hard to solve because the input of the reversible circuit will experience a huge increase when extended to multi-bit. In this paper, a novel algorithm of reversible circuit synthesis is proposed. With the satisfied priority of positions, we can efficiently select the position which should be satisfied, and each selected gate is generated to benefit the overall situation. Therefore, the proposed algorithm is able to optimize the reversible circuit with fewer gates and can be implemented in regard to multibit reversible circuit synthesis. In addition, the gate set we used contains only Toffoli, spanning all wires. This Toffoli gate is liable to be transformed into another gate set and is helpful for algorithm design. The experiment shows that the proposed algorithm, with efficient and optimal results, is superior to others.