How Haar Is It to Look Random?

Makrand Sinha (University of Illinois Urbana-Champaign) https://simons.berkeley.edu/talks/makrand-sinha-university-illinois-urbana-champaign-2026-10-29 Derandomization Classical computer science offers two powerful ways to construct simple substitutes for ideal randomness: k-wise independent functions, which look random on any k inputs, and pseudorandom functions, which look random to any computationally efficient algorithm. This talk explores how these classical ideas can be used to construct quantum operations that look random. For quantum operations, the natural benchmark is a Haar random unitary matrix. These matrices play important roles in quantum computation and cryptography and provide models of chaotic physical systems such as black holes. I will introduce the PFC ensemble, which combines random permutations (P) and functions (F) with quantum Clifford (C) operations. It provides a unified approach to constructing unitary designs and pseudorandom unitaries, the quantum counterparts of the two classical notions. I will also highlight a few recent developments and open questions in quantum pseudorandomness. No background in quantum information will be assumed for this talk. Based in part on joint work with Tony Metger, Alexander Poremba and Henry Yuen.