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

IEEE International Conference on VLSI Systems, Architecture, Technology and Applications (VLSI SATA)

Quantum cost realization of new reversible gates with transformation based synthesis technique

H. V. Jayashree, V.K. Agrawal, Shishir Bharadwaj N

Published Jan 1, 2015• 0 citations
Publisher

Abstract

Reversible computing appears to be promising due its applications in emerging technologies. To compute any reversible function it is necessary to build the system with reversible gates. Simplified version of transformation technique [3,5] to synthesize new reversible gates with Fredkin and Toffoli gates network is presented in this paper. Basic and bidirectional transformation algorithms with an example are illustrated, which uncovers every step of the algorithm. The same example is used for both the algorithms to give clarity on the difference in the efficiency of the algorithms. Simple pseudo code is also presented to illustrate the steps of the algorithm. The best quantum cost obtained is listed in this paper.

DOI
10.1109/vlsi-sata.2015.7050491

Related papers

Post synthesis optimization of reversible logic functions with extended template matching

H. V. Jayashree, V.K. Agrawal, N Shishir Bharadwaj

Research affinity towards Reversible Computing is increasing day to day due to its lower energy dissipation computing capability. To evaluate any reversible function it is necessary to build the system with reversible gates. In view of this there are many new reversible logic gates proposed by many authors. Quantum cost of few reversible gates are unpublished. Simplified version of transformation technique to synthesize new reversible gates with Fredkin and Toffoli gates network are presented in this paper. Post synthesis optimization with the new set of templates are carried out to reduce the Quantum cost.

International Conference on Circuits, Control, Communication and Computing (I4C)•Nov 1, 2014•1 citation

Fredkin/Toffoli templates for reversible logic synthesis

D. Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified-they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously.

International Conference on Computer Aided Design•May 13, 2004•23 citations

Reversible Logic Synthesis of Networks of Positive/Negative Control Gates

Wenying Zhu, Zhijin Guan, Yueqing Hang

The research in reversible logic has been attracted in recent years. It has applications in quantum computing, low-power CMOS design and nanotechnology. Many methods on how to cascade a reversible network have been proposed. And all these networks are composed of Toffoli/Fredkin gates. In this paper, we present a method that synthesizes a network with family of Positive/Negative Control (PNC) gates. Through introducing some examples for 3×3 reversible functions, and comparing with the network which is composed of Toffoli gates, the results show that introducing the PNC gates can produce an improvement for the number of gates in the reversible network, and have an advantage in reducing the cost of network.

International Conference on Natural Computation (ICNC)•Jan 1, 2009•2 citations

Synthesis of quantum arrays with low quantum costs from Kronecker Functional Lattice Diagrams

Dipal Shah, Marek A. Perkowski

Reversible logic has many applications such as Quantum computing, low power CMOS circuit design, Optical computing. Hence reversible logic synthesis has attracted attention especially in quantum computing community. A logic function is reversible if it is a one-to-one mapping between input and output vectors. In this paper we present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams. Unlike other contemporary algorithms for synthesis of reversible function that use n × n Toffoli gates, our method invariably synthesizes functions using only 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost. Our method adds small cost by adding extra ancilla bits. Moreover, our circuits are always (4-neighbors) regular, which is an asset when they are mapped to 2-Dimensional arrays in Ion Trap (quantum) technology.

IEEE Congress on Evolutionary Computation (CEC)•Jul 1, 2010•4 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

Efficient Three Variables Reversible Logic Synthesis Using Mixed-polarity Toffoli Gate

Chua Shin Cheng, Ashutosh Kumar Singh, Lenin Gopal

In this paper, we present an efficient reversible logic synthesis algorithm that uses Toffoli and mixed-polarity based Toffoli gate. In this paper, we propose an algorithm to synthesizereversible function in their positive-polarity Reed Muller (PPRM) expansion and usethe Hamming Distance (HD) approach to select suitable transformation path. Once a transformation path is defined, suitable gates for substitution are selected through the gate matching factor and reduction is performed. The algorithm does not generate any extra lines and thus keeping the synthesized function in its simplest form. The algorithm target on efficient way to synthesize three variables based reversible function into a cascade of Toffoli and mixed-polarity based Toffoli gate in term of quantum cost and gate count. Experimental results showthat the proposed algorithm is efficient in terms of the realization of all three variable based reversible functions.

Procedia Computer Science•Jan 1, 2015•16 citations
Reversible computing appears to be promising due its applications in emerging technologies. To compute any reversible function it is necessary to build the system with reversible gates. Simplified version of transformation technique [3,5] to synthesize new reversible gates with Fredkin and Toffoli gates network is presented in this paper. Basic and bidirectional transformation algorithms with an example are illustrated, which uncovers every step of the algorithm. The same example is used for both the algorithms to give clarity on the difference in the efficiency of the algorithms. Simple pseudo code is also presented to illustrate the steps of the algorithm. The best quantum cost obtained is listed in this paper.
Research affinity towards Reversible Computing is increasing day to day due to its lower energy dissipation computing capability. To evaluate any reversible function it is necessary to build the system with reversible gates. In view of this there are many new reversible logic gates proposed by many authors. Quantum cost of few reversible gates are unpublished. Simplified version of transformation technique to synthesize new reversible gates with Fredkin and Toffoli gates network are presented in this paper. Post synthesis optimization with the new set of templates are carried out to reduce the Quantum cost.
Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified-they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously.
The research in reversible logic has been attracted in recent years. It has applications in quantum computing, low-power CMOS design and nanotechnology. Many methods on how to cascade a reversible network have been proposed. And all these networks are composed of Toffoli/Fredkin gates. In this paper, we present a method that synthesizes a network with family of Positive/Negative Control (PNC) gates. Through introducing some examples for 3×3 reversible functions, and comparing with the network which is composed of Toffoli gates, the results show that introducing the PNC gates can produce an improvement for the number of gates in the reversible network, and have an advantage in reducing the cost of network.
Reversible logic has many applications such as Quantum computing, low power CMOS circuit design, Optical computing. Hence reversible logic synthesis has attracted attention especially in quantum computing community. A logic function is reversible if it is a one-to-one mapping between input and output vectors. In this paper we present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams. Unlike other contemporary algorithms for synthesis of reversible function that use n × n Toffoli gates, our method invariably synthesizes functions using only 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost. Our method adds small cost by adding extra ancilla bits. Moreover, our circuits are always (4-neighbors) regular, which is an asset when they are mapped to 2-Dimensional arrays in Ion Trap (quantum) technology.
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.
In this paper, we present an efficient reversible logic synthesis algorithm that uses Toffoli and mixed-polarity based Toffoli gate. In this paper, we propose an algorithm to synthesizereversible function in their positive-polarity Reed Muller (PPRM) expansion and usethe Hamming Distance (HD) approach to select suitable transformation path. Once a transformation path is defined, suitable gates for substitution are selected through the gate matching factor and reduction is performed. The algorithm does not generate any extra lines and thus keeping the synthesized function in its simplest form. The algorithm target on efficient way to synthesize three variables based reversible function into a cascade of Toffoli and mixed-polarity based Toffoli gate in term of quantum cost and gate count. Experimental results showthat the proposed algorithm is efficient in terms of the realization of all three variable based reversible functions.