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

IEEE Access

Synthesis of Reversible and Quantum Circuit Using ROCBDD and Mixed-Polarity Toffoli Gate

Hieu Nguyen, Linh Hoang Tran

Published Jan 1, 2021• 5 citations
Publisher

Abstract

In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.

DOI
10.1109/access.2021.3116756

Related papers

An Implementation of KFDD based Reversible Logic using IBM-Q Experience

P. Sangeetha, Prameela Kumari

Reversible logic is a circuit which has the ability to reduce the power dissipation. This type of logic circuit is used for the process of running the system both forward and backward.One of the main advantages of using any reversible logic is to get back the original data and to reduce the garbage output. Logic synthesis based on the Kronecker Functional Decision Diagram (KFDD) are generated for different reversible cascade methods both complemented and uncomplemented edge by using different reversible gates such as the CNOT (Controlled NOT), NOT, Toffoli gates, Peres gates, etc., and implemented in a quantum processor. In order to reduce the qubits which in turn reduces the quantum cost, it is implemented using reversible logic synthesis in KFDD method.The proposed method shows the implementation of these reversible circuits in an IBM quantum computer to find the probabilities, as it gives less quantum cost and also consumes less time when compared to other decision diagram. Reversible logic finds a wide range of applications in quantum computing and also in areas which deals with the low power design.This paper presents the implementation of KFDD using quantum circuits in IBM Quantum (IBM-Q) processor using different reversible logics and the output is discussed.

International Conference on Computing for Sustainable Global Development•Mar 1, 2020•4 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

Minimization of AND-XOR Expressions with Decoders for Quantum Circuits

Sonia Yang, Ali Al-Bayaty, Marek Perkowski

This paper introduces a new logic structure for reversible quantum circuit synthesis. Our synthesis method aims to minimize the quantum cost of reversible quantum circuits with decoders. In this method, multi-valued input, binary output (MVI) functions are utilized as a mathematical concept only, but the circuits are binary. We introduce the new concept of ``Multi-Valued Input Fixed Polarity Reed-Muller (MVI-RM)" forms. Our decoder-based circuit uses three logical levels in contrast to commonly-used methods based on Exclusive-or Sum of Products (ESOP) with two levels (AND-XOR expressions), realized by Toffoli gates. In general, the high number of input qubits in the resulting Toffoli gates is a problem that greatly impacts the quantum cost. Using decoders decreases the number of input qubits in these Toffoli gates. We present two practical algorithms for three-level circuit synthesis by finding the MVI-FPRM: products-matching and the newly developed butterfly diagrams. The best MVI-FPRM forms are factorized and reduced to approximate Multi-Valued Input Generalized Reed-Muller (MVI-GRM) forms.

quant-pharXiv:2601.02515•Jan 7, 2026•0 citations

A Novel Hypercube-Based Heuristic for Quantum Boolean Circuit Synthesis

Yu-Chi Jiang, Kuo-Chun Tseng, Cheng-Yen Hua +3 more

Quantum computation has extraordinary capabilities for solving complicated problems. As quantum computations are reversible by nature, reversible circuits are important for the development of quantum computation techniques. Designing an effective and efficient method for synthesizing reversible circuits to reduce costs and stabilize circuit efficiency is crucial. The traditional synthesis methods of solving reversible circuits focus on the conversion efficiency rather than discussing the properties of the reversible function. Thus, this paper aims to propose a novel synthesis method that directly and efficiently optimizes reversible circuit synthesis with the properties of the reversible circuit. The proposed method converts the reversible function into a hypercube, allowing visual observations of the overall circuit. Two new indicators, the adjacent Hamming distance (AHD) and total cycle distance (TCD), aid in effective decision-making, generating shorter circuits. Furthermore, we use the generalized Toffoli gate set, which without requiring any additional ancilla bits and has applications in error correction and fault tolerance. The experimental results show that our method can find better solutions than traditional methods, significantly reducing the gate count, while the hypercube assists in synthesizing the reversible circuit.

IEEE Journal on Emerging and Selected Topics in Circuits and Systems•Aug 29, 2022•9 citations

Reversible Logic Synthesis Using Binary Decision Diagrams With Exploiting Efficient Reordering Operators

Baker K. Abdalhaq, Ahmed Awad, Amjad Hawash

With the continuous shrinkage of transistor sizes in very large scale integrated circuits, power consumption forms a serious concern to be tackled. With their ability to allow for zero energy dissipation, reversible circuits have been considered as promising solution to meetup with low power design requirements. Moreover, advances in their synthesis methodologies can be easily applied to quantum circuits due to the inherited reversibility of the latter. Although numerous algorithms have been proposed in the literature to synthesize reversible circuits and map them into their corresponding quantum circuits, the scalability and computational effort of such algorithms form a serious concern when synthesizing large size input functions. Binary Decision Diagram-based synthesis for reversible circuits has shown great evidence in realizing reversible circuits with low quantum cost through exploiting proper reduction rules for smaller graph size. However, the order of the variables in the decision diagram impacts its overall size, and thus, the cost of its corresponding reversible circuit. While several reordering algorithms have been proposed in this manner, their direct impact on the quantum cost has not been considered. In this article, a Binary Decision Diagram-based algorithm for reversible circuit synthesis is proposed to synthesize reversible circuits for a given Boolean function with low quantum cost through exploiting a linearized relationship between the decision diagram size and the corresponding quantum cost. Thereafter, different decision diagram reordering algorithms have been integrated with the proposed algorithm and compared in terms of their impact on the quantum cost. Experimental results show that Genetic Algorithm-based reordering for decision diagram, supported with, cycle crossover, inverse mutation, and tournament selection, results in the least quantum cost of the output circuit if compared with other algorithms due to its property in preserving the nodes of the decision diagram in their near-optimal locations during the optimiation recipe.

