Quantum Pseudorandom Scramblers
SIAM Journal on Computing · 31.08.2026 · 55 (4) · 787-850
DOI: 10.1137/24m170990x ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 21.08.2026. Verfasst von Chuhan Lu und 4 weiteren Autor:innen. Die Arbeit nennt 64 Literaturangaben. Gefördert von: National Science Foundation, National Natural Science Foundation of China, Quantum Science and Technology-National Science and Technology Major Project.
Abstract (Originalsprache)
Quantum pseudorandom state generators ( PRSG s) have stimulated exciting developments in recent years. A PRSG , on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states. In this work, we propose and construct quantum pseudorandom state scramblers ( PRSS s), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an [Formula: see text]-net of the state space. This significantly strengthens what standard PRSG s can induce, as they may only concentrate on a small region of the state space provided that the average output state approximates a Haar random state. Our PRSS construction develops a parallel extension of the famous Kac’s walk, and we show that it mixes exponentially faster than the standard Kac’s walk. This constitutes the core of our proof. We also describe a few applications of PRSS s. While our PRSS construction assumes a postquantum one-way function, PRSS s are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSG s.
Förderung
- National Science Foundation
- National Natural Science Foundation of China
- Quantum Science and Technology-National Science and Technology Major Project
- NSFC/RGC
- Natural Science Foundation of Jiangsu Province
- Ministry of Education of China
- Fundamental Research Funds for the Central Universities
Zitieren
APA
Lu, C., Qin, M., Song, F., Yao, P., & Zhao, M. (2026). Quantum Pseudorandom Scramblers. SIAM Journal on Computing, 55(4), 787-850. https://doi.org/10.1137/24m170990x
Vancouver
Lu C, Qin M, Song F, Yao P, Zhao M. Quantum Pseudorandom Scramblers. SIAM Journal on Computing. 2026;55(4):787-850. doi:10.1137/24m170990x
BibTeX
@article{Lu2026,
author = {Lu, Chuhan and Qin, Minglong and Song, Fang and Yao, Penghui and Zhao, Mingnan},
title = {Quantum Pseudorandom Scramblers},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {4},
pages = {787--850},
doi = {10.1137/24m170990x}
}
EUVIMED