Paper 2025/1863

On Limits on the Provable Consequences of Quantum Pseudorandomness

Abstract

There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs) and pseudorandom function-like state generators (PRFSGs). Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relation between quantum pseudorandomness has yet to be fully established. We present evidence suggesting that some forms of quantum pseudorandomness are unlikely to be constructed from the others. This indicates that quantum pseudorandomness behaves quite differently from classical pseudorandomness. Our main result is a unitary oracle separation where log-length output PRFSGs exist but quantum-computable pseudorandom generators (QPRGs) with negligible correctness error do not. This result suggests that the inverse-polynomial error in the state-of-the-art construction of QPRGs from log-length PRSGs is inherent. To achieve this, we prove a novel geometric \emph{barrier theorem} for the product Haar measure on quantum states which replaces the usual concentration inequalities by certifying a non-negligible ``gap'' between two large trace-separated sets. As further evidence that quantum pseudorandomness does not collapse to a single assumption, we also obtain separations showing limitations of: (i) deriving ancilla-free pseudorandom unitaries (PRUs) from PRFSGs, and (ii) a natural way of constructing super-log-length output PRSGs from log-length output PRFSGs. The latter partly complements the known hardness of shrinking the PRSG output lengths. These partial results highlight technical difficulties when dealing with ancillary registers, measurements, and adaptivity in the quantum setting. Along the way, we also show an intriguing \emph{gentle} behavior of intermediate measurements in algorithms producing outcome states with high purity, which may be of independent interest. All our worlds are based on (variants of) oracles that output Haar random quantum states for each bit string, which can be viewed as a quantum version of the random oracle model, where output strings are replaced by quantum states.