Abstract: As quantum computing hardware continues to improve, so must the tools we use to write quantum algorithms. There is a growing need for more expressive quantum programming languages that enable developers to write code at higher levels of abstraction than quantum circuits. This, in turn, necessitates robust and automated compilers that can generate optimized sequences of quantum operations in a scalable way. Such compilers are especially important for algorithms with many interdependent classical and quantum subroutines, such as Shor’s factoring algorithm.

In this talk I will provide a pedagogical introduction to Shor’s algorithm by presenting its implementation at varying levels of abstraction. While its high-level subroutines are straightforward to express, compilation and optimization incurs a large overhead due to the algorithm’s randomized nature. To that end, I will highlight on-going work on a fully just-in-time-compiled implementation using PennyLane and Catalyst. I’ll discuss its scaling, practical resource requirements, implementation tricks (and unique quirks), and the feasibility of executing it on near-term hardware.