Pseudorandom unitaries
- LecturerDr. Hsin-Yuan Huang (Google Quantum AI)
Host: Kai-Min Chung - Time2024-08-05 (Mon.) 10:00 ~ 12:00
- LocationAuditorium 106 at IIS new Building
Abstract
Pseudorandom unitaries (PRUs) are efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries. First conjectured in 2017, the existence of PRUs has been a major open question in cryptography and complexity theory. In this work, we resolve this conjecture by proving that PRUs exist, assuming any quantum-secure one-way function exists. Furthermore, strong PRUs, which are secure given access to both the unitary, its inverse, and their controlled operations, also exist under the same assumption. We achieve these results by introducing the "compressed unitary oracle", a new and simple way to analyze algorithms that query a random unitary.
BIO
https://hsinyuan-huang.github.io/