No linear stretching of single-copy quantum pseudorandomness

Abstract

Pseudorandom states, introduced by Ji, Liu, and Song (CRYPTO 2018), are quantum analogues of classical pseudorandom generators. A fundamental property of classical pseudorandom generators is that their output can be stretched to arbitrary polynomial length. Whether an analogous stretching property holds for quantum pseudorandom states has been elusive. Here, we essentially resolve this question for the single-copy variant of pseudorandom states, 1PRS. We show, via a unitary oracle separation, that no fully black-box construction can stretch the output length of a 1PRS by any constant factor greater than one.