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].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].

quant-pharXiv:2609.38986Oct 1, 20260 citations

Error Correcting Codes

Peter M Kosek

Error correcting codes is an area of mathematics that combines many theoretical concepts with a wide variety of applications.In this expository thesis, we will begin by introducing many of the fundamental ideas in classical error correcting codes.The goal of this is to introduce the reader to the field of coding theory and discuss a few of the wide range of classical codes that have been studied.The second section will discuss the recent findings in error correcting codes, namely their use in quantum error correcting codes.This section uses much more theoretical areas of math, when compared to the classical section, in the construction of quantum error correcting codes.Most of the research discussed in this section has been completed within the past six years.All of the research discoveries presented in this thesis have been previously known.Error correcting codes is an area of mathematics that combines many theoretical concepts with a wide variety of applications.In this expository thesis, we will begin by introducing many of the fundamental ideas in classical error correcting codes.The goal of this is to introduce the reader to the field of coding theory and discuss a few of the wide range of classical codes that have been studied.The second section will discuss the recent findings in error correcting codes, namely their use in quantum error correcting codes.This section uses much more theoretical areas of math, when compared to the classical section, in the construction of quantum error correcting codes.Most of the research discussed in this section has been completed within the past six years.All of the research discoveries presented in this thesis have been previously known.

Jan 1, 20140 citations

Information Theory and Classical Error Correcting Codes

Ivan B. Djordjević

Elsevier eBooksJan 1, 20211 citation

Applications of Error Correcting Codes

Marco Chiani

Mar 2, 20090 citations

Theory of Quantum Error Correction for General Noise

Emanuel H. Knill, Raymond Laflamme, Lorenza Viola

A measure of quality of an error-correcting code is the maximum number of errors that it is able to correct. We show that a suitable notion of "number of errors" e makes sense for any quantum or classical system in the presence of arbitrary interactions. Thus, e-error-correcting codes protect information without requiring the usual assumptions of independence. We prove the existence of large codes for both quantum and classical information. By viewing error-correcting codes as subsystems, we relate codes to irreducible representations of operator algebras and show that noiseless subsystems are infinite-distance error-correcting codes.A measure of quality of an error-correcting code is the maximum number of errors that it is able to correct. We show that a suitable notion of "number of errors" e makes sense for any quantum or classical system in the presence of arbitrary interactions. Thus, e-error-correcting codes protect information without requiring the usual assumptions of independence. We prove the existence of large codes for both quantum and classical information. By viewing error-correcting codes as subsystems, we relate codes to irreducible representations of operator algebras and show that noiseless subsystems are infinite-distance error-correcting codes.

arXiv:quant-ph/9604034Physical Review LettersMar 13, 2000866 citations

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].