On the Limits of Stretching Quantum Pseudorandomness

Quantum Physics [Submitted on 23 Jun 2026] On the Limits of Stretching Quantum Pseudorandomness Boyang Chen, Andrea Coladangelo, Yao-Ting Lin, Nikos Skoumios, Justin Tysdal, Yiming Wang Pseudorandom states, introduced by Ji, Liu, and Song (CRYPTO '18), 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 remains unclear. In this work, we prove the first black-box separation between single-copy secure pseudorandom states (\mathsf{1PRS}) with different output lengths. Specifically, we construct a quantum oracle relative to which \mathsf{1PRS} with output length m(n)=1.1n exist, but \mathsf{1PRS} with output length m(n)=\Omega(n^{2+\epsilon}) do not, for any \epsilon>0. Our proof leverages the Common Haar Random State (CHRS) model introduced by Chen, Coladangelo, and Sattath (EUROCRYPT '25), and introduces a technique to bound the effective number of resource CHRS states utilized by any \mathsf{1PRS} generator in this model. Subjects: Quantum Physics (quant-ph); Cryptography and Security (cs.CR) Cite as: arXiv:2606.24736 [quant-ph]   (or arXiv:2606.24736v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2606.24736 Focus to learn more Submission history From: Yiming Wang [view email] [v1] Tue, 23 Jun 2026 16:00:17 UTC (58 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-06 Change to browse by: cs cs.CR References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)