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

Signal Processing and Communications Applications Conference (SIU)

Parallelization and performance analysis of reversible circuit synthesis

Ömercan Susam, Şuayb S. Arslan

Published May 1, 2018• 0 citations
Publisher

Abstract

Rising popularity of quantum computers in the last decade resulted in increased interest paid to reversible circuit synthesis process. In this work, a popular essential function-based synthesis algorithm known in the literature is parallelized using openMP library. Contrary to conventional way, essential functions are synthesized when needed without keeping a table-lookup library. When the reversible circuit is synthesized in parallel using a double core processor (4 active threads with hyperthearding technology), around 2.6 speed-up is demonstrated relative to the performance of serial synthesis work. Comparison between serial and parallel synthesis by using common benchmark circuits demonstrated that the performance of the proposed parallel synthesis is always better in the overall operation work load.

DOI
10.1109/siu.2018.8404481

Related papers

Parallelizing quantum circuit synthesis

Olivia Di Matteo, C Olivia Di Matteo

I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii We present an algorithmic framework for parallel quantum circuit synthesis using meet-in-the-middle synthesis techniques. We also present two implementations thereof, using both threaded and hybrid parallelization techniques. We give examples where applying parallelism offers a speedup on the time of circuit synthesis for 2-and 3-qubit circuits. We use a threaded algorithm to synthesize 3-qubit circuits with optimal T-count 9, and 11, breaking the previous record of T-count 7. As the estimated runtime of the framework is inversely proportional to the number of processors, we propose an implementation using hybrid parallel programming which can take full advantage of a computing cluster’s thousands of cores. This implementation has the potential to synthesize circuits which were previously deemed impossible due to the exponential runtime of existing algorithms.

•Jan 1, 2015•33 citations

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 30, 2006•371 citations

An efficient algorithm to synthesize quantum circuits and optimization

Ömercan Susam, Mustafa Altun

Quantum computers, more specifically quantum circuits, take on the eyes with their computational promises such as reversibility. In this paper, we perform synthesis and optimization of quantum circuits. In the first part, we propose a fast synthesis algorithm that implements any given reversible Boolean function with quantum gates. Instead of an exhaustive search on every given function, our algorithm creates a library of essential functions and performs sorting. As an example, to implement 4 bit circuits we only use 120 essential functions out of all 20922789888000 functions. In the second part, we optimize our circuits by using new templates. The proposed templates mainly consist of Toffoli gates with negative and positive controlling lines. These templates also show us that optimum area solutions proposed in the literature are not actually optimum; they can be improved.

IEEE International Conference on Electronics, Circuits and Systems (ICECS)•Dec 1, 2014•2 citations

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

SAT-based Exact Synthesis of Ternary Reversible Circuits using a Functionally Complete Gate Library

Abhoy Kole, Kamalika Datta, Indranil Sengupta +1 more

The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.

Euromicro Conference on Digital System Design (DSD)•Aug 1, 2022•1 citation

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
Rising popularity of quantum computers in the last decade resulted in increased interest paid to reversible circuit synthesis process. In this work, a popular essential function-based synthesis algorithm known in the literature is parallelized using openMP library. Contrary to conventional way, essential functions are synthesized when needed without keeping a table-lookup library. When the reversible circuit is synthesized in parallel using a double core processor (4 active threads with hyperthearding technology), around 2.6 speed-up is demonstrated relative to the performance of serial synthesis work. Comparison between serial and parallel synthesis by using common benchmark circuits demonstrated that the performance of the proposed parallel synthesis is always better in the overall operation work load.
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii We present an algorithmic framework for parallel quantum circuit synthesis using meet-in-the-middle synthesis techniques. We also present two implementations thereof, using both threaded and hybrid parallelization techniques. We give examples where applying parallelism offers a speedup on the time of circuit synthesis for 2-and 3-qubit circuits. We use a threaded algorithm to synthesize 3-qubit circuits with optimal T-count 9, and 11, breaking the previous record of T-count 7. As the estimated runtime of the framework is inversely proportional to the number of processors, we propose an implementation using hybrid parallel programming which can take full advantage of a computing cluster’s thousands of cores. This implementation has the potential to synthesize circuits which were previously deemed impossible due to the exponential runtime of existing algorithms.
Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25
Quantum computers, more specifically quantum circuits, take on the eyes with their computational promises such as reversibility. In this paper, we perform synthesis and optimization of quantum circuits. In the first part, we propose a fast synthesis algorithm that implements any given reversible Boolean function with quantum gates. Instead of an exhaustive search on every given function, our algorithm creates a library of essential functions and performs sorting. As an example, to implement 4 bit circuits we only use 120 essential functions out of all 20922789888000 functions. In the second part, we optimize our circuits by using new templates. The proposed templates mainly consist of Toffoli gates with negative and positive controlling lines. These templates also show us that optimum area solutions proposed in the literature are not actually optimum; they can be improved.
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.
The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.
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.