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 Transactions on Computer-Aided Design of Integrated Circuits and Systems

Product Transformation and Heuristic EXOR-AND-OR Logic Synthesis of Incompletely Specified Functions

Ben Schaeffer

Published Feb 7, 2017• 2 citations
Publisher

Abstract

Previously, the synthesis of reversible and quantum permutative circuits based on products of Exclusive-OR (EXOR) sums of inputs (POE) was explored as an approach to reduce quantum cost. Herein, the mathematical representation used in POE expressions is formally detailed and contrasted with the pseudoproduct-based theory of Luccio and Pagli. The theory and practice of product transformation, or computation of equivalent POE expressions, is presented. To demonstrate the generality of the mathematical representations outside of the reversible domain, a new method to synthesize incompletely specified functions as EXOR-AND-OR circuits is introduced. The method is heuristic. It first uses spectral information from the Walsh-Hadamard transform to compute a set of POE implicants for a function, and then uses product transformation to minimize both the total number of literals and unique EXOR sums (ignoring polarity) used in the POE implicants. The product transformation minimization extends to multioutput functions. The new method has no performance guarantees, i.e., it does not have a fallback mode of minimum or near-minimum sum of products; therefore, it is suited to a tournament synthesis approach. When synthesizing benchmark functions of up to 26 inputs, the new method is shown to typically produce lower cost circuits than heuristic pseudoproduct-based methods.

DOI
10.1109/tcad.2017.2664064

Related papers

Synthesis of Linear Reversible Circuits and EXOR-AND-based Circuits for Incompletely Specified Multi-Output Functions

Ben Schaeffer

At this time the synthesis of reversible circuits for quantum computing is an active area of research. In the most restrictive quantum computing models there are no ancilla lines and the quantum cost, or latency, of performing a reversible form of the AND gate, or Toffoli gate, increases exponentially with the number of input variables. In contrast, the quantum cost of performing any combination of reversible EXOR gates, or CNOT gates, on n input variables requires at most O(n2/log2n) gates. It was under these conditions that EXOR-AND-EXOR, or EPOE, synthesis was developed. In this work, the GF(2) logic theory used in EPOE is expanded and the concept of an EXOR-AND product transform is introduced. Because of the generality of this logic theory, it is adapted to EXOR-AND-OR, or SPOE, synthesis. Three heuristic spectral logic synthesis algorithms are introduced, implemented in a program called XAX, and compared with previous work in classical logic circuits of up to 26 inputs. Three linear reversible circuit methods are also introduced and compared with previous work in linear reversible logic circuits of up to 100 inputs.

•Jul 21, 2017•0 citations

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•8 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

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

Ternary max-min algebra for representation of reversible logic functions

Musharrat Khan, Jacqueline E. Rice

Ternary reversible logic functions are generally represented as ternary Galois field sum of products (TGFSOP) expressions and the TGFSOP expressions are mapped to reversible circuits using cascades of Feynman and Toffoli gates. Although a ternary logic function with a large number of variables can be minimized as a TGFSOP expression, the process is computationally expensive and the resulting reversible circuit tends to have a high quantum cost and ancilla inputs. To overcome these limitations, in this work we propose a new method of representing ternary reversible logic functions as Max of Min-terms (Max-Min) expressions, which can be mapped to a reversible circuit using multiple-controlled unary gates requiring lower quantum cost and fewer ancilla inputs. We propose a map-based minimization method for Max-Min expressions of up to four variables focusing on restrictions of the reversible circuit mapping technique.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2016•8 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
Previously, the synthesis of reversible and quantum permutative circuits based on products of Exclusive-OR (EXOR) sums of inputs (POE) was explored as an approach to reduce quantum cost. Herein, the mathematical representation used in POE expressions is formally detailed and contrasted with the pseudoproduct-based theory of Luccio and Pagli. The theory and practice of product transformation, or computation of equivalent POE expressions, is presented. To demonstrate the generality of the mathematical representations outside of the reversible domain, a new method to synthesize incompletely specified functions as EXOR-AND-OR circuits is introduced. The method is heuristic. It first uses spectral information from the Walsh-Hadamard transform to compute a set of POE implicants for a function, and then uses product transformation to minimize both the total number of literals and unique EXOR sums (ignoring polarity) used in the POE implicants. The product transformation minimization extends to multioutput functions. The new method has no performance guarantees, i.e., it does not have a fallback mode of minimum or near-minimum sum of products; therefore, it is suited to a tournament synthesis approach. When synthesizing benchmark functions of up to 26 inputs, the new method is shown to typically produce lower cost circuits than heuristic pseudoproduct-based methods.
At this time the synthesis of reversible circuits for quantum computing is an active area of research. In the most restrictive quantum computing models there are no ancilla lines and the quantum cost, or latency, of performing a reversible form of the AND gate, or Toffoli gate, increases exponentially with the number of input variables. In contrast, the quantum cost of performing any combination of reversible EXOR gates, or CNOT gates, on n input variables requires at most O(n2/log2n) gates. It was under these conditions that EXOR-AND-EXOR, or EPOE, synthesis was developed. In this work, the GF(2) logic theory used in EPOE is expanded and the concept of an EXOR-AND product transform is introduced. Because of the generality of this logic theory, it is adapted to EXOR-AND-OR, or SPOE, synthesis. Three heuristic spectral logic synthesis algorithms are introduced, implemented in a program called XAX, and compared with previous work in classical logic circuits of up to 26 inputs. Three linear reversible circuit methods are also introduced and compared with previous work in linear reversible logic circuits of up to 100 inputs.
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 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 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.
Ternary reversible logic functions are generally represented as ternary Galois field sum of products (TGFSOP) expressions and the TGFSOP expressions are mapped to reversible circuits using cascades of Feynman and Toffoli gates. Although a ternary logic function with a large number of variables can be minimized as a TGFSOP expression, the process is computationally expensive and the resulting reversible circuit tends to have a high quantum cost and ancilla inputs. To overcome these limitations, in this work we propose a new method of representing ternary reversible logic functions as Max of Min-terms (Max-Min) expressions, which can be mapped to a reversible circuit using multiple-controlled unary gates requiring lower quantum cost and fewer ancilla inputs. We propose a map-based minimization method for Max-Min expressions of up to four variables focusing on restrictions of the reversible circuit mapping technique.
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.