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

CDES

A Quantum Algorithm for Finding Minimum Exclusive-Or Expressions for Multi-Output Incompletely Specified Boolean Functions.

Marinos Sampson, Dimitris Voudouris, George K. Papakonstantinou

Published Jan 1, 2008• 0 citations
OpenAlex

Abstract

Abstract— This paper,presents,a,quantum,algorithm,for finding minimal,ESCT (Exclusive-or Sum,of Complex,Terms) or ESOP (Exclusive-or Sum Of Products) expressions,for any arbitrary multi-output switching,function that is not necessarily completely,specified. The proposed,algorithm,takes advantage,of the inherent,massive,parallelism,of quantum,circuits in order to achieve,better complexity,than,the conventional,ones. The proposed,Exclusive-Or (xor) expressions,such as ESCT can be used to implement,an arbitrary Boolean function into a reversible or even a quantum,circuit. keywords: quantum computing,

Related papers

A Quantum Algorithm for Finding Minimum Exclusive-Or Expressions

Marinos Sampson, D. Voudouris, G. Papakonstantinou

This paper presents a quantum algorithm for minimizing both exclusive-or sum of complex terms (ESCT) and exclusive-or sum of products (ESOP) expressions. The proposed algorithm, QMin, takes advantage of the inherent massive parallelism of quantum circuits. The ESCT expressions produced by QMin are presented in the related bibliography as an attractive architecture for implementing reversible and quantum circuits.

IEEE Computer Society Annual Symposium on VLSI•Jan 1, 2007•0 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

Quantum rotational cryptanalysis for preimage recovery of round-reduced Keccak

Runsong Wang, Xuelian Li, Juntao Tony Gao +2 more

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

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

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
Abstract— This paper,presents,a,quantum,algorithm,for finding minimal,ESCT (Exclusive-or Sum,of Complex,Terms) or ESOP (Exclusive-or Sum Of Products) expressions,for any arbitrary multi-output switching,function that is not necessarily completely,specified. The proposed,algorithm,takes advantage,of the inherent,massive,parallelism,of quantum,circuits in order to achieve,better complexity,than,the conventional,ones. The proposed,Exclusive-Or (xor) expressions,such as ESCT can be used to implement,an arbitrary Boolean function into a reversible or even a quantum,circuit. keywords: quantum computing,
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.
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.
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.
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.