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

Journal of Circuits Systems and Computers

Reversible Circuits Synthesis from Functional Decision Diagrams by using Node Dependency Matrices

Suzana Stojković, Radomir S. Stanković, Claudio Moraga, Milena Stanković

Published Jun 10, 2019• 7 citations
Publisher

Abstract

Decision diagrams are a data structure suitable for reversible circuit synthesis. Functional decision diagrams (FDDs) are particularly convenient in synthesis with Toffoli gates, since the functional expressions for decomposition rules used in them are similar to the functional expressions of Toffoli gates. The main drawback of reversible circuit synthesis based on decision diagrams is the usually large number of ancilla lines. This paper presents two methods for the reduction of the number of ancilla lines in reversible circuits derived from FDDs by selecting the order of implementation of nodes. In the first method, nodes are implemented by levels, starting from the bottom level to the top. The method uses appropriately defined level dependency matrices for choosing the optimal order of implementation of nodes at the same level. In this way, the optimization is performed level by level. The second method uses a diagram dependency matrix expressing mutual dependencies among all the nodes in the diagram. This method is computationally more demanding than the first method, but the reductions of both the number of lines and the Quantum cost of the circuits are larger.

DOI
10.1142/s0218126620500796

Related papers

Effect of BDD Optimization on Synthesis of Reversible and Quantum Logic

Robert Wille, Rolf Drechsler

Synthesis of reversible and quantum logic has become an intensely studied topic in the last years. However, most synthesis methods are limited, since they rely on a truth table representation of the function to be synthesized. BDD-based synthesis offers an alternative. Here, reversible or quantum circuits are derived from a function given as Binary Decision Diagram (BDD) by substituting all nodes of the BDD with a cascade of Toffoli or elementary quantum gates, respectively. As a result, the application of the approach is not limited by the truth table of the function but by the (quite more efficient) BDD representation. Furthermore, many optimization techniques for BDDs exist which can be exploited. In this work, we evaluate the effect of three optimization methods for BDDs (namely shared nodes, complement edges, and advanced orderings) on the resulting reversible and quantum circuits. We describe in detail the adjustments, which have to be done to support these optimizations for synthesis, and discuss possible improvements and drawbacks. In a case study, the effects are experimentally evaluated. The results showed, that applying these optimization techniques leads to significant smaller circuits (with respect to number of gates and lines) in most of the cases.

Electronic Notes in Theoretical Computer Science•Mar 1, 2010•53 citations

Reversible Circuit Synthesis Method Using Sub-graphs of Shared Functional Decision Diagrams

Dengli Bu, Junyi Deng, Pengjie Tang +1 more

Abstract Reversible circuit synthesis methods based on decision diagrams achieve low quantum costs but do not account for quantum bit (qubit) limits for the application of reversible logic in quantum computing. Here, a synthesis method using sub-graphs of shared functional decision diagrams (SFDDs) is proposed for reducing the number of lines when synthesizing reversible circuits. An SFDD is partitioned into sub-graphs by exploiting the longest dominant-active paths, and the sub-graphs are mapped to reversible gate cascades. To further reduce the number of lines, template root matching is presented for reusing circuit lines. Experimental results indicate that the proposed method achieves the known minimum number of lines in many cases and has good scalability. Although the proposed method increases the quantum cost over a prior method based on functional decision diagrams, it significantly reduces the number of lines in most cases. Compared with the one-pass method using quantum multiple-valued decision diagrams, the proposed method reduces the quantum cost without increasing the number of lines in many cases. When compared with the lookup table-based method using a direct mapping flow, the method reduces the number of lines in a few cases. Thus, the method aids in the physical realization of a quantum circuit.

The Computer Journal•Aug 1, 2022•1 citation

Performance trade-off in decision diagram based synthesis of reversible logic circuits

H. V. Jayashree, Anmol Prakash Surhonne, V.K. Agrawal

