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.
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.
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.
Recent experimental progress in realizing surface code on hardware, including demonstrations of break-even logical memory on devices with up to hundreds of physical qubits, has materially advanced the prospects for fault-tolerant quantum computation. This progress creates urgency for the development of compilation workflows that directly target the forthcoming generation of devices with thousands of physical qubits, for which algorithm execution becomes practical. We develop a pipeline for compiling logical algorithms to physical circuits implementing lattice surgery on the surface code, and use this pipeline to identify the requirements for achieving algorithmic break-even -- where quantum error correction improves the performance of a quantum algorithm -- for two prominent quantum algorithms: the quantum approximate optimization algorithm (QAOA) and quantum phase estimation (QPE). Our pipeline integrates several open-source software tools, and leverages recent advances in error-aware unitary gate synthesis, high-fidelity magic state production, and the calculation of correlation surfaces in the surface code. We perform classical simulations of physical Clifford proxy circuits produced by our pipeline, and find that both 5-qubit QAOA and QPE can reach algorithmic break-even with 2517 physical qubits (surface code distance
d=11) at physical error rates of
p=10−3, or 1737 physical qubits (
d=9) at
p=5×10−4. Our work thereby identifies conditions for achieving algorithmic break-even with near-term quantum hardware and paves the way towards an end-to-end compiler for early-fault-tolerant surface code architectures.