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 Symposium on Circuits and Systems proceedings

A pre-optimization technique to generate initial reversible circuits with low quantum cost

Nurul Ain Binti Adnan, Kouhei Kushida, Shigeru Yamashita

Published May 1, 2016• 2 citations
Publisher

Abstract

In order to generate an initial reversible/quantum circuit to realize a given Boolean function, one of the major approaches is to find a small Exclusive-or Sum-Of-Products (ESOP) expression for the function; each product term in the ESOP expression naturally corresponds to a single Mixed Polarity Multiple-Control Toffoli (MPMCT) gate. In this paper, we propose a technique to perform pre-optimization before generating an ESOP expression. Our approach is unique in a sense that instead of finding a small ESOP expression for a given function, we try to change it by adding MPMCT gates so that the modified function has a smaller ESOP expression. We expect that our approach can generate a better initial circuit compared to using ESOP minimization techniques only. Indeed our preliminary experiments for small functions confirm this expectation. Thus, we expect that our approach would be a good pre-optimization technique that can be used with most existing reversible circuit synthesis techniques.

DOI
10.1109/iscas.2016.7539043

Related papers

Reduction of Quantum Cost by Making Temporary Changes to the Function

Nurul Ain Binti Adnan, Shigeru Yamashita, Alan Mishchenko

This paper presents a technique to reduce the quantum cost by making temporary changes to the functionality of a given Boolean function. This technique is one of the very few known methods based on manipulating Exclusive-or Sum-Of-Products (ESOP) expressions to reduce the quantum cost of the corresponding circuit. The idea involves adding Mixed Polarity Multiple-Control Toffoli (MPMCT) gates to temporarily change the functionality of the given function, so that the modified function has a smaller quantum cost. To compensate for the temporary change, additional gates are inserted into the circuit. The proposed method finds a small ESOP expression for the given function, and then finds a good pair of product terms in the ESOP expression so that the quantum cost can be reduced by applying the transformation. The proposed approach is likely to produce a better quantum cost reduction than the existing methods, and indeed experimental results confirm this expectation.

IEICE Transactions on Information and Systems•Jan 1, 2017•3 citations

Quantum algorithm for ESOP minimization

Hrithik Ketineni, Marek A. Perkowski

The Exclusive-OR Sum-of-Product (ESOP) minimization problem has long been of interest to the research community because of its importance in classical logic design (including low-power design and design for test), reversible logic synthesis, and knowledge discovery, among other applications. However, no exact minimal minimization method has been presented for more than seven variables on arbitrary functions. This paper presents a novel quantum-classical hybrid algorithm for the exact minimal ESOP minimization of incompletely specified Boolean functions. This algorithm constructs oracles from sets of constraints and leverages the quantum speedup offered by Grover's algorithm to find solutions to these oracles, thereby improving over classical algorithms. Improved encoding of ESOP expressions results in substantially fewer decision variables compared to many existing algorithms for many classes of Boolean functions. This paper also extends the idea of exact minimal ESOP minimization to additionally minimize the cost of realizing an ESOP expression as a quantum circuit. To the extent of the authors' knowledge, such a method has never been published. This algorithm was tested on completely and incompletely specified Boolean functions via quantum simulation.

Quantum Information and Computation•Jan 29, 2023•2 citations

Scaling-up ESOP Synthesis for Quantum Compilation

Bruno de O. Schmitt, Mathias Soeken, Giovanni De Micheli +1 more

Today's rapid advances in quantum computing hardware call for scalable synthesis methods to map combinational logic represented as multi-level Boolean networks (e.g., an and-inverter graph, AIG) to quantum circuits. Such synthesis process must yield reversible logic function since quantum circuits are reversible. Thus, logic representations using exclusive sum-of-products (ESOP) are advantageous because of their natural relation to Toffoli gates, one of the primitives in reversible logic. This motivates developing effective methods to collapse AIG logic networks into ESOPs. In this work, we present two state-of-the-art methods to collapse an AIG into an ESOP expression, describe their shortcomings and introduce a new approach based on the divide-and-conquer paradigm. We demonstrate the effectiveness of our method in collapsing IEEE-compliant half precision floating point networks. Results show that our method can collapse designs-which were previously not solvable within a week-in less than 5 minutes. We also describe a technique capable of taking advantage of this new method to generate quantum circuits with up to 50% fewer T gates compared to state-of-the-art methods.

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

Ancilla-Quantum Cost Trade-off during Reversible Logic Synthesis using Exclusive Sum-of-Products

Anupam Chattopadhyay, Pal, Nilanjan, Soumajit Majumder

