Curator's Take
This article shows that a Coherent Ising Machine can solve Learning‑With‑Errors instances without the usual penalty terms, turning the cryptographic noise directly into the QUBO objective and dramatically cutting qubit and coefficient overhead. By embedding LWE as a Closest Vector Problem and using a continuous‑relaxed Babai projection, the authors achieve a penalty‑free, hardware‑aware mapping that scales to 40‑dimensional challenges on a NISQ‑class CIM. If the approach generalises, it could provide a new quantum‑accelerated attack vector against post‑quantum lattice schemes and also inspire more efficient hybrid algorithms for other combinatorial optimisation problems. However, the demonstration is limited to modest dimensions and a specialised optical processor, so further work will be needed to assess scalability to cryptographically relevant sizes.
— Mark Eatherly
Summary
The Learning With Errors (LWE) problem constitutes the mathematical foundation of modern Post-Quantum Cryptography (PQC). Cryptanalysis of LWE ranges from classical lattice reduction to machine learning and quantum-classical hybrids. We propose CIM-BDD, a hybrid Bounded-Distance-Decoding solver that reduces LWE to a Quadratic Unconstrained Binary Optimization (QUBO) problem through a strictly \emph{penalty-free} mapping. An algebraic elimination of the secret embeds LWE into a $q$-ary lattice, absorbing the modular arithmetic and recasting the problem as a Closest Vector Problem (CVP). The squared error norm is then used \emph{directly} as the QUBO energy, so the cryptographic noise is the objective to be minimized rather than a penalized constraint. To realize this general model on current Noisy Intermediate-Scale Quantum (NISQ) devices, we design a special encoding method: a Continuous Relaxed Babai's Nearest Plane (CR-BNP) projection drives an adaptive mixed-radix encoder that greatly reduces both the qubit count and the QUBO coefficient range, so that a single batched hardware submission suffices. We further derive a statistically bounded early-stopping threshold ($T_{\text{early}}$) that acts as a one-sided certificate and doubles as a Decision-LWE distinguisher. We validate the framework on the TU Darmstadt LWE Challenge, giving an end-to-end demonstration for both Search- and Decision-LWE of a $40$-dimensional instance on the Coherent Ising Machine CPQC-550. This work establishes a new algorithm-hardware co-design paradigm for quantum-classical hybrid cryptanalysis.