Skip to content
DraconiticResearch
Search Sources API
201,642 studies31 sourcesUpdated 12 min ago
PreprintarXiv licencearXiv

No linear stretching of single-copy quantum pseudorandomness

  • Boyang Chen
  • Andrea Coladangelo
  • Yao-Ting Lin
  • Nikos Skoumios
  • Justin Tysdal
  • Yiming Wang
Open at sourcePDFDOICite

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.

Related

  1. The Single-Copy Quantum Bandit Is Classical: An Exact Spectral Collapse
    Siu Hin Ng
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  2. Optimal single-copy estimation of quantum state moments: why Tr(ρ3) and Tr(ρ4) are equally hard
    Zhenhuan Liu
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  3. Learning Random Quantum Circuits and the Emergence of Pseudorandomness
    Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  4. On the pseudorandomness of simple quantum processes
    Jesko Dujmovic, Jonas Haferkamp, Alexander Poremba
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  5. Temporal stretching of single-photon pulses by intra-cavity frequency conversion
    Mathias L. H. Korsgaard, Eva M. González-Ruiz, Anders S. Sørensen
    arXivPreprintarXiv licenceFull textOptics & photonicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026linear,
  title = {{No linear stretching of single-copy quantum pseudorandomness}},
  author = {Boyang Chen and Andrea Coladangelo and Yao-Ting Lin and Nikos Skoumios and Justin Tysdal and Yiming Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2606.24736},
  eprint = {2606.24736},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.24736},
}
RIS
TY  - UNPB
TI  - No linear stretching of single-copy quantum pseudorandomness
AU  - Boyang Chen
AU  - Andrea Coladangelo
AU  - Yao-Ting Lin
AU  - Nikos Skoumios
AU  - Justin Tysdal
AU  - Yiming Wang
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2606.24736
UR  - https://arxiv.org/abs/2606.24736
AB  - 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.
ER  -