Pseudorandom unitaries
- 講者黃信元 博士 (Google Quantum AI)
邀請人：鐘楷閔 - 時間2024-08-05 (Mon.) 10:00 ~ 12:00
- 地點資訊所新館106演講廳
摘要
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/