Reversible computing is an emerging and promising technique due to its wide applications in quantum, optical and DNA computing and many more. Reversible circuit synthesis is a main focus for researchers as conventional synthesis techniques are not suitable for reversible circuits. Our work focuses on BDD based synthesis as it has capabilities of realizing circuit for large boolean functions unlike other reversible synthesis methods. Existing BDD based synthesis techniques rely on positive [1] and negative [2] controlled Toffoli gates. In this paper work we explore BDD based synthesis technique along with evolutionary computation method. We employed Fredkin and elementary CNOT gate library. Experimental results demonstrate that this approach reduces the gate count and quantum cost at the cost of increase in the number of lines.

IEEE International Conference on Electron Devices and Solid-State Circuits (EDSSC)•Jun 1, 2015•1 citation

Synthesis of quantum circuits based on incompletely specified functions and if-decision diagrams

Anatoly Alekseevich Prihozhy

The problem of synthesis and optimisation of logical reversible and quantum circuits from functional descriptions represented as decision diagrams is considered. It is one of the key problems being solved with the aim of creating quantum computing technology and quantum computers. A new method of stepwise transformation of the initial functional specification to a quantum circuit is proposed, which provides for the following project states: reduced ordered binary decision diagram, if-decision diagram, functional if-decision diagram, reversible circuit and quantum circuit. The novelty of the method consists in extending the Shannon and Davio expansions of a Boolean function on a single variable to the expansions of the same Boolean function on another function with obtaining decomposition products that are represented by incompletely defined Boolean functions. Uncertainty in the decomposition products gives remarkable opportunities for minimising the graph representation of the specified function. Instead of two outgoing branches of the binary diagram vertex, three outgoing branches of the if-diagram vertex are generated, which increase the level of parallelism in reversible and quantum circuits. For each transformation step, appropriate mapping rules are proposed that reduce the number of lines, gates and the depth of the reversible and quantum circuit. The comparison of new results with the results given by the known method of mapping the vertices of binary decision diagram into cascades of reversible and quantum gates shows a significant improvement in the quality of quantum circuits that are synthesised by the proposed method.

Journal of the Belarusian State University Mathematics and Informatics•Dec 14, 2021•0 citations

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

Hieu Nguyen, Linh Hoang Tran

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.

IEEE Access•Jan 1, 2021•5 citations

A Decision Diagram Package for Reversible and Quantum Circuit Simulation

D. Michael Miller, Mitchell Aaron Thornton, David A. Goodman

This paper presents a decision diagram structure intended for the simulation and verification of reversible and quantum circuits. The structure is designed to efficiently represent the matrices describing reversible and quantum gate and circuit behaviour and takes advantage of key properties of those matrices. Algorithms are described for efficiently building the decision diagram representation directly from a gate without constructing the actual matrix and for performing matrix multiplication which is the fundamental operation to determine the function realized by a cascade of gates. Experimental results show the methods presented are applicable to large circuits at the state of the art in reversible and quantum synthesis and design.

