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 Nanotechnology (IEEE-NANO)

An approach to quantum cost optimization in reversible circuits

Marek Szyprowski, Paweł Kerntopf

Published Aug 1, 2011• 18 citations
Publisher

Abstract

Recently, one of the main criteria used to evaluate reversible circuit designs is quantum cost. In this paper, an approach to reducing quantum cost of small-width reversible circuits is presented. Using our tool we have shown that for known benchmarks as well as designs taken from recent publications it is possible to obtain substantial savings in quantum cost (35% on average for 4-input benchmarks). It is also shown that quantum cost of 5-input circuits can be reduced using the same tool.

DOI
10.1109/nano.2011.6144568

Related papers

Reducing Quantum Cost in Reversible Toffoli Circuits

Marek Szyprowski, Paweł Kerntopf

Recently, reversible circuit synthesis has been intensively studied. One of the problems that has not been solved for a long time was exact minimization of gate count (GC) in 4-bit circuits. Finally, last year a tool of practical usage for finding optimal gate count Toffoli networks for any 4-variable function was developed. However, not much work has been done yet on exact minimization of quantum cost (QC) in 4-bit circuits. This paper presents an application of the above mentioned tool to reducing QC of 4-bit reversible circuits. It is shown that for benchmarks and for designs taken from recent publications it is possible to obtain savings in QC of up to 74% comparing with previously known circuits.

arXiv:1105.5831•May 29, 2011•29 citations

Two-Qubit Quantum Gates to Reduce the Quantum Cost of Reversible Circuit

Md. Mazder Rahman, Anindita Banerjee, Gerhard W. Dueck +1 more

This paper presents a quantum gate library that consists of all possible two-qubit quantum gates which do not produce entangled states. The quantum cost of each two-qubit gate in the proposed library is one. Therefore, these gates can be used to reduce the quantum costs of reversible circuits. Experimental results show a significant reduction of quantum cost in benchmark circuits. The resulting circuits could be further optimized with existing tools, such as quantum template matching.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2011•23 citations

Technology mapping and optimization for reversible and quantum circuits

Zahra Sasanian

Quantum information processing is of interest as it offers the potential for a new generation of very powerful computers supporting novel computational paradigms. Over the last couple of decades, different aspects of quantum computers ranging from quantum algorithms to quantum physical design have received growing attention. One of the most important research areas is the synthesis and post-synthesis optimization of reversible and quantum circuits. Many synthesis and optimization approaches can be found in the literature, yet, due to the complexity of the problem, finding approaches leading to optimal, or near optimal, results is still an open problem. The synthesized circuits are usually evaluated based on quantum cost models. Therefore, they are often technology mapped to circuits of more primitive gates. To this end, various technology mapping approaches have also been proposed in the past few years. Related work shows an existing gap in optimized technology mapping for reversible and quantum circuits. In this dissertation, an optimized technology mapping design flow is introduced for mapping reversible circuits to quantum circuits. The contributions of this dissertation are classified as follows: - New reversible circuit optimization methods. - Optimized reversible to quantum mapping approaches. - New quantum gate libraries and new cost models for reversible gates based on the new libraries. - Quantum circuit optimization approaches. The steps above, form an optimized flow for mapping reversible circuits to quantum circuits. At each step of the design flow optimized and consistent approaches are suggested with the goal of reducing the quantum cost of the synthesized reversible circuits. The evaluations show that the proposed mapping methodology leads to significant improvement in the quantum cost of the existing benchmark circuits.

•Jan 1, 2012•14 citations

An Efficient Reduction of Common Control Lines for Reversible Circuit Optimization

Arighna Deb, Robert Wille, Rolf Drechsler +1 more

New prospects in several emerging technologies such as quantum computation and certain aspects of low-power design motivated an intensive consideration of the design of reversible circuits. Since most of the existing synthesis approaches usually generate circuits of high costs, post-synthesis optimization is frequently applied. Here, the reduction of control line connections is a major focus as they are a main reason for high quantum costs in the respective reversible circuits. Previous approaches aimed for exploiting so-called common control lines for this purpose. However, while these solutions indeed lead to substantial improvements in the costs, they inherit some drawbacks and restrictions. In this work, we propose an alternative approach for the reduction of common control lines in reversible circuits, which (1) is based in the concepts of previously proposed solutions, but (2) combines them in a new fashion. This enables us to achieve the same or even better improvements, while - at the same time - overcome their drawbacks. Experimental evaluations confirm these benefits, i.e. significant improvements compared to the previous methods can often be achieved without the need to deal with their drawbacks.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2015•5 citations

A Study of Optimal 4-bit Reversible Circuit Synthesis from Mixed-Polarity

