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

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics

A Novel Algorithm for Reversible Circuit Optimization

Yi-Tzu Lo, Shu–Yu Kuo, Guo-Jyun Zeng, Yung-Che Tsai, Yao–Hsin Chou

Published Oct 1, 2015• 1 citation
Publisher

Abstract

Reversible circuit synthesis is an important field in quantum computing, low-power design, and reversible circuit. The problem of reversible circuit synthesis is complicated and hard to solve because the input of the reversible circuit will experience a huge increase when extended to multi-bit. In this paper, a novel algorithm of reversible circuit synthesis is proposed. With the satisfied priority of positions, we can efficiently select the position which should be satisfied, and each selected gate is generated to benefit the overall situation. Therefore, the proposed algorithm is able to optimize the reversible circuit with fewer gates and can be implemented in regard to multibit reversible circuit synthesis. In addition, the gate set we used contains only Toffoli, spanning all wires. This Toffoli gate is liable to be transformed into another gate set and is helpful for algorithm design. The experiment shows that the proposed algorithm, with efficient and optimal results, is superior to others.

DOI
10.1109/smc.2015.499

Related papers

A Novel Efficient Optimal Reversible Circuit Synthesis Algorithm

Yu-Shan Yang, Han-Kuan Chen, Shu–Yu Kuo +2 more

In quantum computing, the synthesis of reversible circuits is an important topic. Reversible circuit synthesis is particularly challenging because the complexity grows as the number of bits increases. To date, many reversible circuit synthesis algorithms have been proposed, but most are unable to find the optima within an acceptable time. Because traditional methods only consider partial interests, the resulting cost would be more gates. This paper proposes a novel method, called Bound Oriented Algorithm, which has the ability to find the optimal solution with a high hit rate, one greater than 75% on average. Moreover, with the prediction of the optima by bound, it can reduce excess calculation to further improve efficiency. In addition, a special library containing only Toffoli gates is used, which simplifies algorithm design and is more easily converted to a common library. The experiment result shows that the proposed method performs better than other methods in terms of solution quality and time cost.

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Oct 1, 2015•2 citations

A multi-commodity network model for optimal quantum reversible circuit synthesis

Jihye Jung, In-Chan Choi

Quantum computing is a newly emerging computing environment that has recently attracted intense research interest in improving the output fidelity, fully utilizing its high computing power from both hardware and software perspectives. In particular, several attempts have been made to reduce the errors in quantum computing algorithms through the efficient synthesis of quantum circuits. In this study, we present an application of an optimization model for synthesizing quantum circuits with minimum implementation costs to lower the error rates by forming a simpler circuit. Our model has a unique structure that combines the arc-subset selection problem with a conventional multi-commodity network flow model. The model targets the circuit synthesis with multiple control Toffoli gates to implement Boolean reversible functions that are often used as a key component in many quantum algorithms. Compared to previous studies, the proposed model has a unifying yet straightforward structure for exploiting the operational characteristics of quantum gates. Our computational experiment shows the potential of the proposed model, obtaining quantum circuits with significantly lower quantum costs compared to prior studies. The proposed model is also applicable to various other fields where reversible logic is utilized, such as low-power computing, fault-tolerant designs, and DNA computing. In addition, our model can be applied to network-based problems, such as logistics distribution and time-stage network problems.

PLoS ONE•Jun 22, 2021•3 citations

A Novel Hypercube-Based Heuristic for Quantum Boolean Circuit Synthesis

Yu-Chi Jiang, Kuo-Chun Tseng, Cheng-Yen Hua +3 more

Quantum computation has extraordinary capabilities for solving complicated problems. As quantum computations are reversible by nature, reversible circuits are important for the development of quantum computation techniques. Designing an effective and efficient method for synthesizing reversible circuits to reduce costs and stabilize circuit efficiency is crucial. The traditional synthesis methods of solving reversible circuits focus on the conversion efficiency rather than discussing the properties of the reversible function. Thus, this paper aims to propose a novel synthesis method that directly and efficiently optimizes reversible circuit synthesis with the properties of the reversible circuit. The proposed method converts the reversible function into a hypercube, allowing visual observations of the overall circuit. Two new indicators, the adjacent Hamming distance (AHD) and total cycle distance (TCD), aid in effective decision-making, generating shorter circuits. Furthermore, we use the generalized Toffoli gate set, which without requiring any additional ancilla bits and has applications in error correction and fault tolerance. The experimental results show that our method can find better solutions than traditional methods, significantly reducing the gate count, while the hypercube assists in synthesizing the reversible circuit.

