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 Great Lakes Symposium on VLSI (GLSVLSI)

Reversible synthesis of symmetric boolean functions based on unate decomposition

Arighna Deb, Debesh Kumar Das, Hafizur Rahaman, Bhargab B. Bhattacharya

Published May 2, 2013• 4 citations
Publisher

Abstract

In this paper, we introduce a new method to realize symmetric Boolean functions with reversible logic based on unate decomposition. In contrast to earlier synthesis methods, our solution uses a simpler circuit structure of reversible gates, which enables a significant reduction with respect to quantum cost. The resulting design offers an improved solution to reversible synthesis of symmetric Boolean functions.

DOI
10.1145/2483028.2483138

Related papers

Reversible Synthesis of Symmetric Functions with a Simple Regular Structure and Easy Testability

Arighna Deb, Debesh Kumar Das, Hafizur Rahaman +3 more

In this article, we introduce a novel method of synthesizing symmetric Boolean functions with reversible logic gates. In contrast to earlier approaches, the proposed technique deploys a simple, regular, and cascaded structure consisting of an array of Peres and CNOT gates, which results in significant reduction with respect to the quantum cost. However, the number of circuit inputs may increase slightly when such cascades are used. In order to reduce their number, we next propose a postsynthesis optimization phase that allows judicious reuse of circuit lines. In addition to offering a cost-effective synthesis methodology, the proposed reversible logic structure supports elegant testability properties. With respect to all single or partial missing gate faults (SMGFs and PMGFs), or repeated gate faults (RGFs) in such an n -input circuit module, we show that it admits a universal test set of constant cardinality (=3) for any value of n . Thus, considering both the cost and testability issues, this approach provides a superior option for synthesizing symmetric functions compared to existing designs.

ACM Journal on Emerging Technologies in Computing Systems•Jun 27, 2016•4 citations

Modular Design for Symmetric Functions Using Quantum Quaternary Logic

Arighna Deb, Debesh Kumar Das, Susmita Sur‐Kolay

In this paper, we propose a method to realize symmetric binary functions as quaternary quantum/reversible circuits. In contrast to the existing binary synthesis methods, our design in quaternary domain offers a simple and regular cascade structure composed of quaternary quantum modules which enables significant reductions with respect to number of lines, levels and quantum costs. Further, a method to obtain an optimal realization is presented, this uses a few special quaternary quantum modules of low quantum cost. Experimental results confirm that our new method leads to realizations in quaternary domain with a significant reduction in number of lines, levels and quantum cost compared to the existing approaches in binary domain. Hence, our design in quaternary logic offers a useful alternative to existing designs in binary logic for realizing symmetric functions.

International Symposium on Electronic System Design•Dec 1, 2013•1 citation

Efficient reversible and quantum implementations of symmetric Boolean functions

D. Maslov

It is a well-known fact in logic design that synthesis of some special classes of Boolean functions is often easier than the synthesis of a general unrestricted specification. In reversible logic, well-scaled synthesis methods with a reasonably small cost of the associated implementation have been found for only a few classes of functions. This includes synthesis of multiple-output symmetric and reversible linear functions. The author presents an efficient reversible/quantum synthesis method for the class of multiple-output symmetric functions. The method is purely theoretical, therefore its scaling on functions with a large number of inputs/outputs requires minimal resources. The author calculates garbage, i.e. the number of outputs that are not required by the function specification, the number of reversible gates, and the quantum cost of the presented implementations. The proposed approach is then applied to the synthesis of benchmark functions. Comparison of the designs to the previously reported implementations is favourable.

IEE Proceedings - Circuits Devices and Systems•Jan 1, 2006•16 citations

Regular realization of symmetric functions using reversible logic

Marek A. Perkowski, Paweł Kerntopf, Andrzej Buller +7 more

Reversible logic is of increasing importance to many future computer technologies. We introduce a regular structure to realize symmetric functions in binary reversible logic. This structure, called a 2*2 net structure, allows for a more efficient realization of symmetric functions than the methods introduced by the other authors. Our synthesis method allows us to realize arbitrary symmetric function in a completely regular structure of reversible gates with relatively little "garbage". Because every Boolean function can be made symmetric by repeating input variables, our method is applicable to arbitrary multi-input multi-output Boolean functions and realizes such arbitrary function in a circuit with a relatively small number of additional gate outputs. The method can also be used in classical logic. Its advantages in terms of numbers of gates and inputs/outputs are especially seen for symmetric or incompletely specified functions with many outputs.

