How to Simulate a Random Unitary (and Its Inverse)

Many central questions in quantum computing involve algorithms that apply a Haar-random unitary. But analyzing such algorithms is often difficult: if the unitary is applied k times, the final state depends on k-th moments of the Haar measure, which typically require sophisticated mathematical tools to control. 

In this talk, I'll present a new way to analyze Haar-random unitaries using the path recording oracle, a data structure that efficiently "spoofs" a random unitary. I’ll explain the intuition behind its definition, how it can be used to prove theorems about random unitaries, and how it works in settings where the algorithm can access both the unitary and its inverse. 

The talk is based on joint work with Robert Huang (https://arxiv.org/abs/2410.10116), but will focus primarily on the path-recording oracle.