Spring 2020

Quantum Pseudorandomness and Classical Complexity

Thursday, Jul. 15, 2021 10:30 am11:15 am

Add to Calendar


William Kretschmer (UT Austin)



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.

Based on arXiv:2103.09320

PDF icon Slides330.57 KB