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

Asia and South Pacific Design Automation Conference (ASP-DAC)

Synthesis of reversible circuits with minimal lines for large functions

Mathias Soeken, Robert Wille, Christoph Hilken, Nils Przigoda, Rolf Drechsler

Published Jan 1, 2012• 107 citations
Publisher

Abstract

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.

DOI
10.1109/aspdac.2012.6165069

Related papers

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

BDD-Based Synthesis of Reversible Logic

Robert Wille, Rolf Drechsler

Reversible logic became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.

International Journal of Applied Metaheuristic Computing•Oct 1, 2010•8 citations

Generalizing the Concept of Scalable Reversible Circuit Synthesis for Multiple-Valued Logic

Alwin Zulehner, P. Mercy Nesa Rani, Kamalika Datta +2 more

Research on reversible circuits has gained significance due to its application in quantum computations and many further areas such as the design of encoders. At the same time, the use of multiple-valued logic gained importance since this reduces the number of required entities in physical systems (e.g. in a future quantum computer). While most research is still conducted in the Boolean domain, there exist only few approaches which realize reversible circuits for multiple-valued logic. Moreover, most of the previously proposed solutions for synthesis of multiple-valued reversible circuits are not scalable and consider ternary (i.e. 3-valued circuits) only. Instead of overcoming these issues by developing new synthesis approaches for multiple-valued reversible circuits from scratch, we propose to utilize the recent accomplishments in the design of Boolean reversible circuits and to generalize them for multiple-valued logic. To this end, we discuss how to generalize Quantum Multiple-valued Decision Diagram based (QMDD-based) synthesis - a synthesis approach for Boolean reversible circuits which has been proven to be scalable and which has been used in several recently developed design flows. The discussions eventually show how to bridge the development gap between Boolean and multiple-valued logic for reversible circuits.

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

Determining the minimal number of lines for large reversible circuits

Robert Wille, Oliver Keszöcze, Rolf Drechsler

Synthesis of reversible circuits is an active research area motivated by its applications e.g. in quantum computation or low-power design. The number of used circuit lines is thereby a crucial criterion. In this paper, we introduce several methods (including a theoretical upper bound) for the efficient computation or at least approximation of the minimal number of lines needed to realize a given function in reversible logic. While the proposed exact approach requires a significant amount of run-time (exponential in the worst case), the heuristic methods lead to very precise approximations in very short run-time. Using this, it can be shown that current synthesis approaches for large functions are still far away from producing optimal circuits with respect to the number of lines.

Design, Automation, and Test in Europe•Mar 1, 2011•46 citations

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

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
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.
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 became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.
Research on reversible circuits has gained significance due to its application in quantum computations and many further areas such as the design of encoders. At the same time, the use of multiple-valued logic gained importance since this reduces the number of required entities in physical systems (e.g. in a future quantum computer). While most research is still conducted in the Boolean domain, there exist only few approaches which realize reversible circuits for multiple-valued logic. Moreover, most of the previously proposed solutions for synthesis of multiple-valued reversible circuits are not scalable and consider ternary (i.e. 3-valued circuits) only. Instead of overcoming these issues by developing new synthesis approaches for multiple-valued reversible circuits from scratch, we propose to utilize the recent accomplishments in the design of Boolean reversible circuits and to generalize them for multiple-valued logic. To this end, we discuss how to generalize Quantum Multiple-valued Decision Diagram based (QMDD-based) synthesis - a synthesis approach for Boolean reversible circuits which has been proven to be scalable and which has been used in several recently developed design flows. The discussions eventually show how to bridge the development gap between Boolean and multiple-valued logic for reversible circuits.
Synthesis of reversible circuits is an active research area motivated by its applications e.g. in quantum computation or low-power design. The number of used circuit lines is thereby a crucial criterion. In this paper, we introduce several methods (including a theoretical upper bound) for the efficient computation or at least approximation of the minimal number of lines needed to realize a given function in reversible logic. While the proposed exact approach requires a significant amount of run-time (exponential in the worst case), the heuristic methods lead to very precise approximations in very short run-time. Using this, it can be shown that current synthesis approaches for large functions are still far away from producing optimal circuits with respect to the number of lines.
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.
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.