Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.19819

Quantum approaches to learning parity with noise

Daniel Shiu

Published Feb 23, 2026• 0 citations
arXivHTMLPDF

Abstract

The learning parity with noise (LPN) problem is a well-established computational challenge whose difficulty is critical to the security of several post-quantum cryptographic primitives such as HQC and Classic McEliece. Classically, the best-known attacks involve information set decoding methods which are exponential in complexity for parameterisations of interest. In this paper we investigate whether quantum methods might offer alternative approaches. The line of inquiry is inspired by Regev's relating of certain lattice problems to the hidden dihedral subgroup problem. We use neighbourhoods of binary fields to produce a function close to fulfilling Simon's promise with difference equal to the secret parity vector. Although unlikely to recover the secret parity vector directly, running Simon's algorithm essentially produces new LPN samples. This gives the hope that we might be able to produce enough new samples to ignore one or more variables and iteratively reduce the problem. We make no claim that these methods will necessarily be competitive with existing approaches, merely that they warrant deeper investigation.

DOI
10.48550/arxiv.2602.19819

Related papers

Quantum learning robust against noise

Andrew W. Cross, Graeme Smith, John A. Smolin

Noise is often regarded as anathema to quantum computation, but in some settings it can be an unlikely ally. We consider the problem of learning the class of $n$-bit parity functions by making queries to a quantum example oracle. In the absence of noise, quantum and classical parity learning are easy and almost equally powerful, both information-theoretically and computationally. We show that in the presence of noise this story changes dramatically. Indeed, the classical learning problem is believed to be intractable, while the quantum version remains efficient. Depolarizing the qubits at the oracle's output at any constant nonzero rate does not increase the computational (or query) complexity of quantum learning more than logarithmically. However, the problem of learning from corresponding classical examples is the learning parity with noise problem, for which the best known algorithms have superpolynomial complexity. This creates the possibility of observing a quantum advantage with a few hundred noisy qubits. The presence of noise is essential for creating this quantum-classical separation.

arXiv:1407.5088•Physical Review A•Jul 27, 2015•85 citations

The Learning Stabilizers with Noise Problem

Alexander Poremba, Yihui Quek, Peter W. Shor

Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) problem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise. We give both polynomial-time and exponential-time quantum algorithms for solving LSN in various depolarizing noise regimes, ranging from extremely low noise, to low constant noise rates, and even higher noise rates up to a threshold. Next, we provide concrete evidence that LSN is hard. First, we show that LSN includes LPN as a special case, which suggests that it is at least as hard as its classical counterpart. Second, we prove worst-case to average-case reductions for variants of LSN. We then ask: what is the computational complexity of solving LSN? Because the task features quantum inputs, its complexity cannot be characterized by traditional complexity classes. Instead, we show that the LSN problem lies in a recently introduced (distributional and oracle) unitary synthesis class. Finally, we identify several applications of our LSN assumption, ranging from the construction of quantum bit commitment schemes to the computational limitations of learning from quantum data.

arXiv:2410.18953•Leibniz international proceedings in informatics•Oct 24, 2024•11 citations

Analysis of learning with errors problems with variational quantum algorithms

Jinfeng Zeng, Muxi Zheng, Hang Li +2 more

Abstract Variational Quantum Algorithms (VQAs) offer a promising approach to solving optimization problems on quantum computers. In this paper, we investigate the use of VQAs to solve the Learning With Errors (LWE) problem, a crucial challenge in post-quantum cryptography. We propose a VQA-based algorithm and a Quantum Approximate Optimization Algorithm (QAOA) for solving the Learning Parity with Noise (LPN) problem, a special case of LWE. We examine the sample complexity of combinatorial optimization methods for LPN and analyze the performance of these two variational quantum algorithms in terms of quantum resources. For the VQA algorithm, both the number of qubits and the circuit depth scale polynomially with the secret key length n . In the case of QAOA, the number of qubits matches the secret key length n , but the CNOT gate count increases exponentially with n . However, numerical simulations of the VQA-based algorithm show that choosing optimal ansatzes and optimization methods can significantly enhance success rates.

Europhysics Letters (EPL)•May 15, 2025•3 citations

Post-Quantum Cryptography from Quantum Stabilizer Decoding

Jonathan Z. Lu, Alexander Poremba, Yihui Quek +1 more

Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes---a quantum analog of the well-studied LPN problem---is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practically efficient: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption. Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suite of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.

quant-pharXiv:2603.19110•Lecture notes in computer science•Mar 20, 2026•1 citation

Superposition Attacks Against LPN-Based Authentication Protocols

Carlos Del Cid, David Elkouss, Manuel Goulão

Quantum security most commonly encompasses only offline passive quantum attacks, where a quantum computer is used by an adversary to solve some computationally hard problem, e.g. factoring or discrete logarithm. However, we are witnessing major efforts for the development and deployment of quantum communication networks, and in this environment, cryptographic protocols may also be implemented in quantum devices. In this new setting, a wider range of online active attacks may become possible, for example against targets that may, either deliberately or inadvertently, run a cryptographic scheme in superposition. In this work, we demonstrate that authentication protocols whose security is based on the difficulty of learning linear functions subject to errors may be vulnerable to attacks where adversaries can make queries in superposition — that is, under the so-called “Q2” adversarial model. We do so by describing superposition attacks against a family of symmetric-key authentication protocols based on the LPN problem, a post-quantum cryptography assumption. Our attacks against the HB+ and HB# protocols, both of which have classical proofs of security against active attacks, are based on the Bernstein-Vazirani algorithm, and can efficiently recover the secret key. Despite being conceptually simple, we suggest that our attack techniques might be extended and adapted to also allow for superposition attacks against some modern lattice-based identification and post-quantum signature schemes.

