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

Lecture notes in computer science

Solving the Learning Parity with Noise Problem Using Quantum Algorithms

Bénédikt Tran, Serge Vaudenay B

Published Jan 1, 2022• 0 citations
Publisher
DOI
10.1007/978-3-031-17433-9_13

Related papers

On Noise-Tolerant Learning of Sparse Parities and Related Problems

Elena Grigorescu, Lev Reyzin, Santosh Vempala

Lecture notes in computer science•Jan 1, 2011•20 citations

Quantum learning robust to noise

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

Bulletin of the American Physical Society•Mar 4, 2015•3 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•1 citation

Solving Learning Parity with Noise on an Optical Coherent Ising Machine

Woji He, Bei Zhou, Qiming Du +2 more

The Learning Parity with Noise (LPN) problem is a fundamental hard problem in cryptography and computational learning theory, whose difficulty increases sharply with the noise rate. Here we show that LPN can be reformulated as a combinatorial optimization problem and encoded into an Ising Hamiltonian, enabling solution by physical Ising solvers. As a proof of concept, we solve a structured large-scale case, in which each constraint involves at most two variables, with 512 variables and a 0.45 noise rate on an optical coherent Ising machine (CIM). Numerical experiments using simulated annealing on the same Hamiltonian formulation achieve substantially higher success rates than classical algebraic algorithms in the high-noise regime. This work establishes a physical-computing pathway for the LPN problem, demonstrating that hard algebraic problems can be addressed through Ising-model optimization.

Communications Physics•Sep 15, 2026•0 citations

Efficient learning of quantum noise

Robin Harper, Steven T. Flammia, Joel J. Wallman

arXiv:1907.13022•Nature Physics•Aug 10, 2020•253 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•2 citations
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.
The Learning Parity with Noise (LPN) problem is a fundamental hard problem in cryptography and computational learning theory, whose difficulty increases sharply with the noise rate. Here we show that LPN can be reformulated as a combinatorial optimization problem and encoded into an Ising Hamiltonian, enabling solution by physical Ising solvers. As a proof of concept, we solve a structured large-scale case, in which each constraint involves at most two variables, with 512 variables and a 0.45 noise rate on an optical coherent Ising machine (CIM). Numerical experiments using simulated annealing on the same Hamiltonian formulation achieve substantially higher success rates than classical algebraic algorithms in the high-noise regime. This work establishes a physical-computing pathway for the LPN problem, demonstrating that hard algebraic problems can be addressed through Ising-model optimization.
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.