IEEE Journal on Emerging and Selected Topics in Circuits and Systems•Aug 29, 2022•9 citations

Fast Synthesis of Reversible Circuits Using a Sorting Algorithm and Optimization.

Ömercan Susam, Mustafa Altun

This paper studies synthesis and optimization of reversible circuits composed of Toffoli gates with negative and positive control lines. The proposed synthesis algorithm performs sorting among optimal implementations of certain functions - called as essential functions - to implement any reversible Boolean function. Essential functions comprise very small amount of all functions. For example, to implement 3 bit circuits, 28 essential functions out of all 40320 functions are needed. The proposed optimization algorithm considers both reversible and quantum circuit costs. First, reversible cost is reduced by considering adjacent gate pairs. Then, inner quantum structures of the gates are investigated and quantum optimization is performed. The proposed algorithms are evaluated on benchmark circuits in comparison with the results in the literature.

J. Multiple Valued Log. Soft Comput.•Jan 1, 2017•4 citations

Reversible circuit optimization using modified toffoli templates

Mridula J Deshpande, H. V. Jayashree, V.K. Agrawal

Reversible gates are gaining popularity in the field of circuit synthesis due to their property of having lower power loss and reduced dissipation of power as heat. These low power design models need to have better optimization properties. In this paper, we have ventured into the template and rule based optimization process. While most reversible netlists are built using the standard Toffoli gates, the proposed Modified Toffoli Gate has been used to achieve optimization. In this paper, the quantum realization of mixed control Modified Toffoli Gate and negative control Modified Toffoli Gates are proposed. Few templates and rules for transforming the original Toffoli network to the Modified Toffoli network are also proposed. This optimization yields a better quantum cost and gate count when compared to that of it's Toffoli counterpart.

International Conference on Advances in Computing, Communications and Informatics (ICACCI)•Sep 1, 2017•0 citations

Post-Synthesis Optimization of Reversible Circuits

Edinelço Dalcumune, Luis Antônio Brasil Kowada, Celina M.H. de Figueiredo +1 more

One of the main motivations for reversible computing is that quantum computing has as one of its foundations the reversibility of all gates, that is, quantum computing circuit models are reversible. An important problem in reversible computing that has been intensively studied for the last decades is the synthesis of reversible circuits. The extended abstract considers optimization rules aiming to a new algorithm for post-synthesis optimization of reversible circuits composed of generalized Toffoli gates.

