Region Inference for Ancilla Safety in Quantum Programming

Christopher McNally | Charles Yuan | William Oliver

Coherent quantum effects promise unprecedented speedups for certain computational problems. However, quantum algorithms remain difficult to express, reason about, and debug, due to the intricacy of the highly-entangled quantum states they rely on. Recent quantum programming languages have therefore sought to control the entanglement patterns that can appear in a program. One key desideratum is a property we call “ancilla safety”: a program should not free certain ancilla qubits while they remain entangled with data qubits, as this would lead to an unintended loss of coherence. We present an efficient, fully compile-time analysis to detect ancilla-unsafe programs, related to classical region-based analyses for memory- and thread-safety. This analysis is implemented in a complete compiler for a new high-level imperative, affinely typed quantum programming language. We show that this system is more liberal than existing languages: it admits more correct programs without compromising ancilla safety, at the cost of only sparse and lightweight type annotations.

Funding Sources: CQE-LPS Doc Bedard Fellowship