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

Anais do Seminário Integrado de Software e Hardware (SEMISH)

Improving Qiskit strategies for circuit synthesis using the Reed-Muller spectrum

Raphael B. F. Lima, Luis Antônio Brasil Kowada, Fábio G. dos Santos

Published Jul 20, 2025• 0 citations
Publisher

Abstract

Reversible computing and quantum computing have gained increasing attention due to their potential to overcome some of the fundamental limitations of classical computing, particularly regarding energy efficiency and computational power. In this paper, we compare the synthesis process using the well-known Qiskit framework developed by IBM and an approach based on Reed-Muller spectra. We show that some approaches are efficient for small values and others are better for the general use case. The synthesis results are presented using four strategies: unitary matrices, linear function synthesis, permutation synthesis, and Reed-Muller spectra. Our analysis shows that, on average, our proposal surpasses the Qiskit synthesis algorithms when considering the gate count metric. Additionally, a post-synthesis evaluation is performed using our proposed method, which employs a Reed-Muller–based representation to assess its effectiveness.

DOI
10.5753/semish.2025.9256

Related papers

Reversible circuit synthesis using a cycle-based approach

Mehdi Saeedi, Morteza Saheb Zamani, Mehdi Sedighi +1 more

Reversible logic has applications in various research areas, including signal processing, cryptography and quantum computation. In this article, direct NCT-based synthesis of a given k -cycle in a cycle-based synthesis scenario is examined. To this end, a set of seven building blocks is proposed that reveals the potential of direct synthesis of a given permutation to reduce both quantum cost and average runtime. To synthesize a given large cycle, we propose a decomposition algorithm to extract the suggested building blocks from the input specification. Then, a synthesis method is introduced that uses the building blocks and the decomposition algorithm. Finally, a hybrid synthesis framework is suggested that uses the proposed cycle-based synthesis method in conjunction with one of the recent NCT-based synthesis approaches which is based on Reed-Muller (RM) spectra. The time complexity and the effectiveness of the proposed synthesis approach are analyzed in detail. Our analyses show that the proposed hybrid framework leads to a better quantum cost in the worst-case scenario compared to the previously presented methods. The proposed framework always converges and typically synthesizes a given specification very fast compared to the available synthesis algorithms. Besides, the quantum costs of benchmark functions are improved about 20% on average (55% in the best case).

arXiv:1004.4320•ACM Journal on Emerging Technologies in Computing Systems•Dec 1, 2010•131 citations

Improved Implementation of a Reed-Muller Spectra Based Reversible Synthesis Algorithm

Jing Zhong, Jon C. Muzio

Reversible logic synthesis has been gaining much attention recently. There are many synthesis approaches including those using spectral techniques. In this paper, we discuss an improved implementation of a reversible synthesis algorithm for Toffoli networks based on Reed-Muller spectra. We use a compact RM spectral table in the algorithm to reduce runtime and memory occupation. This method is proved to be able to speed up synthesis for many benchmark reversible functions.

IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)•Aug 1, 2007•7 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•379 citations

RMDDS

Chia-Chun Lin, Niraj Kumar Jha

In this article, we propose a flexible and efficient reversible logic synthesizer. It exploits the complementary advantages of two methods: Reed-Muller Reversible Logic Synthesis (RMRLS) and Decision Diagram Synthesis (DDS), and is thus called Reed-Muller Decision Diagram Synthesis (RMDDS). RMRLS does not scale to a large number of qubits (i.e., quantum bits). DDS tools, even though efficient, add a large number of ancillary qubits and typically incur much higher quantum cost than necessary. RMDDS overcomes these obstacles. It is flexible in the sense that users can either optimize the number of qubits or the quantum cost in the circuit implementation. It is also efficient because the circuits can be synthesized within user-defined CPU times. This combination of flexibility and efficiency has been missing from synthesizers presented earlier. When used to synthesize reversible functions, RMDDS reduces the number of qubits by up to 79.2% (average of 54.6%) when the synthesis objective is to minimize the number of qubits and the quantum cost by up to 71.5% (average of 35.7%) when the synthesis objective is to minimize quantum cost, relative to DDS methods. For irreversible functions (which are automatically embedded in reversible functions), the corresponding best (average) reductions in the number of qubits is 42.1% (22.5%) when minimizing the number of qubits, and in quantum cost, it is 63.0% (25.9%) when minimizing quantum cost.

ACM Journal on Emerging Technologies in Computing Systems•Feb 1, 2014•24 citations

Positive Davio-based synthesis algorithm for reversible logic

Yu Pang, Shaoquan Wang, Zhilong He +3 more

Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.

IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)•Oct 1, 2011•17 citations

A Method to Synthesize Boolean Quantum Circuit Based on Reed-Muller Expansions

Shengchao Ding, Zhi Hao Jin

This paper presents how to synthesize efficient Boolean quantum circuits (BQC) from Reed-Muller (RM) expansions of Boolean functions. Firstly, the method of Younes et al [A. Younes and J. F. Miller, International Journal of Electronics 91, 431 (2004)] is generalized to synthesize BQC for multiple outputs function. The transformation is straightforward. A technique rearranging the modified Toffoli gates is also presented to eliminate additive NOT gates as much as possible. Secondly, the approach synthesizing BQC without work qubits is proposed which is simple and high-efficient. The necessary conditions for the RM expansions which can be synthesized by the proposed method are derived too.

International Conference on Communications, Circuits and Systems•Jul 1, 2007•1 citation
Reversible computing and quantum computing have gained increasing attention due to their potential to overcome some of the fundamental limitations of classical computing, particularly regarding energy efficiency and computational power. In this paper, we compare the synthesis process using the well-known Qiskit framework developed by IBM and an approach based on Reed-Muller spectra. We show that some approaches are efficient for small values and others are better for the general use case. The synthesis results are presented using four strategies: unitary matrices, linear function synthesis, permutation synthesis, and Reed-Muller spectra. Our analysis shows that, on average, our proposal surpasses the Qiskit synthesis algorithms when considering the gate count metric. Additionally, a post-synthesis evaluation is performed using our proposed method, which employs a Reed-Muller–based representation to assess its effectiveness.
Reversible logic has applications in various research areas, including signal processing, cryptography and quantum computation. In this article, direct NCT-based synthesis of a given k -cycle in a cycle-based synthesis scenario is examined. To this end, a set of seven building blocks is proposed that reveals the potential of direct synthesis of a given permutation to reduce both quantum cost and average runtime. To synthesize a given large cycle, we propose a decomposition algorithm to extract the suggested building blocks from the input specification. Then, a synthesis method is introduced that uses the building blocks and the decomposition algorithm. Finally, a hybrid synthesis framework is suggested that uses the proposed cycle-based synthesis method in conjunction with one of the recent NCT-based synthesis approaches which is based on Reed-Muller (RM) spectra. The time complexity and the effectiveness of the proposed synthesis approach are analyzed in detail. Our analyses show that the proposed hybrid framework leads to a better quantum cost in the worst-case scenario compared to the previously presented methods. The proposed framework always converges and typically synthesizes a given specification very fast compared to the available synthesis algorithms. Besides, the quantum costs of benchmark functions are improved about 20% on average (55% in the best case).
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
In this article, we propose a flexible and efficient reversible logic synthesizer. It exploits the complementary advantages of two methods: Reed-Muller Reversible Logic Synthesis (RMRLS) and Decision Diagram Synthesis (DDS), and is thus called Reed-Muller Decision Diagram Synthesis (RMDDS). RMRLS does not scale to a large number of qubits (i.e., quantum bits). DDS tools, even though efficient, add a large number of ancillary qubits and typically incur much higher quantum cost than necessary. RMDDS overcomes these obstacles. It is flexible in the sense that users can either optimize the number of qubits or the quantum cost in the circuit implementation. It is also efficient because the circuits can be synthesized within user-defined CPU times. This combination of flexibility and efficiency has been missing from synthesizers presented earlier. When used to synthesize reversible functions, RMDDS reduces the number of qubits by up to 79.2% (average of 54.6%) when the synthesis objective is to minimize the number of qubits and the quantum cost by up to 71.5% (average of 35.7%) when the synthesis objective is to minimize quantum cost, relative to DDS methods. For irreversible functions (which are automatically embedded in reversible functions), the corresponding best (average) reductions in the number of qubits is 42.1% (22.5%) when minimizing the number of qubits, and in quantum cost, it is 63.0% (25.9%) when minimizing quantum cost.
Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.
This paper presents how to synthesize efficient Boolean quantum circuits (BQC) from Reed-Muller (RM) expansions of Boolean functions. Firstly, the method of Younes et al [A. Younes and J. F. Miller, International Journal of Electronics 91, 431 (2004)] is generalized to synthesize BQC for multiple outputs function. The transformation is straightforward. A technique rearranging the modified Toffoli gates is also presented to eliminate additive NOT gates as much as possible. Secondly, the approach synthesizing BQC without work qubits is proposed which is simple and high-efficient. The necessary conditions for the RM expansions which can be synthesized by the proposed method are derived too.