Anais do Encontro de Teoria da Computação (ETC)•Jul 16, 2021•0 citations
Reversible circuit synthesis is an important field in quantum computing, low-power design, and reversible circuit. The problem of reversible circuit synthesis is complicated and hard to solve because the input of the reversible circuit will experience a huge increase when extended to multi-bit. In this paper, a novel algorithm of reversible circuit synthesis is proposed. With the satisfied priority of positions, we can efficiently select the position which should be satisfied, and each selected gate is generated to benefit the overall situation. Therefore, the proposed algorithm is able to optimize the reversible circuit with fewer gates and can be implemented in regard to multibit reversible circuit synthesis. In addition, the gate set we used contains only Toffoli, spanning all wires. This Toffoli gate is liable to be transformed into another gate set and is helpful for algorithm design. The experiment shows that the proposed algorithm, with efficient and optimal results, is superior to others.
In quantum computing, the synthesis of reversible circuits is an important topic. Reversible circuit synthesis is particularly challenging because the complexity grows as the number of bits increases. To date, many reversible circuit synthesis algorithms have been proposed, but most are unable to find the optima within an acceptable time. Because traditional methods only consider partial interests, the resulting cost would be more gates. This paper proposes a novel method, called Bound Oriented Algorithm, which has the ability to find the optimal solution with a high hit rate, one greater than 75% on average. Moreover, with the prediction of the optima by bound, it can reduce excess calculation to further improve efficiency. In addition, a special library containing only Toffoli gates is used, which simplifies algorithm design and is more easily converted to a common library. The experiment result shows that the proposed method performs better than other methods in terms of solution quality and time cost.
Quantum computing is a newly emerging computing environment that has recently attracted intense research interest in improving the output fidelity, fully utilizing its high computing power from both hardware and software perspectives. In particular, several attempts have been made to reduce the errors in quantum computing algorithms through the efficient synthesis of quantum circuits. In this study, we present an application of an optimization model for synthesizing quantum circuits with minimum implementation costs to lower the error rates by forming a simpler circuit. Our model has a unique structure that combines the arc-subset selection problem with a conventional multi-commodity network flow model. The model targets the circuit synthesis with multiple control Toffoli gates to implement Boolean reversible functions that are often used as a key component in many quantum algorithms. Compared to previous studies, the proposed model has a unifying yet straightforward structure for exploiting the operational characteristics of quantum gates. Our computational experiment shows the potential of the proposed model, obtaining quantum circuits with significantly lower quantum costs compared to prior studies. The proposed model is also applicable to various other fields where reversible logic is utilized, such as low-power computing, fault-tolerant designs, and DNA computing. In addition, our model can be applied to network-based problems, such as logistics distribution and time-stage network problems.
Quantum computation has extraordinary capabilities for solving complicated problems. As quantum computations are reversible by nature, reversible circuits are important for the development of quantum computation techniques. Designing an effective and efficient method for synthesizing reversible circuits to reduce costs and stabilize circuit efficiency is crucial. The traditional synthesis methods of solving reversible circuits focus on the conversion efficiency rather than discussing the properties of the reversible function. Thus, this paper aims to propose a novel synthesis method that directly and efficiently optimizes reversible circuit synthesis with the properties of the reversible circuit. The proposed method converts the reversible function into a hypercube, allowing visual observations of the overall circuit. Two new indicators, the adjacent Hamming distance (AHD) and total cycle distance (TCD), aid in effective decision-making, generating shorter circuits. Furthermore, we use the generalized Toffoli gate set, which without requiring any additional ancilla bits and has applications in error correction and fault tolerance. The experimental results show that our method can find better solutions than traditional methods, significantly reducing the gate count, while the hypercube assists in synthesizing the reversible circuit.
This paper studies synthesis and optimization of reversible circuits composed of Toffoli gates with negative and positive control lines. The proposed synthesis algorithm performs sorting among optimal implementations of certain functions - called as essential functions - to implement any reversible Boolean function. Essential functions comprise very small amount of all functions. For example, to implement 3 bit circuits, 28 essential functions out of all 40320 functions are needed. The proposed optimization algorithm considers both reversible and quantum circuit costs. First, reversible cost is reduced by considering adjacent gate pairs. Then, inner quantum structures of the gates are investigated and quantum optimization is performed. The proposed algorithms are evaluated on benchmark circuits in comparison with the results in the literature.
Reversible gates are gaining popularity in the field of circuit synthesis due to their property of having lower power loss and reduced dissipation of power as heat. These low power design models need to have better optimization properties. In this paper, we have ventured into the template and rule based optimization process. While most reversible netlists are built using the standard Toffoli gates, the proposed Modified Toffoli Gate has been used to achieve optimization. In this paper, the quantum realization of mixed control Modified Toffoli Gate and negative control Modified Toffoli Gates are proposed. Few templates and rules for transforming the original Toffoli network to the Modified Toffoli network are also proposed. This optimization yields a better quantum cost and gate count when compared to that of it's Toffoli counterpart.
One of the main motivations for reversible computing is that quantum computing has as one of its foundations the reversibility of all gates, that is, quantum computing circuit models are reversible. An important problem in reversible computing that has been intensively studied for the last decades is the synthesis of reversible circuits. The extended abstract considers optimization rules aiming to a new algorithm for post-synthesis optimization of reversible circuits composed of generalized Toffoli gates.