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

Theoretical Computer Science

Realization and synthesis of reversible functions

Guowu Yang, Fei Xie, William N. N. Hung, Xiaoyu Song B, Marek A. Perkowski

Published Nov 30, 2010• 9 citations
Publisher
DOI
10.1016/j.tcs.2010.11.031

Related papers

Synthesis of reversible logic

Md. Mazder Rahman

•Jan 1, 2014•1 citation

Reversible Logic Synthesis with Output Permutation

Robert Wille, Daniel J. Grosse, Gerhard W. Dueck +1 more

Synthesis of reversible logic has become a very important research area. In recent years several algorithms--heuristic as well as exact ones--have been introduced in this area. Typically, they use the specification of a reversible function in terms of a truth table as input. Here, the position of the outputs are fixed. However, in general it is irrelevant, how the respective outputs are ordered. Thus, a synthesis methodology is proposed that determines for a given reversible function an equivalent circuit realization modulo output permutation. More precisely, the result of the synthesis process is a circuit realization whose output functions have been permuted in comparison to the original specification and the respective permutation vector. We show that this synthesis methodology may lead to significant smaller realizations. We apply Synthesis with Output Permutation (SWOP) to both, an exact and a heuristic synthesis algorithm. As our experiments show using the new synthesis paradigm leads to multiple control Toffoli networks that are smaller than the currently best known realizations.

International Conference on VLSI Design•Jan 1, 2009•51 citations

Synthesis of Boolean Functions in Reversible Logic

Robert Wille, Rolf Drechsler

Synthesis lectures on digital circuits and systems•Jan 1, 2010•6 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

Classical and Reversible Computation

Osama M. Raisuddin, Suvranu De

Springer eBooks•Nov 14, 2025•0 citations

Quantum cost realization of new reversible functions using ESOP based synthesis

H. V. Jayashree, V.K. Agrawal, Deepika Kumari

Research in Reversible Logic Synthesis is progressing due to its application in quantum computing, low power applications, DNA computing. Reversible computing is efficient in terms of saving power compared to irreversible computing. The work presented here is an attempt to illustrate the shared cube synthesis proposed by N. M. Nayeem et. al with pseudocode. Stepwise demonstration is illustrated with reversible function not considered in the original work. Pseudocode is verified against benchmark reversible functions. The algorithm is experimented on new reversible functions in order to realize quantum diagram, quantum cost, gate count and garbage outputs.

International Conference on Contemporary Computing and Informatics (IC3I)•Nov 1, 2014•0 citations
Synthesis of reversible logic has become a very important research area. In recent years several algorithms--heuristic as well as exact ones--have been introduced in this area. Typically, they use the specification of a reversible function in terms of a truth table as input. Here, the position of the outputs are fixed. However, in general it is irrelevant, how the respective outputs are ordered. Thus, a synthesis methodology is proposed that determines for a given reversible function an equivalent circuit realization modulo output permutation. More precisely, the result of the synthesis process is a circuit realization whose output functions have been permuted in comparison to the original specification and the respective permutation vector. We show that this synthesis methodology may lead to significant smaller realizations. We apply Synthesis with Output Permutation (SWOP) to both, an exact and a heuristic synthesis algorithm. As our experiments show using the new synthesis paradigm leads to multiple control Toffoli networks that are smaller than the currently best known 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.
Research in Reversible Logic Synthesis is progressing due to its application in quantum computing, low power applications, DNA computing. Reversible computing is efficient in terms of saving power compared to irreversible computing. The work presented here is an attempt to illustrate the shared cube synthesis proposed by N. M. Nayeem et. al with pseudocode. Stepwise demonstration is illustrated with reversible function not considered in the original work. Pseudocode is verified against benchmark reversible functions. The algorithm is experimented on new reversible functions in order to realize quantum diagram, quantum cost, gate count and garbage outputs.