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 Multiple-Valued Logic (ISMVL)

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

Linh Hoang Tran, Addison Gronquist, Marek A. Perkowski, John S. Caughman

Published May 1, 2016• 5 citations
Publisher

Abstract

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.

DOI
10.1109/ismvl.2016.56

Related papers

Synthesis of Reversible Circuits Based on Products of Exclusive OR Sums

Ben Schaeffer, Linh Hoang Tran, Addison Gronquist +2 more

This paper introduces a new synthesis approach called Products of EXOR-sums (POE) and demonstrates its utility when employed in an Exclusive-Or-Sum-of-Products (ESOP) based algorithm for reversible and permutative quantum circuits restricted to single output functions. Unlike previous ESOP approaches such as EXORCISM-4 which realize functions as an EXOR-ed sum of product literals, this new algorithm realizes functions as an EXOR-ed sum of POEs (EPOE). A comparison of EXORCISM-4 and EPOE circuits shows that the latter approach often produces circuits with significantly lower quantum costs.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2013•7 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•Physical Review A•Jan 7, 2026•1 citation

Factorization of Exclusive-Sum-Of-Products Expressions with Rectangle Covering to Reduce Quantum Circuit Cost

Audrey Hou, Lucia Zhang, Ali Al-Bayaty +1 more

The implementation of quantum circuits is currently very expensive, especially due to the usage of large Toffoli gates. Therefore, it is critical to optimize circuit costs by factoring expressions as they become more complex. In the proposed algorithms to factor ESOP expressions, each product term is converted into a cell in a 2D matrix, and optimal factored AND/EXOR solutions are determined using Disjoint and Even-Odd Rectangle covering methods. Two Python programs implementing these algorithms were tested and evaluated using well-known benchmarks. The results showed that both the literal counts used in classical logic circuits as well as the Maslov cost used in quantum circuits was reduced by 20%-95% depending on expression size.

quant-pharXiv:2608.03188•Aug 5, 2026•0 citations

A shared-cube approach to ESOP-based synthesis of reversible logic

Noor Muhammed Nayeem, Jacqueline Rice

Reversible logic is being suggested as a possibility for overcoming potential power loss and heat dissipation problems that the computing industry may soon be at a loss to overcome. However, for reversible logic to be a solution we must have techniques for synthesizing function descriptions to reversible circuits. This paper presents an improved ESOP-based reversible logic synthesis approach which leverages situations where cubes are shared by multiple outputs and ensures that the implementation of each cube requires just one Toffoli gate. It has the potential to minimize both gate count and quantum cost, and in fact our experimental results show that this technique can reduce the quantum cost up to 75% compared to results from the existing work.

Facta universitatis - series Electronics and Energetics•Jan 1, 2011•40 citations

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

Nurul Ain Binti Adnan, Kouhei Kushida, Shigeru Yamashita

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.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2016•2 citations

Comparison of various error-detecting and error-correcting encodings of reversible automata built from irreversible state tables using EPOE circuits with EXOR lattices

Linh Hoang Tran, Bruce Yen, Marek A. Perkowski

This paper presents a new approach to synthesize reversible (quantum permutative) automata from standard state tables. It uses various variants of error-detecting and error-correcting encodings. Next, a combination of recently introduced “EPOE circuits” as well as EXOR Lattices are used for synthesis. The goal is to compare the costs of various encodings and synthesis methods for the same machine, especially strongly unspecified one.

International Conference on Information and Digital Technologies (IDT)•Jul 1, 2017•2 citations
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.
This paper introduces a new synthesis approach called Products of EXOR-sums (POE) and demonstrates its utility when employed in an Exclusive-Or-Sum-of-Products (ESOP) based algorithm for reversible and permutative quantum circuits restricted to single output functions. Unlike previous ESOP approaches such as EXORCISM-4 which realize functions as an EXOR-ed sum of product literals, this new algorithm realizes functions as an EXOR-ed sum of POEs (EPOE). A comparison of EXORCISM-4 and EPOE circuits shows that the latter approach often produces circuits with significantly lower quantum costs.
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.
The implementation of quantum circuits is currently very expensive, especially due to the usage of large Toffoli gates. Therefore, it is critical to optimize circuit costs by factoring expressions as they become more complex. In the proposed algorithms to factor ESOP expressions, each product term is converted into a cell in a 2D matrix, and optimal factored AND/EXOR solutions are determined using Disjoint and Even-Odd Rectangle covering methods. Two Python programs implementing these algorithms were tested and evaluated using well-known benchmarks. The results showed that both the literal counts used in classical logic circuits as well as the Maslov cost used in quantum circuits was reduced by 20%-95% depending on expression size.
Reversible logic is being suggested as a possibility for overcoming potential power loss and heat dissipation problems that the computing industry may soon be at a loss to overcome. However, for reversible logic to be a solution we must have techniques for synthesizing function descriptions to reversible circuits. This paper presents an improved ESOP-based reversible logic synthesis approach which leverages situations where cubes are shared by multiple outputs and ensures that the implementation of each cube requires just one Toffoli gate. It has the potential to minimize both gate count and quantum cost, and in fact our experimental results show that this technique can reduce the quantum cost up to 75% compared to results from the existing work.
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.