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

Graphical Method of Reversible Circuits Synthesis

Andrzej Skorupski

Published Aug 28, 2017• 2 citations
Publisher

Abstract

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.

DOI
10.1515/eletel-2017-0031

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

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

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

A novel Toffoli network synthesis algorithm for reversible logic

Yexin Zheng, Chao Huang

Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2009•21 citations

Reversible logic circuit synthesis

Vivek Shende, Aditya K. Prasad, Igor L. Markov +1 more

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

Digest of technical papers/Digest of technical papers - IEEE/ACM International Conference on Computer-Aided Design•Jan 1, 2002•155 citations

Reversible logic circuit synthesis

Vivek Shende, Aditya K. Prasad, Igor L. Markov +1 more

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

International Conference on Computer Aided Design•Jun 25, 2003•69 citations
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.
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.
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.
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.
Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.