Euromicro Conference on Digital System Design (DSD)•Nov 13, 2002•51 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

Compact Quantum Circuits for Dimension Reducible Functions

Anna Bernasconi, Valentina Ciriani, Asma Taheri Monfared +1 more

The classical synthesis method for quantum oracles generally requires a reversible logic synthesis and a quantum compilation step. In the reversible logic synthesis it is important to obtain a compact reversible circuit in order to minimize the quantum cost of the final quantum circuit. In this paper, we exploit function regularities for enabling efficient reversible syn-thesis. In particular, we propose and implement a new method for the quantum synthesis of Dimension reducible Boolean functions. The experimental results validate the proposed approach showing relevant gains in area.

Euromicro Conference on Digital System Design (DSD)•Sep 6, 2023•1 citation
In this paper, we introduce a new method to realize symmetric Boolean functions with reversible logic based on unate decomposition. In contrast to earlier synthesis methods, our solution uses a simpler circuit structure of reversible gates, which enables a significant reduction with respect to quantum cost. The resulting design offers an improved solution to reversible synthesis of symmetric Boolean functions.
In this article, we introduce a novel method of synthesizing symmetric Boolean functions with reversible logic gates. In contrast to earlier approaches, the proposed technique deploys a simple, regular, and cascaded structure consisting of an array of Peres and CNOT gates, which results in significant reduction with respect to the quantum cost. However, the number of circuit inputs may increase slightly when such cascades are used. In order to reduce their number, we next propose a postsynthesis optimization phase that allows judicious reuse of circuit lines. In addition to offering a cost-effective synthesis methodology, the proposed reversible logic structure supports elegant testability properties. With respect to all single or partial missing gate faults (SMGFs and PMGFs), or repeated gate faults (RGFs) in such an n -input circuit module, we show that it admits a universal test set of constant cardinality (=3) for any value of n . Thus, considering both the cost and testability issues, this approach provides a superior option for synthesizing symmetric functions compared to existing designs.
In this paper, we propose a method to realize symmetric binary functions as quaternary quantum/reversible circuits. In contrast to the existing binary synthesis methods, our design in quaternary domain offers a simple and regular cascade structure composed of quaternary quantum modules which enables significant reductions with respect to number of lines, levels and quantum costs. Further, a method to obtain an optimal realization is presented, this uses a few special quaternary quantum modules of low quantum cost. Experimental results confirm that our new method leads to realizations in quaternary domain with a significant reduction in number of lines, levels and quantum cost compared to the existing approaches in binary domain. Hence, our design in quaternary logic offers a useful alternative to existing designs in binary logic for realizing symmetric functions.
It is a well-known fact in logic design that synthesis of some special classes of Boolean functions is often easier than the synthesis of a general unrestricted specification. In reversible logic, well-scaled synthesis methods with a reasonably small cost of the associated implementation have been found for only a few classes of functions. This includes synthesis of multiple-output symmetric and reversible linear functions. The author presents an efficient reversible/quantum synthesis method for the class of multiple-output symmetric functions. The method is purely theoretical, therefore its scaling on functions with a large number of inputs/outputs requires minimal resources. The author calculates garbage, i.e. the number of outputs that are not required by the function specification, the number of reversible gates, and the quantum cost of the presented implementations. The proposed approach is then applied to the synthesis of benchmark functions. Comparison of the designs to the previously reported implementations is favourable.
Reversible logic is of increasing importance to many future computer technologies. We introduce a regular structure to realize symmetric functions in binary reversible logic. This structure, called a 2*2 net structure, allows for a more efficient realization of symmetric functions than the methods introduced by the other authors. Our synthesis method allows us to realize arbitrary symmetric function in a completely regular structure of reversible gates with relatively little "garbage". Because every Boolean function can be made symmetric by repeating input variables, our method is applicable to arbitrary multi-input multi-output Boolean functions and realizes such arbitrary function in a circuit with a relatively small number of additional gate outputs. The method can also be used in classical logic. Its advantages in terms of numbers of gates and inputs/outputs are especially seen for symmetric or incompletely specified functions with many outputs.
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.
The classical synthesis method for quantum oracles generally requires a reversible logic synthesis and a quantum compilation step. In the reversible logic synthesis it is important to obtain a compact reversible circuit in order to minimize the quantum cost of the final quantum circuit. In this paper, we exploit function regularities for enabling efficient reversible syn-thesis. In particular, we propose and implement a new method for the quantum synthesis of Dimension reducible Boolean functions. The experimental results validate the proposed approach showing relevant gains in area.