Quantum Pseudorandomness and Classical Complexity

William Kretschmer, University of Texas at Austin, USA

Pseudorandomness is a key notion in complexity theory that has recently found applications in quantum cryptography and black hole physics. Ji, Liu, and Song (2018) defined "pseudorandom quantum states" (PRSs) as a sort of computational approximation to the Haar measure, analogous to cryptographic pseudorandom generators. In this talk, I will explore some connections between PRSs and structural complexity theory. I will present a surprising and counterintuitive result: a quantum oracle relative to which BQP = QMA but PRSs exist. On the other hand, I will show that PRSs do not exist if BQP = PP, a result which holds relative to all oracles. I will discuss several implications of these results, including a new impossibility result for shadow tomography, and a corollary involving quantum complexity classes augmented with Haar-random unitary oracles.

Recording of the talk