Solving Learning Parity with Noise on an Optical Coherent Ising Machine

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.