Quantum Pseudorandom Error-Correcting Codes

@misc{hsieh2026quantum,
  title = {{Quantum Pseudorandom Error-Correcting Codes}},
  author = {Min-Hsiu Hsieh and Shogo Yamada},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38986},
  eprint = {2609.38986},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38986},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Quantum Pseudorandom Error-Correcting Codes
AU  - Min-Hsiu Hsieh
AU  - Shogo Yamada
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.38986
UR  - https://arxiv.org/abs/2609.38986
AB  - Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn [CRYPTO 2024], are classical error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings. We initiate the study of quantum analogues of PRCs. We define quantum pseudorandom error-correcting codes (QPRCs). Assuming that Learning Parity with Noise (LPN) is hard for 2^O(√n)-time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all o(n (log log n)/(log n))-local quantum noise, where n is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all αn-local quantum noise for some constant α>0. The latter QPRCs give a direct quantum analogue of classical PRCs. To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].
ER  -