Emerging technologies with asymptotic zero power dissipation, such as quantum computing, require the logical operations to be done in a reversible manner. In recent years, the problem of synthesizing Boolean functions in the reversible logic domain has gained significant research attention. The efficiency of the synthesis methods is measured in terms of quantum cost, gate cost, garbage lines, logic depth and speed of synthesis. In this paper, we present an approach based on Exclusive sum-of-Products (ESOP), which allows the user to explore the trade-off between quantum cost and garbage lines. The proposed technique adds a new dimension to the reversible logic synthesis solutions. We demonstrate by detailed experiments that controlled improvement in quantum cost and gate count by increasing garbage count can be achieved. In some cases, improved quantum cost and gate count compared to state-of-the-art synthesis methods are reported. Furthermore, we propose a novel rule-based approach to achieve ancilla-free reversible logic synthesis starting from an ESOP formulation.

arXiv:1405.6073•May 23, 2014•5 citations

Minimization of AND-XOR Expressions with Decoders for Quantum Circuits

Sonia Yang, Ali Al-Bayaty, Marek Perkowski

This paper introduces a new logic structure for reversible quantum circuit synthesis. Our synthesis method aims to minimize the quantum cost of reversible quantum circuits with decoders. In this method, multi-valued input, binary output (MVI) functions are utilized as a mathematical concept only, but the circuits are binary. We introduce the new concept of ``Multi-Valued Input Fixed Polarity Reed-Muller (MVI-RM)" forms. Our decoder-based circuit uses three logical levels in contrast to commonly-used methods based on Exclusive-or Sum of Products (ESOP) with two levels (AND-XOR expressions), realized by Toffoli gates. In general, the high number of input qubits in the resulting Toffoli gates is a problem that greatly impacts the quantum cost. Using decoders decreases the number of input qubits in these Toffoli gates. We present two practical algorithms for three-level circuit synthesis by finding the MVI-FPRM: products-matching and the newly developed butterfly diagrams. The best MVI-FPRM forms are factorized and reduced to approximate Multi-Valued Input Generalized Reed-Muller (MVI-GRM) forms.

quant-pharXiv:2601.02515•Jan 7, 2026•0 citations

An Improved Factorization Approach to Reversible Circuit Synthesis Based on EXORs of Products of EXORs

Linh Hoang Tran, Addison Gronquist, Marek A. Perkowski +1 more

