Pseudorandomness: From Quantum States to Binary Strings

Explore the concept of quantum pseudorandom generators (QPRGs) in this 42-minute lecture from the Minimum Quantum Assumptions for Cryptography Workshop. Delve into the research conducted by Prabhanjan Ananth, Yao-Ting Lin, and Henry Yuen, which investigates the possibility of basing QPRGs on assumptions weaker than one-way functions. Learn about the key differences between classical PRGs and QPRGs, including the allowance for small determinism error and polynomial-time quantum algorithm generation. Discover how QPRGs can be based on logarithmic-output pseudorandom quantum states and understand the main contribution of designing a (pseudo)-deterministic extractor for extracting uniformly random strings from Haar-random states. Examine the cryptographic applications and variants of QPRGs, gaining insights into the intersection of quantum computing and cryptography.