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

Communications Physics

Solving Learning Parity with Noise on an Optical Coherent Ising Machine

Woji He, Bei Zhou, Qiming Du, Jinchen Xu, Zheng Shan

Published Sep 15, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1038/s42005-026-02868-1

Related papers

Physical coherent Ising machines for solving combinatorial optimization problems

Yoonhyuk Rah, Kyoungsik Yu

Abstract Coherent Ising machines (CIM) have shown promising potential as hardware solvers for tackling combinatorial optimization problems, where discrete variables are encoded onto physical states to form an Ising Hamiltonian. Various platforms, starting from optical parametric oscillators, have been proposed and demonstrated to implement an actual physical CIM. In this review article, we briefly introduce the basic operation principle of CIMs and review physical schemes focusing on MEMS-based nanophotonics.

Japanese Journal of Applied Physics•Feb 27, 2026•0 citations

100,000-spin coherent Ising machine

Toshimori Honjo, Tomohiro Sonobe, Kensuke Inaba +9 more

Computers based on physical systems are increasingly anticipated to overcome the impending limitations on digital computer performance. One such computer is a coherent Ising machine (CIM) for solving combinatorial optimization problems. Here, we report a CIM with 100,512 degenerate optical parametric oscillator pulses working as the Ising spins. We show that the CIM delivers fine solutions to maximum cut problems of 100,000-node graphs drastically faster than standard simulated annealing. Moreover, the CIM, when operated near the phase transition point, provides some extremely good solutions and a very broad distribution. This characteristic will be useful for applications that require fast random sampling such as machine learning.

Science Advances•Sep 29, 2021•340 citations

Coherent Ising machines: models for architectures and applications

Edwin Ng, Tatsuhiro Onodera, Ryotatsu Yanagimoto +3 more

Coherent Ising machines (CIMs) are an experimentally promising class of physics-based computational architectures that embed hard combinatorial optimization problems into systems of coupled nonlinear optical oscillators. The solution-finding mechanisms employed by CIMs feature complicated dynamical bifurcations occurring on a network scale, posing significant challenges to the development of theory and models for their underlying principles of operation. These difficulties are especially pronounced in the ultra-low-power or quantum regimes where the benefits in computational efficiency over conventional optimization algorithms are expected to be largest. We discuss some of our recent approaches and results at this intersection of dynamical systems theory and quantum model reduction, which have highlighted some potentially useful architectures and applications on the horizon for CIMs.

AI and Optical Data Sciences•Mar 9, 2022•0 citations

A single shot coherent Ising machine based on a network of injection-locked multicore fiber lasers

Masoud Babaeian, Dan Trung Nguyen, Veysi Demir +6 more

Combinatorial optimization problems over large and complex systems have many applications in social networks, image processing, artificial intelligence, computational biology and a variety of other areas. Finding the optimized solution for such problems in general are usually in non-deterministic polynomial time (NP)-hard complexity class. Some NP-hard problems can be easily mapped to minimizing an Ising energy function. Here, we present an analog all-optical implementation of a coherent Ising machine (CIM) based on a network of injection-locked multicore fiber (MCF) lasers. The Zeeman terms and the mutual couplings appearing in the Ising Hamiltonians are implemented using spatial light modulators (SLMs). As a proof-of-principle, we demonstrate the use of optics to solve several Ising Hamiltonians for up to thirteen nodes. Overall, the average accuracy of the CIM to find the ground state energy was ~90% for 120 trials. The fundamental bottlenecks for the scalability and programmability of the presented CIM are discussed as well.

Nature Communications•Aug 6, 2019•95 citations

A coherent Ising machine with quantum measurement and feedback control

Yoshitaka Haribara, Y. Yamamoto, Ken‐ichi Kawarabayashi +1 more

Combinatorial optimization problems are computationally hard in general, but they are ubiquitous in our modern life. A coherent Ising machine (CIM) based on a multiple-pulse degenerate optical parametric oscillator (DOPO) is an alternative approach to solve these problems by a specialized physical computing system. To evaluate its potential performance, computational experiments are performed on maximum cut (MAX-CUT) problems against traditional algorithms such as semidefinite programming relaxation of Goemans-Williamson and simulated annealing by Kirkpatrick, et al. The numerical results empirically suggest that the almost constant computation time is required to obtain the reasonably accurate solutions of MAX-CUT problems on a CIM with the number of vertices up to $2 \times 10^4$ and the number of edges up to $10^8$.

•Jan 28, 2015•5 citations

Coherent Ising machines based on optical parametric oscillators

Hideo Mabuchi, Surya Ganguli, Daniel Wennberg +3 more

