arXiv:2609.38986
Quantum Pseudorandom Error-Correcting Codes
Min-Hsiu Hsieh, Shogo Yamada
Abstract
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(\sqrt{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 \frac{\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].
AI Summary
Can efficient quantum error correction coexist with encodings that look computationally random, even under coherent oracle queries? This paper defines quantum pseudorandom error-correcting codes (QPRCs) and constructs two variants, assuming LPN is hard for $2^{O(\sqrt n)}$-time quantum algorithms, with $n$ denoting the LPN secret length. Pseudorandom isometric codes (PRICs) have encodings indistinguishable from a fixed Haar-random isometry. They achieve constant encoding rate and correct arbitrary $t$-local quantum noise for every $t=o(N\log\log N/\log N)$, where $N$ is the physical-qubit count. A second, public-key construction has encodings indistinguishable from the completely depolarizing channel and corrects $\alpha N$-local noise for some constant $\alpha>0$, also at constant rate. It combines an ordinary QECC with a quantum one-time pad whose keys are protected by classical pseudorandom codes. The PRIC construction introduces pseudorandom functional codes: deterministic classical encoders that are quantum-query-secure pseudorandom functions and permit decoding after a constant fraction of bit flips. These yield isometries correcting bit errors. A codeword-stabilized graph layer extends recovery to phase errors through an efficient randomized-graph decoding procedure. This also gives a black-box, keyed quantum-code construction from efficiently decodable nonlinear classical codes. Recovery guarantees concern the key-averaged channel in diamond distance and key-independent noise, not adaptive attacks informed by encoding queries. The CWS decoding result is correspondingly keyed rather than a decoder for arbitrary CWS codes. Linear-error robustness for PRICs remains open, as do stronger adaptive robustness notions and quantum watermarking, steganography, or chaotic-system applications.
Codex and Claude Code assisted with drafting and editing the manuscript.
Error found: The abstract overstates the CWS decoding result: the paper proves efficient decoding for a specially sampled keyed construction against key-independent noise, averaged over the key, rather than a general efficient decoder for arbitrary CWS codes.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 73 pages, 2 figures