Tools for Quantum and Reversible Circuit Compilation

We present tools for resource-aware compilation of higher-level, irreversible programs into lower-level, reversible circuits. Our main focus is on optimizing the memory footprint of the resulting reversible networks. We discuss a number of examples to illustrate our compilation strategy for problems at scale, including a reversible implementation of hash functions such as SHA-256, automatic generation of reversible integer arithmetic from irreversible descriptions, as well as a test-bench of Boolean circuits that is used by the classical Circuits and Systems community. Our main findings are that, when compared with Bennett’s original “compute-copy-uncompute”, it is possible to reduce the space complexity by 75% or more, at the price of having an only moderate increase in circuit size as well as in compilation time. Finally, we discuss some emerging new paradigms in quantum circuit synthesis, namely the use of dirty ancillas to save overall memory footprint, probabilistic protocols such as the RUS framework which can help to reduce the gate complexity of rotations, and synthesis methods for higher-dimensional quantum systems.