Coherent Ising Machines (CIMs) are an emerging class of computational architectures that embed hard combinatorial optimization problems in the continuous dynamics of a physical system with analog degrees of freedom. While crisp theoretical results on the ultimate performance and scaling of such architectures are lacking, large-scale experimental prototypes have begun to exhibit promising results in practice. Our team at Stanford has begun to study the fundamental properties of CIM dynamics using a combination of techniques from statistical physics, random matrices, and dynamical systems theory. Many connections to recent work in neuroscience and deep learning are noted. Our work focuses specifically on CIMs that utilize the nonlinear threshold behavior of optical parametric oscillators to effect a soft (potentially glassy) transition between linear and binary dynamical regimes.

AI and Optical Data Sciences•Mar 4, 2021•0 citations
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.
Abstract Coherent Ising machines (CIM) have shown promising potential as hardware solvers for tackling combinatorial optimization problems, where discrete variables are encoded onto physical states to form an Ising Hamiltonian. Various platforms, starting from optical parametric oscillators, have been proposed and demonstrated to implement an actual physical CIM. In this review article, we briefly introduce the basic operation principle of CIMs and review physical schemes focusing on MEMS-based nanophotonics.
Computers based on physical systems are increasingly anticipated to overcome the impending limitations on digital computer performance. One such computer is a coherent Ising machine (CIM) for solving combinatorial optimization problems. Here, we report a CIM with 100,512 degenerate optical parametric oscillator pulses working as the Ising spins. We show that the CIM delivers fine solutions to maximum cut problems of 100,000-node graphs drastically faster than standard simulated annealing. Moreover, the CIM, when operated near the phase transition point, provides some extremely good solutions and a very broad distribution. This characteristic will be useful for applications that require fast random sampling such as machine learning.
Coherent Ising machines (CIMs) are an experimentally promising class of physics-based computational architectures that embed hard combinatorial optimization problems into systems of coupled nonlinear optical oscillators. The solution-finding mechanisms employed by CIMs feature complicated dynamical bifurcations occurring on a network scale, posing significant challenges to the development of theory and models for their underlying principles of operation. These difficulties are especially pronounced in the ultra-low-power or quantum regimes where the benefits in computational efficiency over conventional optimization algorithms are expected to be largest. We discuss some of our recent approaches and results at this intersection of dynamical systems theory and quantum model reduction, which have highlighted some potentially useful architectures and applications on the horizon for CIMs.
Combinatorial optimization problems over large and complex systems have many applications in social networks, image processing, artificial intelligence, computational biology and a variety of other areas. Finding the optimized solution for such problems in general are usually in non-deterministic polynomial time (NP)-hard complexity class. Some NP-hard problems can be easily mapped to minimizing an Ising energy function. Here, we present an analog all-optical implementation of a coherent Ising machine (CIM) based on a network of injection-locked multicore fiber (MCF) lasers. The Zeeman terms and the mutual couplings appearing in the Ising Hamiltonians are implemented using spatial light modulators (SLMs). As a proof-of-principle, we demonstrate the use of optics to solve several Ising Hamiltonians for up to thirteen nodes. Overall, the average accuracy of the CIM to find the ground state energy was ~90% for 120 trials. The fundamental bottlenecks for the scalability and programmability of the presented CIM are discussed as well.
Combinatorial optimization problems are computationally hard in general, but they are ubiquitous in our modern life. A coherent Ising machine (CIM) based on a multiple-pulse degenerate optical parametric oscillator (DOPO) is an alternative approach to solve these problems by a specialized physical computing system. To evaluate its potential performance, computational experiments are performed on maximum cut (MAX-CUT) problems against traditional algorithms such as semidefinite programming relaxation of Goemans-Williamson and simulated annealing by Kirkpatrick, et al. The numerical results empirically suggest that the almost constant computation time is required to obtain the reasonably accurate solutions of MAX-CUT problems on a CIM with the number of vertices up to 2×1042 \times 10^42×104 and the number of edges up to 10810^8108.
Coherent Ising Machines (CIMs) are an emerging class of computational architectures that embed hard combinatorial optimization problems in the continuous dynamics of a physical system with analog degrees of freedom. While crisp theoretical results on the ultimate performance and scaling of such architectures are lacking, large-scale experimental prototypes have begun to exhibit promising results in practice. Our team at Stanford has begun to study the fundamental properties of CIM dynamics using a combination of techniques from statistical physics, random matrices, and dynamical systems theory. Many connections to recent work in neuroscience and deep learning are noted. Our work focuses specifically on CIMs that utilize the nonlinear threshold behavior of optical parametric oscillators to effect a soft (potentially glassy) transition between linear and binary dynamical regimes.