IEEE Congress on Evolutionary Computation (CEC)•Sep 22, 2006•22 citations
Decision diagrams are a data structure suitable for reversible circuit synthesis. Functional decision diagrams (FDDs) are particularly convenient in synthesis with Toffoli gates, since the functional expressions for decomposition rules used in them are similar to the functional expressions of Toffoli gates. The main drawback of reversible circuit synthesis based on decision diagrams is the usually large number of ancilla lines. This paper presents two methods for the reduction of the number of ancilla lines in reversible circuits derived from FDDs by selecting the order of implementation of nodes. In the first method, nodes are implemented by levels, starting from the bottom level to the top. The method uses appropriately defined level dependency matrices for choosing the optimal order of implementation of nodes at the same level. In this way, the optimization is performed level by level. The second method uses a diagram dependency matrix expressing mutual dependencies among all the nodes in the diagram. This method is computationally more demanding than the first method, but the reductions of both the number of lines and the Quantum cost of the circuits are larger.
Synthesis of reversible and quantum logic has become an intensely studied topic in the last years. However, most synthesis methods are limited, since they rely on a truth table representation of the function to be synthesized. BDD-based synthesis offers an alternative. Here, reversible or quantum circuits are derived from a function given as Binary Decision Diagram (BDD) by substituting all nodes of the BDD with a cascade of Toffoli or elementary quantum gates, respectively. As a result, the application of the approach is not limited by the truth table of the function but by the (quite more efficient) BDD representation. Furthermore, many optimization techniques for BDDs exist which can be exploited. In this work, we evaluate the effect of three optimization methods for BDDs (namely shared nodes, complement edges, and advanced orderings) on the resulting reversible and quantum circuits. We describe in detail the adjustments, which have to be done to support these optimizations for synthesis, and discuss possible improvements and drawbacks. In a case study, the effects are experimentally evaluated. The results showed, that applying these optimization techniques leads to significant smaller circuits (with respect to number of gates and lines) in most of the cases.
Abstract Reversible circuit synthesis methods based on decision diagrams achieve low quantum costs but do not account for quantum bit (qubit) limits for the application of reversible logic in quantum computing. Here, a synthesis method using sub-graphs of shared functional decision diagrams (SFDDs) is proposed for reducing the number of lines when synthesizing reversible circuits. An SFDD is partitioned into sub-graphs by exploiting the longest dominant-active paths, and the sub-graphs are mapped to reversible gate cascades. To further reduce the number of lines, template root matching is presented for reusing circuit lines. Experimental results indicate that the proposed method achieves the known minimum number of lines in many cases and has good scalability. Although the proposed method increases the quantum cost over a prior method based on functional decision diagrams, it significantly reduces the number of lines in most cases. Compared with the one-pass method using quantum multiple-valued decision diagrams, the proposed method reduces the quantum cost without increasing the number of lines in many cases. When compared with the lookup table-based method using a direct mapping flow, the method reduces the number of lines in a few cases. Thus, the method aids in the physical realization of a quantum circuit.
Reversible computing is an emerging and promising technique due to its wide applications in quantum, optical and DNA computing and many more. Reversible circuit synthesis is a main focus for researchers as conventional synthesis techniques are not suitable for reversible circuits. Our work focuses on BDD based synthesis as it has capabilities of realizing circuit for large boolean functions unlike other reversible synthesis methods. Existing BDD based synthesis techniques rely on positive [1] and negative [2] controlled Toffoli gates. In this paper work we explore BDD based synthesis technique along with evolutionary computation method. We employed Fredkin and elementary CNOT gate library. Experimental results demonstrate that this approach reduces the gate count and quantum cost at the cost of increase in the number of lines.
The problem of synthesis and optimisation of logical reversible and quantum circuits from functional descriptions represented as decision diagrams is considered. It is one of the key problems being solved with the aim of creating quantum computing technology and quantum computers. A new method of stepwise transformation of the initial functional specification to a quantum circuit is proposed, which provides for the following project states: reduced ordered binary decision diagram, if-decision diagram, functional if-decision diagram, reversible circuit and quantum circuit. The novelty of the method consists in extending the Shannon and Davio expansions of a Boolean function on a single variable to the expansions of the same Boolean function on another function with obtaining decomposition products that are represented by incompletely defined Boolean functions. Uncertainty in the decomposition products gives remarkable opportunities for minimising the graph representation of the specified function. Instead of two outgoing branches of the binary diagram vertex, three outgoing branches of the if-diagram vertex are generated, which increase the level of parallelism in reversible and quantum circuits. For each transformation step, appropriate mapping rules are proposed that reduce the number of lines, gates and the depth of the reversible and quantum circuit. The comparison of new results with the results given by the known method of mapping the vertices of binary decision diagram into cascades of reversible and quantum gates shows a significant improvement in the quality of quantum circuits that are synthesised by the proposed method.
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.
This paper presents a decision diagram structure intended for the simulation and verification of reversible and quantum circuits. The structure is designed to efficiently represent the matrices describing reversible and quantum gate and circuit behaviour and takes advantage of key properties of those matrices. Algorithms are described for efficiently building the decision diagram representation directly from a gate without constructing the actual matrix and for performing matrix multiplication which is the fundamental operation to determine the function realized by a cascade of gates. Experimental results show the methods presented are applicable to large circuits at the state of the art in reversible and quantum synthesis and design.