IACR Communications in Cryptology•May 4, 2026•0 citations

Quantum Pseudorandom Error-Correcting Codes

Min-Hsiu Hsieh, Shogo Yamada

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.38986•Oct 1, 2026•0 citations
The learning parity with noise (LPN) problem is a well-established computational challenge whose difficulty is critical to the security of several post-quantum cryptographic primitives such as HQC and Classic McEliece. Classically, the best-known attacks involve information set decoding methods which are exponential in complexity for parameterisations of interest. In this paper we investigate whether quantum methods might offer alternative approaches. The line of inquiry is inspired by Regev's relating of certain lattice problems to the hidden dihedral subgroup problem. We use neighbourhoods of binary fields to produce a function close to fulfilling Simon's promise with difference equal to the secret parity vector. Although unlikely to recover the secret parity vector directly, running Simon's algorithm essentially produces new LPN samples. This gives the hope that we might be able to produce enough new samples to ignore one or more variables and iteratively reduce the problem. We make no claim that these methods will necessarily be competitive with existing approaches, merely that they warrant deeper investigation.
Noise is often regarded as anathema to quantum computation, but in some settings it can be an unlikely ally. We consider the problem of learning the class of nnn-bit parity functions by making queries to a quantum example oracle. In the absence of noise, quantum and classical parity learning are easy and almost equally powerful, both information-theoretically and computationally. We show that in the presence of noise this story changes dramatically. Indeed, the classical learning problem is believed to be intractable, while the quantum version remains efficient. Depolarizing the qubits at the oracle's output at any constant nonzero rate does not increase the computational (or query) complexity of quantum learning more than logarithmically. However, the problem of learning from corresponding classical examples is the learning parity with noise problem, for which the best known algorithms have superpolynomial complexity. This creates the possibility of observing a quantum advantage with a few hundred noisy qubits. The presence of noise is essential for creating this quantum-classical separation.
Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) problem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise. We give both polynomial-time and exponential-time quantum algorithms for solving LSN in various depolarizing noise regimes, ranging from extremely low noise, to low constant noise rates, and even higher noise rates up to a threshold. Next, we provide concrete evidence that LSN is hard. First, we show that LSN includes LPN as a special case, which suggests that it is at least as hard as its classical counterpart. Second, we prove worst-case to average-case reductions for variants of LSN. We then ask: what is the computational complexity of solving LSN? Because the task features quantum inputs, its complexity cannot be characterized by traditional complexity classes. Instead, we show that the LSN problem lies in a recently introduced (distributional and oracle) unitary synthesis class. Finally, we identify several applications of our LSN assumption, ranging from the construction of quantum bit commitment schemes to the computational limitations of learning from quantum data.
Abstract Variational Quantum Algorithms (VQAs) offer a promising approach to solving optimization problems on quantum computers. In this paper, we investigate the use of VQAs to solve the Learning With Errors (LWE) problem, a crucial challenge in post-quantum cryptography. We propose a VQA-based algorithm and a Quantum Approximate Optimization Algorithm (QAOA) for solving the Learning Parity with Noise (LPN) problem, a special case of LWE. We examine the sample complexity of combinatorial optimization methods for LPN and analyze the performance of these two variational quantum algorithms in terms of quantum resources. For the VQA algorithm, both the number of qubits and the circuit depth scale polynomially with the secret key length n . In the case of QAOA, the number of qubits matches the secret key length n , but the CNOT gate count increases exponentially with n . However, numerical simulations of the VQA-based algorithm show that choosing optimal ansatzes and optimization methods can significantly enhance success rates.
Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes---a quantum analog of the well-studied LPN problem---is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practically efficient: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption. Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suite of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.
Quantum security most commonly encompasses only offline passive quantum attacks, where a quantum computer is used by an adversary to solve some computationally hard problem, e.g. factoring or discrete logarithm. However, we are witnessing major efforts for the development and deployment of quantum communication networks, and in this environment, cryptographic protocols may also be implemented in quantum devices. In this new setting, a wider range of online active attacks may become possible, for example against targets that may, either deliberately or inadvertently, run a cryptographic scheme in superposition. In this work, we demonstrate that authentication protocols whose security is based on the difficulty of learning linear functions subject to errors may be vulnerable to attacks where adversaries can make queries in superposition — that is, under the so-called “Q2” adversarial model. We do so by describing superposition attacks against a family of symmetric-key authentication protocols based on the LPN problem, a post-quantum cryptography assumption. Our attacks against the HB+ and HB# protocols, both of which have classical proofs of security against active attacks, are based on the Bernstein-Vazirani algorithm, and can efficiently recover the secret key. Despite being conceptually simple, we suggest that our attack techniques might be extended and adapted to also allow for superposition attacks against some modern lattice-based identification and post-quantum signature schemes.
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 2O(n)2^{O(\sqrt{n})}2O(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(nlog⁡log⁡nlog⁡n)o(n \frac{\log \log n}{\log n})o(nlognloglogn​)-local quantum noise, where nnn 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αnαn-local quantum noise for some constant α>0α>0α>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].