IEEE Access•Jan 1, 2020•7 citations

SAT-based Exact Synthesis of Ternary Reversible Circuits using a Functionally Complete Gate Library

Abhoy Kole, Kamalika Datta, Indranil Sengupta +1 more

The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.

Euromicro Conference on Digital System Design (DSD)•Aug 1, 2022•1 citation
In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.
Reversible logic is a circuit which has the ability to reduce the power dissipation. This type of logic circuit is used for the process of running the system both forward and backward.One of the main advantages of using any reversible logic is to get back the original data and to reduce the garbage output. Logic synthesis based on the Kronecker Functional Decision Diagram (KFDD) are generated for different reversible cascade methods both complemented and uncomplemented edge by using different reversible gates such as the CNOT (Controlled NOT), NOT, Toffoli gates, Peres gates, etc., and implemented in a quantum processor. In order to reduce the qubits which in turn reduces the quantum cost, it is implemented using reversible logic synthesis in KFDD method.The proposed method shows the implementation of these reversible circuits in an IBM quantum computer to find the probabilities, as it gives less quantum cost and also consumes less time when compared to other decision diagram. Reversible logic finds a wide range of applications in quantum computing and also in areas which deals with the low power design.This paper presents the implementation of KFDD using quantum circuits in IBM Quantum (IBM-Q) processor using different reversible logics and the output is discussed.
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.
This paper introduces a new logic structure for reversible quantum circuit synthesis. Our synthesis method aims to minimize the quantum cost of reversible quantum circuits with decoders. In this method, multi-valued input, binary output (MVI) functions are utilized as a mathematical concept only, but the circuits are binary. We introduce the new concept of ``Multi-Valued Input Fixed Polarity Reed-Muller (MVI-RM)" forms. Our decoder-based circuit uses three logical levels in contrast to commonly-used methods based on Exclusive-or Sum of Products (ESOP) with two levels (AND-XOR expressions), realized by Toffoli gates. In general, the high number of input qubits in the resulting Toffoli gates is a problem that greatly impacts the quantum cost. Using decoders decreases the number of input qubits in these Toffoli gates. We present two practical algorithms for three-level circuit synthesis by finding the MVI-FPRM: products-matching and the newly developed butterfly diagrams. The best MVI-FPRM forms are factorized and reduced to approximate Multi-Valued Input Generalized Reed-Muller (MVI-GRM) forms.
Quantum computation has extraordinary capabilities for solving complicated problems. As quantum computations are reversible by nature, reversible circuits are important for the development of quantum computation techniques. Designing an effective and efficient method for synthesizing reversible circuits to reduce costs and stabilize circuit efficiency is crucial. The traditional synthesis methods of solving reversible circuits focus on the conversion efficiency rather than discussing the properties of the reversible function. Thus, this paper aims to propose a novel synthesis method that directly and efficiently optimizes reversible circuit synthesis with the properties of the reversible circuit. The proposed method converts the reversible function into a hypercube, allowing visual observations of the overall circuit. Two new indicators, the adjacent Hamming distance (AHD) and total cycle distance (TCD), aid in effective decision-making, generating shorter circuits. Furthermore, we use the generalized Toffoli gate set, which without requiring any additional ancilla bits and has applications in error correction and fault tolerance. The experimental results show that our method can find better solutions than traditional methods, significantly reducing the gate count, while the hypercube assists in synthesizing the reversible circuit.
With the continuous shrinkage of transistor sizes in very large scale integrated circuits, power consumption forms a serious concern to be tackled. With their ability to allow for zero energy dissipation, reversible circuits have been considered as promising solution to meetup with low power design requirements. Moreover, advances in their synthesis methodologies can be easily applied to quantum circuits due to the inherited reversibility of the latter. Although numerous algorithms have been proposed in the literature to synthesize reversible circuits and map them into their corresponding quantum circuits, the scalability and computational effort of such algorithms form a serious concern when synthesizing large size input functions. Binary Decision Diagram-based synthesis for reversible circuits has shown great evidence in realizing reversible circuits with low quantum cost through exploiting proper reduction rules for smaller graph size. However, the order of the variables in the decision diagram impacts its overall size, and thus, the cost of its corresponding reversible circuit. While several reordering algorithms have been proposed in this manner, their direct impact on the quantum cost has not been considered. In this article, a Binary Decision Diagram-based algorithm for reversible circuit synthesis is proposed to synthesize reversible circuits for a given Boolean function with low quantum cost through exploiting a linearized relationship between the decision diagram size and the corresponding quantum cost. Thereafter, different decision diagram reordering algorithms have been integrated with the proposed algorithm and compared in terms of their impact on the quantum cost. Experimental results show that Genetic Algorithm-based reordering for decision diagram, supported with, cycle crossover, inverse mutation, and tournament selection, results in the least quantum cost of the output circuit if compared with other algorithms due to its property in preserving the nodes of the decision diagram in their near-optimal locations during the optimiation recipe.
The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.