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

ACM/IEEE Design Automation Conference (DAC)

Unlocking efficiency and scalability of reversible logic synthesis using conventional logic synthesis

Mathias Soeken, Anupam Chattopadhyay

Published May 25, 2016• 22 citations
Publisher

Abstract

Latest quantum technologies promise realization of extremely large circuits, whereas, reversible logic synthesis, the key automation step for quantum computing, suffers from scalability bottleneck. Scalability can be achieved with Decision Diagram (DD)-based synthesis at the cost of significant an-cilla/garbage lines overhead. In this paper, we present a novel hierarchical reversible logic synthesis, where DD-based synthesis is invoked within an And-Inverter Graph (AIG)-based synthesis wrapper, balancing scalability and performance.

DOI
10.1145/2897937.2898107

Related papers

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

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

Efficient Reversible Logic Synthesis via Isomorphic Subgraph Matching

Mridul Krishna, Anupam Chattopadhyay

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.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2014•13 citations

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 reversible circuits with minimal lines for large functions

Mathias Soeken, Robert Wille, Christoph Hilken +2 more

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.

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

Positive Davio-based synthesis algorithm for reversible logic

Yu Pang, Shaoquan Wang, Zhilong He +3 more

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.

IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)•Oct 1, 2011•17 citations
Latest quantum technologies promise realization of extremely large circuits, whereas, reversible logic synthesis, the key automation step for quantum computing, suffers from scalability bottleneck. Scalability can be achieved with Decision Diagram (DD)-based synthesis at the cost of significant an-cilla/garbage lines overhead. In this paper, we present a novel hierarchical reversible logic synthesis, where DD-based synthesis is invoked within an And-Inverter Graph (AIG)-based synthesis wrapper, balancing scalability and performance.
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.
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 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 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.
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.
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.