The power of a single Haar random state: constructing and separating quantum pseudorandomness
<|reference_start|>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 show, perhaps surprisingly, that such an oracle is sufficient to construct quantum pseudorandomness.   Pseudorandom states (PRS) 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 (1PRS), satisfies this property with respect to a single copy. We obtain the following results:   1. First, we show, perhaps surprisingly, that 1PRS (as well as bit-commitments) exist relative to an oracle that provides a single Haar random state.   2. Second, we build on this result to show the existence of a unitary oracle relative to which 1PRS exist, but PRS do not.   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.<|reference_end|>
@article{chen2024the,
    title={The power of a single Haar random state: constructing and separating
  quantum pseudorandomness},
    author={Boyang Chen, Andrea Coladangelo, Or Sattath},
    journal={arXiv preprint arXiv:2404.03295},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.03295},
    primaryClass={quant-ph cs.CR}
}