Toffoli Gates, Marek Szyprowski, Pawel Kerntopfi

Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (Le. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.

•Jan 1, 2012•0 citations

A novel optimization method for reversible logic circuit minimization

Matthew A. Morrison, Nagarajan Ranganathan

Programmable reversible logic is emerging as a prospective logic design style for implementation in modern nanotechnology and quantum computing with minimal impact on circuit heat generation. Recent advances in reversible logic using and quantum computer algorithms allow for improved computer architecture and arithmetic logic unit designs. We present an optimization method for reversible logic synthesis based on the Integrated Qubit (IQ) library. This method works in conjunction with existing methods to further improve quantum cost and delay of a synthesized reversible logic circuit. This algorithm runs in O(N) time, and reduces the quantum cost of synthesized circuit by up to 45 percent. In addition, the process of replacing the gates in the synthesized circuits with IQ gates uses a locally optimal technique whose major benefits include reduction of cost as well as delay.

IEEE Computer Society Annual Symposium on VLSI•Aug 1, 2013•14 citations
Recently, one of the main criteria used to evaluate reversible circuit designs is quantum cost. In this paper, an approach to reducing quantum cost of small-width reversible circuits is presented. Using our tool we have shown that for known benchmarks as well as designs taken from recent publications it is possible to obtain substantial savings in quantum cost (35% on average for 4-input benchmarks). It is also shown that quantum cost of 5-input circuits can be reduced using the same tool.
Recently, reversible circuit synthesis has been intensively studied. One of the problems that has not been solved for a long time was exact minimization of gate count (GC) in 4-bit circuits. Finally, last year a tool of practical usage for finding optimal gate count Toffoli networks for any 4-variable function was developed. However, not much work has been done yet on exact minimization of quantum cost (QC) in 4-bit circuits. This paper presents an application of the above mentioned tool to reducing QC of 4-bit reversible circuits. It is shown that for benchmarks and for designs taken from recent publications it is possible to obtain savings in QC of up to 74% comparing with previously known circuits.
Quantum information processing is of interest as it offers the potential for a new generation of very powerful computers supporting novel computational paradigms. Over the last couple of decades, different aspects of quantum computers ranging from quantum algorithms to quantum physical design have received growing attention. One of the most important research areas is the synthesis and post-synthesis optimization of reversible and quantum circuits. Many synthesis and optimization approaches can be found in the literature, yet, due to the complexity of the problem, finding approaches leading to optimal, or near optimal, results is still an open problem. The synthesized circuits are usually evaluated based on quantum cost models. Therefore, they are often technology mapped to circuits of more primitive gates. To this end, various technology mapping approaches have also been proposed in the past few years. Related work shows an existing gap in optimized technology mapping for reversible and quantum circuits. In this dissertation, an optimized technology mapping design flow is introduced for mapping reversible circuits to quantum circuits. The contributions of this dissertation are classified as follows: - New reversible circuit optimization methods. - Optimized reversible to quantum mapping approaches. - New quantum gate libraries and new cost models for reversible gates based on the new libraries. - Quantum circuit optimization approaches. The steps above, form an optimized flow for mapping reversible circuits to quantum circuits. At each step of the design flow optimized and consistent approaches are suggested with the goal of reducing the quantum cost of the synthesized reversible circuits. The evaluations show that the proposed mapping methodology leads to significant improvement in the quantum cost of the existing benchmark circuits.
New prospects in several emerging technologies such as quantum computation and certain aspects of low-power design motivated an intensive consideration of the design of reversible circuits. Since most of the existing synthesis approaches usually generate circuits of high costs, post-synthesis optimization is frequently applied. Here, the reduction of control line connections is a major focus as they are a main reason for high quantum costs in the respective reversible circuits. Previous approaches aimed for exploiting so-called common control lines for this purpose. However, while these solutions indeed lead to substantial improvements in the costs, they inherit some drawbacks and restrictions. In this work, we propose an alternative approach for the reduction of common control lines in reversible circuits, which (1) is based in the concepts of previously proposed solutions, but (2) combines them in a new fashion. This enables us to achieve the same or even better improvements, while - at the same time - overcome their drawbacks. Experimental evaluations confirm these benefits, i.e. significant improvements compared to the previous methods can often be achieved without the need to deal with their drawbacks.
Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (Le. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.
Programmable reversible logic is emerging as a prospective logic design style for implementation in modern nanotechnology and quantum computing with minimal impact on circuit heat generation. Recent advances in reversible logic using and quantum computer algorithms allow for improved computer architecture and arithmetic logic unit designs. We present an optimization method for reversible logic synthesis based on the Integrated Qubit (IQ) library. This method works in conjunction with existing methods to further improve quantum cost and delay of a synthesized reversible logic circuit. This algorithm runs in O(N) time, and reduces the quantum cost of synthesized circuit by up to 45 percent. In addition, the process of replacing the gates in the synthesized circuits with IQ gates uses a locally optimal technique whose major benefits include reduction of cost as well as delay.