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

IEE Proceedings - Circuits Devices and Systems

Efficient reversible and quantum implementations of symmetric Boolean functions

D. Maslov

Published Jan 1, 2006• 17 citations
Publisher

Abstract

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.

DOI
10.1049/ip-cds:20045213

Related papers

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

Dynamic programming algorithms as quantum circuits: symmetric function realization

Dmitri A. Maslov

The work starts with a general idea of how to realize a dynamic programming algorithm as a quantum circuit. This realization is not tied to a specific design model, technology or a class of dynamic algorithms, it shows an approach for such synthesis. As an illustration of the efficiency of this approach, the class of all multiple-output symmetric functions is realized in a dynamic programming algorithm manner as a reversible circuit of Toffoli type elements (NOT, CNOT, and Toffoli gates). The garbage and quantum cost (found based on Barenco et al. paper) of the presented implementation are calculated and compared to the costs of previously described reversible synthesis methods. The summary of results of this comparison is as follows. The quantum cost of the proposed method is less than the quantum cost of any other reported systematic approach. The garbage is usually lower, except for comparison with the synthesis methods, whose primary goal is synthesis with theoretically minimal garbage. The presented algorithm application to the symmetric function synthesis results in circuits suitable for quantum technology realizations.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•4 citations

Reversible synthesis of symmetric boolean functions based on unate decomposition

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

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.

ACM Great Lakes Symposium on VLSI (GLSVLSI)•May 2, 2013•4 citations

Dynamic Programming Algorithms as Reversible Circuits: Symmetric Function Realization

Dmitri Maslov

The work starts with a general idea of how to realize a dynamic programming algorithm as a reversible circuit. This realization is not tied to a specific reversible design model and technology or a class of dynamic algorithms, it shows an approach for such synthesis. As an illustration of this approach, a class of all symmetric functions is realized in a dynamic programming algorithm manner as a reversible circuit of To#oli elements. The garbage, quantum and reversible costs of the presented implementation are calculated and compared to the costs of previously described reversible synthesis methods. The summary of results of this comparison is as follows. The quantum cost of the proposed method is better than the quantum cost of any other known systematic approach. The garbage is usually lower (except for comparison with the synthesis methods, primary goal of which is synthesis with theoretically minimal garbage). For the large functions reversible cost is better or has the same asymptotic that of other methods. Although the reversible cost comparison may not look beneficial for the small functions, the possible technological implementation (quantum) shows that it is beneficial to use the presented approach even for the small functions.

•Jan 1, 2002•2 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

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 30, 2006•371 citations
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.
The work starts with a general idea of how to realize a dynamic programming algorithm as a quantum circuit. This realization is not tied to a specific design model, technology or a class of dynamic algorithms, it shows an approach for such synthesis. As an illustration of the efficiency of this approach, the class of all multiple-output symmetric functions is realized in a dynamic programming algorithm manner as a reversible circuit of Toffoli type elements (NOT, CNOT, and Toffoli gates). The garbage and quantum cost (found based on Barenco et al. paper) of the presented implementation are calculated and compared to the costs of previously described reversible synthesis methods. The summary of results of this comparison is as follows. The quantum cost of the proposed method is less than the quantum cost of any other reported systematic approach. The garbage is usually lower, except for comparison with the synthesis methods, whose primary goal is synthesis with theoretically minimal garbage. The presented algorithm application to the symmetric function synthesis results in circuits suitable for quantum technology realizations.
The work starts with a general idea of how to realize a dynamic programming algorithm as a reversible circuit. This realization is not tied to a specific reversible design model and technology or a class of dynamic algorithms, it shows an approach for such synthesis. As an illustration of this approach, a class of all symmetric functions is realized in a dynamic programming algorithm manner as a reversible circuit of To#oli elements. The garbage, quantum and reversible costs of the presented implementation are calculated and compared to the costs of previously described reversible synthesis methods. The summary of results of this comparison is as follows. The quantum cost of the proposed method is better than the quantum cost of any other known systematic approach. The garbage is usually lower (except for comparison with the synthesis methods, primary goal of which is synthesis with theoretically minimal garbage). For the large functions reversible cost is better or has the same asymptotic that of other methods. Although the reversible cost comparison may not look beneficial for the small functions, the possible technological implementation (quantum) shows that it is beneficial to use the presented approach even for the small functions.
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.
Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25