How Haar Is It to Look Random? @SimonsInstitute
How Haar Is It to Look Random?  @SimonsInstitute
Uploaded October 2026 | Updated November 2026, 1 day ago
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.
How Haar Is It to Look Random?Detecting Uncertainty to Enhance AI ReliabilityQuantum ergodicity on graphs (Part 1)Extractors for Samplable Distributions from the Two-Source Extractor RecipeStrong convergence of right-angled Artin groups and spectral gaps of hyperbolic 3-manifoldsWeak Poincaré Inequalities and Mixing from Non-Worst-Case InitializationsDo we need diffusion in robotics?On Spectral Independence and Localization Schemes (Part 2)Learning the structure of open quantum systemsNormalizing Flow MapsStrong Convergence (Part 3)High-Dimensional Expansion (HDX) (Part 2)
Simons Institute for the Theory of Computing |

How Haar Is It to Look Random?

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER