The Power of a Single Haar Random State: Constructing and Separating Quantum Pseudorandomness
摘要
In this work, we focus on the following question: what are the cryptographic implications of having access to an oracle that provides a single Haar random quantum state? We find that the study of such a model sheds light on several aspects of the notion of quantum pseudorandomness. Pseudorandom states are a family of states for which it is hard to distinguish between polynomially many copies of either a state sampled uniformly from the family or a Haar random state. A weaker notion, called single-copy pseudorandom states ( \({\textsf{1PRS}}\) ), satisfies this property with respect to a single copy. We obtain the following results: Taken together, our contributions yield one of the first black-box separations between central notions of quantum pseudorandomness, and introduce a new framework to study black-box separations between various inherently quantum primitives.