This paper introduces new algorithms to synthesize reversible functions using EXOR-sum of Products-of-EXOR-sums (EPOE) structures. The motivation for using these structures is to reduce the number of as well as the sizes of multiple controlled Toffoli gates, and thus the quantum cost. To achieve these reductions the paper generalizes from existing 2-level AND-EXOR structures (ESOP) commonly used in reversible logic to a mixture of 3-level EXOR-AND-EXOR structures and ESOPs. Our approach can be applied to reversible and permutative quantum circuits to synthesize single output functions on to an output line, with no additional ancilla bits. A comparison of the ESOP minimizer EXORCISM-4 and two variants of the EPOE minimizer, called EPOEM-1s and EPOEM-2, is presented. The results show that EPOE circuits do in fact achieve the above-stated cost reductions, in particular when expressed in terms of Maslov's quantum cost, the metric commonly used in quantum circuit synthesis.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2016•5 citations
In order to generate an initial reversible/quantum circuit to realize a given Boolean function, one of the major approaches is to find a small Exclusive-or Sum-Of-Products (ESOP) expression for the function; each product term in the ESOP expression naturally corresponds to a single Mixed Polarity Multiple-Control Toffoli (MPMCT) gate. In this paper, we propose a technique to perform pre-optimization before generating an ESOP expression. Our approach is unique in a sense that instead of finding a small ESOP expression for a given function, we try to change it by adding MPMCT gates so that the modified function has a smaller ESOP expression. We expect that our approach can generate a better initial circuit compared to using ESOP minimization techniques only. Indeed our preliminary experiments for small functions confirm this expectation. Thus, we expect that our approach would be a good pre-optimization technique that can be used with most existing reversible circuit synthesis techniques.
This paper presents a technique to reduce the quantum cost by making temporary changes to the functionality of a given Boolean function. This technique is one of the very few known methods based on manipulating Exclusive-or Sum-Of-Products (ESOP) expressions to reduce the quantum cost of the corresponding circuit. The idea involves adding Mixed Polarity Multiple-Control Toffoli (MPMCT) gates to temporarily change the functionality of the given function, so that the modified function has a smaller quantum cost. To compensate for the temporary change, additional gates are inserted into the circuit. The proposed method finds a small ESOP expression for the given function, and then finds a good pair of product terms in the ESOP expression so that the quantum cost can be reduced by applying the transformation. The proposed approach is likely to produce a better quantum cost reduction than the existing methods, and indeed experimental results confirm this expectation.
The Exclusive-OR Sum-of-Product (ESOP) minimization problem has long been of interest to the research community because of its importance in classical logic design (including low-power design and design for test), reversible logic synthesis, and knowledge discovery, among other applications. However, no exact minimal minimization method has been presented for more than seven variables on arbitrary functions. This paper presents a novel quantum-classical hybrid algorithm for the exact minimal ESOP minimization of incompletely specified Boolean functions. This algorithm constructs oracles from sets of constraints and leverages the quantum speedup offered by Grover's algorithm to find solutions to these oracles, thereby improving over classical algorithms. Improved encoding of ESOP expressions results in substantially fewer decision variables compared to many existing algorithms for many classes of Boolean functions. This paper also extends the idea of exact minimal ESOP minimization to additionally minimize the cost of realizing an ESOP expression as a quantum circuit. To the extent of the authors' knowledge, such a method has never been published. This algorithm was tested on completely and incompletely specified Boolean functions via quantum simulation.
Today's rapid advances in quantum computing hardware call for scalable synthesis methods to map combinational logic represented as multi-level Boolean networks (e.g., an and-inverter graph, AIG) to quantum circuits. Such synthesis process must yield reversible logic function since quantum circuits are reversible. Thus, logic representations using exclusive sum-of-products (ESOP) are advantageous because of their natural relation to Toffoli gates, one of the primitives in reversible logic. This motivates developing effective methods to collapse AIG logic networks into ESOPs. In this work, we present two state-of-the-art methods to collapse an AIG into an ESOP expression, describe their shortcomings and introduce a new approach based on the divide-and-conquer paradigm. We demonstrate the effectiveness of our method in collapsing IEEE-compliant half precision floating point networks. Results show that our method can collapse designs-which were previously not solvable within a week-in less than 5 minutes. We also describe a technique capable of taking advantage of this new method to generate quantum circuits with up to 50% fewer T gates compared to state-of-the-art methods.
Emerging technologies with asymptotic zero power dissipation, such as quantum computing, require the logical operations to be done in a reversible manner. In recent years, the problem of synthesizing Boolean functions in the reversible logic domain has gained significant research attention. The efficiency of the synthesis methods is measured in terms of quantum cost, gate cost, garbage lines, logic depth and speed of synthesis. In this paper, we present an approach based on Exclusive sum-of-Products (ESOP), which allows the user to explore the trade-off between quantum cost and garbage lines. The proposed technique adds a new dimension to the reversible logic synthesis solutions. We demonstrate by detailed experiments that controlled improvement in quantum cost and gate count by increasing garbage count can be achieved. In some cases, improved quantum cost and gate count compared to state-of-the-art synthesis methods are reported. Furthermore, we propose a novel rule-based approach to achieve ancilla-free reversible logic synthesis starting from an ESOP formulation.
This paper introduces a new logic structure for reversible quantum circuit synthesis. Our synthesis method aims to minimize the quantum cost of reversible quantum circuits with decoders. In this method, multi-valued input, binary output (MVI) functions are utilized as a mathematical concept only, but the circuits are binary. We introduce the new concept of ``Multi-Valued Input Fixed Polarity Reed-Muller (MVI-RM)" forms. Our decoder-based circuit uses three logical levels in contrast to commonly-used methods based on Exclusive-or Sum of Products (ESOP) with two levels (AND-XOR expressions), realized by Toffoli gates. In general, the high number of input qubits in the resulting Toffoli gates is a problem that greatly impacts the quantum cost. Using decoders decreases the number of input qubits in these Toffoli gates. We present two practical algorithms for three-level circuit synthesis by finding the MVI-FPRM: products-matching and the newly developed butterfly diagrams. The best MVI-FPRM forms are factorized and reduced to approximate Multi-Valued Input Generalized Reed-Muller (MVI-GRM) forms.
This paper introduces new algorithms to synthesize reversible functions using EXOR-sum of Products-of-EXOR-sums (EPOE) structures. The motivation for using these structures is to reduce the number of as well as the sizes of multiple controlled Toffoli gates, and thus the quantum cost. To achieve these reductions the paper generalizes from existing 2-level AND-EXOR structures (ESOP) commonly used in reversible logic to a mixture of 3-level EXOR-AND-EXOR structures and ESOPs. Our approach can be applied to reversible and permutative quantum circuits to synthesize single output functions on to an output line, with no additional ancilla bits. A comparison of the ESOP minimizer EXORCISM-4 and two variants of the EPOE minimizer, called EPOEM-1s and EPOEM-2, is presented. The results show that EPOE circuits do in fact achieve the above-stated cost reductions, in particular when expressed in terms of Maslov's quantum cost, the metric commonly used in quantum circuit synthesis.