IQIM Postdoctoral and Graduate Student Seminar

Special IQIM Seminar

Abstract: Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that "look" sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: t-designs are random unitaries that information-theoretically reproduce the first t moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. I will explain a simple unified construction of both t-designs and PRUs from the "PFC ensemble", the concatenation of a random Clifford unitary, a random binary phase, and a random computational basis state permutation. Then, I will show how the PFC ensemble helps us to resolve a long-standing open question about the spectral gap of random quantum circuits, implying that a random quantum circuit is essentially incompressible. This proves the Brown-Susskind conjecture from black hole physics.

Refreshments will be served following the talk.