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

Dynamic Programming Algorithms as Reversible Circuits: Symmetric Function Realization

Dmitri Maslov

Published Jan 1, 2002• 2 citations
OpenAlex

Abstract

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.

Related papers

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

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

Reversible logic synthesis based on a modified tabulation method

Chin-Yung Lu, Shiou-An Wang

An important property of reversible circuits is that they can reduce the energy consumption which is now a big problem for the advanced circuit design. If a circuit is reversible, it can reduce the energy consumption caused by information loss. The tabulation method is more efficient than other simplification methods for combination logic circuits. But the classical tabulation method is not directly applicable to reversible circuits because the basic logic gates, except the NOT gate, are not reversible gates. In this paper, we propose a method to solve the problem so that the tabulation method can be applied to the reversible circuit synthesis. Our algorithm provides a systematic method to simplify the reversible circuit. This can produce the resulting expression in exclusive-sum form and transform it into a final reversible circuit with lower quantum cost. Moreover, we can realize permutations to be reversible circuits with lower quantum cost and without unnecessary garbage bits. We can also convert irreversible circuits by adding qubits to make the circuits reversible. The experimental results show that the average saving in quantum cost is 15.82% compared with previous approaches.

International Conference on Multimedia Technology (ICMT)•Jul 1, 2011•3 citations

An extension of transformation-based reversible and quantum circuit synthesis

Mathias Soeken, Gerhard W. Dueck, Md. Mazder Rahman +1 more

Transformation-based synthesis is a well established systematic approach to determine a circuit implementation from a reversible function specification. Due to the inherent bidirectionality of reversible circuits the basic method can be applied in a bidirectional manner. In the approaches to date, gates are added either to the input side or the output side of the circuit on each iteration. I n this paper, we introduce a new variation where gates may be added at both ends during a single iteration when this is advantageous to reducing the cost of the circuit. Experimental results show the advantage of the new approach over previous transformation-based synthesis methods and that the additional computation is justified by the possibility of improved circuit costs.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2016•12 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

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•107 citations
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.
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.
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.
An important property of reversible circuits is that they can reduce the energy consumption which is now a big problem for the advanced circuit design. If a circuit is reversible, it can reduce the energy consumption caused by information loss. The tabulation method is more efficient than other simplification methods for combination logic circuits. But the classical tabulation method is not directly applicable to reversible circuits because the basic logic gates, except the NOT gate, are not reversible gates. In this paper, we propose a method to solve the problem so that the tabulation method can be applied to the reversible circuit synthesis. Our algorithm provides a systematic method to simplify the reversible circuit. This can produce the resulting expression in exclusive-sum form and transform it into a final reversible circuit with lower quantum cost. Moreover, we can realize permutations to be reversible circuits with lower quantum cost and without unnecessary garbage bits. We can also convert irreversible circuits by adding qubits to make the circuits reversible. The experimental results show that the average saving in quantum cost is 15.82% compared with previous approaches.
Transformation-based synthesis is a well established systematic approach to determine a circuit implementation from a reversible function specification. Due to the inherent bidirectionality of reversible circuits the basic method can be applied in a bidirectional manner. In the approaches to date, gates are added either to the input side or the output side of the circuit on each iteration. I n this paper, we introduce a new variation where gates may be added at both ends during a single iteration when this is advantageous to reducing the cost of the circuit. Experimental results show the advantage of the new approach over previous transformation-based synthesis methods and that the additional computation is justified by the possibility of improved circuit costs.
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 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.