How to Construct Random Unitaries | Quantum Colloquium

Random unitaries play a central role in quantum computing: they underlie the design of quantum supremacy experiments, learning algorithms, and cryptographic protocols. In physics, they’re used to model highly chaotic processes such as black hole dynamics. However, truly random unitaries, known as Haar-random unitaries, require exponential time to implement and are therefore both impractical for applications, and unrealistic as a model for any physical process.

This motivates the notion of a pseudorandom unitary (PRU), proposed by Ji, Liu, and Song: PRUs are efficient unitaries that are indistinguishable from Haar-random unitaries to any polynomial-time observer. Since 2018, the existence of pseudorandom unitaries has been a central open question.

In this talk, we present the first proof that PRUs exist, assuming quantum-secure one-way functions. Our proof uses purification to develop a new perspective on Haar-random unitaries that we call the “path-recording” oracle. This gives an efficient method to simulate queries to a Haar-random unitary, up to inverse-exponential error.

Based on joint work with Hsin-Yuan Huang. https://arxiv.org/abs/2410.10116