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 International Symposium on Multiple-Valued Logic (ISMVL)

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

Alwin Zulehner, P. Mercy Nesa Rani, Kamalika Datta, Indranil Sengupta, Robert Wille

Published May 1, 2018• 2 citations
Publisher

Abstract

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.

DOI
10.1109/ismvl.2018.00028

Related papers

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•104 citations

On design of multiple-valued sequential reversible circuits for nanotechnology based systems

Majid Mohammadi, Mohammad Eshghi, Majid Haghparast

Multiple-valued reversible logic is an emerging area in reversible and quantum logic circuit synthesis. Multiple-valued reversible logic circuits can potentially reduce the width of the reversible or quantum circuit which is a limitation in current quantum technology. In this paper we propose a method to synthesize the multiple-valued reversible sequential circuits. Implementations for ternary D and T flip flops and edge triggered D flip flop are proposed. Synthesis of generalized fanout circuit and generalized r-valued T flip flop are also presented.

IEEE Region 10 Conference (TENCON)•Nov 1, 2008•18 citations

A Review on Fundamentals of Ternary Reversible Logic Circuits

P. Mercy Nesa Rani, Phrangboklang Lyngton Thangkhiew

One of the main motivations for using ternary logic systems is the amount of information per circuit line is higher as compared to the corresponding binary logic representation, thereby leading to more compact circuit realizations. This is particularly attractive for quantum computing as qutrits are expensive resources and minimizing their number is one of the main objectives during synthesis. Therefore, ternary reversible logic synthesis has drawn significant attention among researchers. It deals with fundamental unit of information called qutrits that can exist in one of the three states |0>, |1> and |2>. Hence, the aim of this paper is to bridge the knowledge gap for the beginners in this domain than searching the entire space. Therefore, the present work discusses the basic concepts of ternary reversible logic and ternary reversible gates. The detailed discussion of the various ternary reversible logic synthesis will enable the beginners in this domain to understand the ternary reversible logic in a better way.

International Conference on Computational Performance Evaluation (ComPE)•Jul 1, 2020•9 citations

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

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•2 citations

QUANTUM LOGIC CIRCUIT DESIGN OF MANY-VALUED GALOIS REVERSIBLE EXPANSIONS AND FAST TRANSFORMS

Anas N. Al‐Rabadi

Many-valued quantum circuit synthesis of many-valued reversible expansions and fast transforms is introduced in this paper. Since the reduction of power consumption is a major requirement for the circuit design in future technologies, such as in quantum computing, the main features of several future technologies will include reversibility. Consequently, the new quantum circuits can play an important task in the design of future circuits that consume minimal power. In addition, the new quantum circuit methodology is general and can be used to realize any multiple-valued function in the quantum space. It is also shown that the structural generality advantage that results from the new design methodology is opposed with the increased quantum structural complexity disadvantage which may be considered in any further cost-benefit design analysis.

Journal of Circuits Systems and Computers•Oct 1, 2007•2 citations
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.
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.
Multiple-valued reversible logic is an emerging area in reversible and quantum logic circuit synthesis. Multiple-valued reversible logic circuits can potentially reduce the width of the reversible or quantum circuit which is a limitation in current quantum technology. In this paper we propose a method to synthesize the multiple-valued reversible sequential circuits. Implementations for ternary D and T flip flops and edge triggered D flip flop are proposed. Synthesis of generalized fanout circuit and generalized r-valued T flip flop are also presented.
One of the main motivations for using ternary logic systems is the amount of information per circuit line is higher as compared to the corresponding binary logic representation, thereby leading to more compact circuit realizations. This is particularly attractive for quantum computing as qutrits are expensive resources and minimizing their number is one of the main objectives during synthesis. Therefore, ternary reversible logic synthesis has drawn significant attention among researchers. It deals with fundamental unit of information called qutrits that can exist in one of the three states |0>, |1> and |2>. Hence, the aim of this paper is to bridge the knowledge gap for the beginners in this domain than searching the entire space. Therefore, the present work discusses the basic concepts of ternary reversible logic and ternary reversible gates. The detailed discussion of the various ternary reversible logic synthesis will enable the beginners in this domain to understand the ternary reversible logic in a better way.
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.
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.
Many-valued quantum circuit synthesis of many-valued reversible expansions and fast transforms is introduced in this paper. Since the reduction of power consumption is a major requirement for the circuit design in future technologies, such as in quantum computing, the main features of several future technologies will include reversibility. Consequently, the new quantum circuits can play an important task in the design of future circuits that consume minimal power. In addition, the new quantum circuit methodology is general and can be used to realize any multiple-valued function in the quantum space. It is also shown that the structural generality advantage that results from the new design methodology is opposed with the increased quantum structural complexity disadvantage which may be considered in any further cost-benefit design analysis.