Reversible logic is being studied extensively due to its applications in the design of nanoscale circuits with ultra-low power dissipation and future technologies such as quantum computing. Most methods that synthesize reversible logic circuits are restricted to small functions and are thus, not scalable. Previous methods based on Binary Decision Diagrams (BDD) are scalable but introduce a large number of additional circuit lines. In this paper, we present a technique that maps subgraphs of the BDD to structures with known reversible-circuit templates by posing this as a subgraph isomorphism problem. Experimental results show that this approach reduces the number of additional circuit lines introduced by previous approaches while retaining their scalability. We further show that for small functions, there is also an improvement in the quantum cost.
Reversible logic is being studied extensively due to its applications in the design of nanoscale circuits with ultra-low power dissipation and future technologies such as quantum computing. Most methods that synthesize reversible logic circuits are restricted to small functions and are thus, not scalable. Previous methods based on Binary Decision Diagrams (BDD) are scalable but introduce a large number of additional circuit lines. In this paper, we present a technique that maps subgraphs of the BDD to structures with known reversible-circuit templates by posing this as a subgraph isomorphism problem. Experimental results show that this approach reduces the number of additional circuit lines introduced by previous approaches while retaining their scalability. We further show that for small functions, there is also an improvement in the quantum cost.
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.
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.
Reversible circuits are an emerging technology where all computations are performed in an invertible manner. Motivated by their promising applications, e.g. in the domain of quantum computation or in the low-power design, the synthesis of such circuits has been intensely studied. However, how to automatically realize reversible circuits with the minimal number of lines for large functions is an open research problem. In this paper, we propose a new synthesis approach which relies on concepts that are complementary to existing ones. While “conventional” function representations have been applied for synthesis so far (such as truth tables, ESOPs, BDDs), we exploit Quantum Multiple-valued Decision Diagrams (QMDDs) for this purpose. An algorithm is presented that performs transformations on this data-structure eventually leading to the desired circuit. Experimental results show the novelty of the proposed approach through enabling automatic synthesis of large reversible functions with the minimal number of circuit lines. Furthermore, the quantum cost of the resulting circuits is reduced by 50% on average compared to an existing state-of-the-art synthesis 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.
Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.
Binary Decision Diagrams (BDDs) are instrumental in many electronic design automation (EDA) tasks thanks to their compact representation of Boolean functions. In BDD‑based reversible‑circuit synthesis, which is critical for quantum computing, the chosen variable ordering governs the number of BDD nodes and thus the key metrics of resource consumption, such as Quantum Cost. Because finding an optimal variable ordering for BDDs is an NP‑complete problem, existing heuristics often degrade as circuit complexity grows. We introduce BDD2Seq, a graph‑to‑sequence framework that couples a Graph Neural Network encoder with a Pointer‑Network decoder and Diverse Beam Search to predict high‑quality orderings. By treating the circuit netlist as a graph, BDD2Seq learns structural dependencies that conventional heuristics overlooked, yielding smaller BDDs and faster synthesis. Extensive experiments on three public benchmarks show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern heuristic algorithms. To the best of our knowledge, this is the first work to tackle the variable‑ordering problem in BDD‑based reversible‑circuit synthesis with a graph‑based generative model and diversity‑promoting decoding.