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

摘要

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.