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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Dynamic programming algorithms as quantum circuits: symmetric function realization

Dmitri A. Maslov

Published Aug 24, 2004• 3 citations
Publisher

Abstract

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.

DOI
10.1117/12.541792

Related papers

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

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

Cayley graphs and analysis of quantum cost for reversible circuit synthesis

A.C. Ribeiro, Celina M.H. de Figueiredo, Franklin de Lima Marquezino +1 more

We propose the theory of Cayley graphs as a framework to analyse gate counts and quantum costs resulting from reversible circuit synthesis. Several methods have been proposed in the reversible logic synthesis literature by considering different libraries whose gates are associated to the generating sets of certain Cayley graphs. In a Cayley graph, the distance between two vertices corresponds to the optimal circuit size. The lower bound for the diameter of Cayley graphs is also a lower bound for the worst case for any algorithm that uses the corresponding gate library. In this paper, we study two Cayley graphs on the Symmetric Group $S_{2^n}$: the first, denoted by $I_n$, is defined by a generating set associated to generalized Toffoli gates; and the second, the hypercube Cayley graph $H_n$, is defined by a generating set associated to multiple-control Toffoli gates. Those two Cayley graphs have degree $n2^{n-1}$ and order $2^n!$. Maslov, Dueck and Miller proposed a reversible circuit synthesis that we model by the Cayley graph $I_n$. We propose a synthesis algorithm based on the Cayley graph $H_n$ with upper bound of $(n-1)2^{n}+1$ multiple-control Toffoli gates. In addition, the diameter of the Cayley graph $H_n$ gives a lower bound of $n2^{n-1}$.

arXiv:1209.3275•Sep 14, 2012•2 citations

Synthesis of Quantum Arrays from Kronecker Functional Lattice Diagrams

Martin Lukáč, Dipal Shah, Marek A. Perkowski +1 more

Reversible logic is becoming more and more popular due to the fact that many novel technologies such as quantum computing, low power CMOS circuit design or quantum optical computing are becoming more and more realistic. In quantum computing, reversible computing is the main venue for the realization and design of classical functions and circuits. We present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams (KFLD). Unlike many of contemporary algorithms for synthesis of reversible functions that use n×n Toffoli gates, our method synthesizes functions using 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost of the designed circuit but adds additional ancilla bits. The resulting circuits are always regular in a 4-neighbor model and all connections are predictable. Consequently resulting circuits can be directly mapped in to a quantum device such as quantum FPGA [14]. This is a significant advantage of our method, as it allows us to design optimum circuits for a given quantum technology.

IEICE Transactions on Information and Systems•Jan 1, 2014•3 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

Pairwise decomposition of toffoli gates in a quantum circuit

Nathan O. Scott, Gerhard W. Dueck

Quantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are physical barriers to implementing large quantum gates. Large Toffoli gates can be decomposed into equivalent sets of smaller, quantum elementary gates. The cost of a quantum circuit can be measured by counting the number of elementary gates in the circuit after all gates have been decomposed. Traditionally this decomposition is done independently for each gate in the circuit. This thesis identifies pairs of gates that, if decomposed together, result in fewer total elementary gates than they would otherwise. These improvements are incorporated into a simple decomposition algorithm which manipulates the circuit in order to search for such pairs. The decomposition algorithm is compared to a naive implementation, and the resulting gate costs are presented and compared.

ACM Great Lakes Symposium on VLSI (GLSVLSI)•May 4, 2008•13 citations
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.
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.
We propose the theory of Cayley graphs as a framework to analyse gate counts and quantum costs resulting from reversible circuit synthesis. Several methods have been proposed in the reversible logic synthesis literature by considering different libraries whose gates are associated to the generating sets of certain Cayley graphs. In a Cayley graph, the distance between two vertices corresponds to the optimal circuit size. The lower bound for the diameter of Cayley graphs is also a lower bound for the worst case for any algorithm that uses the corresponding gate library. In this paper, we study two Cayley graphs on the Symmetric Group S2nS_{2^n}S2n​: the first, denoted by InI_nIn​, is defined by a generating set associated to generalized Toffoli gates; and the second, the hypercube Cayley graph HnH_nHn​, is defined by a generating set associated to multiple-control Toffoli gates. Those two Cayley graphs have degree n2n−1n2^{n-1}n2n−1 and order 2n!2^n!2n!. Maslov, Dueck and Miller proposed a reversible circuit synthesis that we model by the Cayley graph InI_nIn​. We propose a synthesis algorithm based on the Cayley graph HnH_nHn​ with upper bound of (n−1)2n+1(n-1)2^{n}+1(n−1)2n+1 multiple-control Toffoli gates. In addition, the diameter of the Cayley graph HnH_nHn​ gives a lower bound of n2n−1n2^{n-1}n2n−1.
Reversible logic is becoming more and more popular due to the fact that many novel technologies such as quantum computing, low power CMOS circuit design or quantum optical computing are becoming more and more realistic. In quantum computing, reversible computing is the main venue for the realization and design of classical functions and circuits. We present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams (KFLD). Unlike many of contemporary algorithms for synthesis of reversible functions that use n×n Toffoli gates, our method synthesizes functions using 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost of the designed circuit but adds additional ancilla bits. The resulting circuits are always regular in a 4-neighbor model and all connections are predictable. Consequently resulting circuits can be directly mapped in to a quantum device such as quantum FPGA [14]. This is a significant advantage of our method, as it allows us to design optimum circuits for a given quantum technology.
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.
Quantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are physical barriers to implementing large quantum gates. Large Toffoli gates can be decomposed into equivalent sets of smaller, quantum elementary gates. The cost of a quantum circuit can be measured by counting the number of elementary gates in the circuit after all gates have been decomposed. Traditionally this decomposition is done independently for each gate in the circuit. This thesis identifies pairs of gates that, if decomposed together, result in fewer total elementary gates than they would otherwise. These improvements are incorporated into a simple decomposition algorithm which manipulates the circuit in order to search for such pairs. The decomposition algorithm is compared to a naive implementation, and the resulting gate costs are presented and compared.