POPL 2025
Sun 19 - Sat 25 January 2025 Denver, Colorado, United States

We present the first implementation of a compiler for the high-level quantum programming language Qunity, which has a central design goal of treating quantum computation as a generalization of classical computation. To mitigate significant overhead associated with Qunity’s versatile quantum control construct, we introduce optimizations at various stages of the compilation process. These optimizations include new high-level compilation procedures that avoid costly operations on direct sums of spaces, as well as techniques for recycling and deleting qubits when constructing low-level circuits. This work also extends Qunity with new pattern-matching constructs that enhance the language’s expressiveness and allow for further optimization. The compiler significantly reduces the size of generated circuits, making it possible to implement and compile various quantum algorithms with reasonably small qubit and gate counts, thereby paving the way for the practical application of high-level languages in quantum algorithm design.