Abstract
Quantum pseudorandomness in Algorithmica, and its implications to cryptography and complexity
Abstract: Pseudorandom quantum states (PRS) are a form of quantum pseudorandomness that mimics the Haar random quantum states against efficient distinguishers. Recently, it has been shown that the existence of PRS is separated from (post-quantum) one-way functions or even P vs NP and BQP vs QMA. In particular, there exists a property of a cryptographic hash function called "hardness of shifted Forrelation" that is simultaneously useful (suffices to construct single-copy-secure PRS), plausible (holds for a random oracle), and is weaker than 𝖯 ≠ 𝖭𝖯 (in the black-box setting).
As a corollary, any black-box implication of PRS can be plausibly established without one-way functions. Especially for cryptography, this implies that a lot of quantum computational cryptography could potentially be realized from much weaker assumptions than one-way functions. This also motivates how a theory of quantum (meta-)complexity may be needed in order to study the complexity theoretic foundations of quantum computational cryptography.