SHF: FET: Programming Foundations for Quantum Random Access

Algorithms for quantum computers offer powerful speedups in domains ranging from materials simulation to logistics and optimization. Like their classical counterparts, many quantum algorithms rely on the ability to randomly access a data value by its address — both of which exist in superposition on a quantum computer. Typically, researchers assume that this logical operation of random access will be implemented by a hardware device known as quantum random-access memory (qRAM). But general-purpose qRAM is challenging on the constrained hardware foreseeable today, and this dependency renders many promising algorithms unimplementable in practice. To break this deadlock, this project redefines quantum random access not as a hardware contract, but as a software abstraction decoupled from its implementation. The project's novelties are a compiler, a program verifier, and a memory management system that support quantum random access in software, bypassing the dependency on specialized hardware. The project's impacts are accelerating the realization as concrete programs of many quantum applications that otherwise exist only as abstract mathematical theory. This project develops a software stack for quantum algorithms organized into three thrusts. The first thrust focuses on efficiency, designing a specializing compiler that lowers abstract random access operations into static circuits optimized for specific usage patterns. The second targets soundness, developing verifiers that check correctness properties of quantum programs via reasoning over high-level abstractions rather than bit-level circuits. The third targets expressivity, introducing language support that relieves programmers from manual management of heap-allocated quantum data. Together, these thrusts shift the paradigm of quantum memory from a problem of hardware engineering to one of compiler optimization. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.