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 classical pseudorandomness, where different notions are known to be existentially equivalent, the relations between quantum pseudorandomness notions have yet to be fully established. We present evidence suggesting that some forms of quantum pseudorandomness are unlikely to be constructed from others, indicating that quantum pseudorandomness behaves quite differently from its classical counterpart. 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 suggests that the inverse-polynomial error in state-of-the-art constructions of QPRGs from log-length PRSGs is inherent. To achieve this, we prove a novel geometric barrier theorem for the product Haar measure on quantum states, replacing 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 obtain separations showing limitations of: (i) deriving ancilla-free PRUs from PRFSGs, and (ii) a natural way of constructing super-log-length PRSGs from log-length PRFSGs. These results highlight technical difficulties when dealing with ancillary registers, measurements, and adaptivity in the quantum setting. We also show an intriguing gentle behavior of intermediate measurements in algorithms producing high-purity outcome states, which may be of independent interest. All our results are based on (variants of) oracles outputting Haar random quantum states per bit string - a quantum analogue of the random oracle model.