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:2606.22843

When the Learning With Errors Problem Meets the Coherent Ising Machine: A Penalty-Free Algorithm-Hardware Co-Design

Shuxian Jiang

quant-phcs.CRSubmitted Jun 22, 2026• Announced Jun 23, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices

Muxi Zheng, Jinfeng Zeng, Wentao Yang +7 more

The Learning-With-Errors (LWE) problem is a fundamental computational challenge with implications for post-quantum cryptography and computational learning theory. Here we propose a quantum-classical hybrid algorithm with Ising model to address LWE, transforming it into the Shortest Vector Problem and using variable qubits to encode lattice vectors into an Ising Hamiltonian. By identifying low-energy Hamiltonian levels, the solution is extracted, making the method suitable for noisy intermediate-scale quantum devices. The required number of qubits is less than m(m + 1), where m is the number of samples. Our heuristic algorithm’s time complexity depends on the specific quantum eigensolver used to find low-energy levels, and the performance when using the Quantum Approximate Optimization Algorithm is investigated. We validate the algorithm by solving a 2-dimensional LWE problem on a 5-qubit quantum device, demonstrating its potential for solving meaningful LWE instances on near-term quantum devices. Evaluating the security of post-quantum cryptography is critically important to ensure resilience against quantum attacks. In this paper, the authors study a complex computational task at the heart of post-quantum cryptography with a hybrid quantum-classical algorithm, heuristically finding some advantages.

arXiv:2408.07936•Communications Physics•May 20, 2025•6 citations

QUBO Modeling of Module Learning With Errors: Stability and Scaling in Post-Quantum Cryptography

Ruturaj Khamitkar, Durga Pritam Suggisetti, Soujanya Chatti +2 more

Lattice-based post-quantum cryptography relies on the hardness of the Learning With Errors (LWE) and Module Learning With Errors (MLWE) problems. This work introduces a constructive framework for encoding small MLWE instances as Quadratic Unconstrained Binary Optimization (QUBO) models suitable for quantum annealing. The formulation jointly represents secret coefficients and explicit error variables within a unified binary optimization structure, enabling their simultaneous recovery from the ground-state solution. Beyond the encoding, we develop a stability analysis of the resulting optimization landscape under additive perturbations. We show that the admissible noise region forms a convex polytope defined by competing candidate secrets, and establish an equivalent characterization in terms of the QUBO energy gap between the optimal and second-best solutions. Numerical experiments on low-dimensional benchmark instances using exact simulation demonstrate correct recovery of both secret and discretized error vectors, and confirm consistency between geometric stability regions and energy-gap behavior. We further quantify the scaling of logical variables and embedding overhead with increasing MLWE dimensions to assess feasibility on quantum annealing architectures. The results establish a systematic connection between MLWE problems and quantum optimization while providing a framework for analyzing robustness properties of QUBO formulations. Although current quantum annealing hardware remains insufficient for cryptographically relevant parameters, the proposed methodology offers a structured basis for studying lattice-based problems in quantum optimization settings without implying a practical threat to standardized post-quantum schemes.

quant-pharXiv:2607.05973•Jul 8, 2026•0 citations

HYBRID QUANTUM-CLASSICAL OPTIMIZATION FOR EFFICIENT AND NOISE-TOLERANT POST-QUANTUM CRYPTOGRAPHIC SYSTEMS

Vikas Sharma, Asha Joseph, Pushpendra Kumar Verma +2 more

The rapid advancement of quantum computing poses an existential threat to classical public-key cryptographic systems, necessitating the transition to post-quantum cryptography (PQC). However, the deployment of lattice-based PQC schemes such as CRYSTALS-Kyber and CRYSTALS-Dilithium faces significant challenges including computational complexity, noise sensitivity, resource constraints, and security vulnerabilities. This research presents a comprehensive hybrid quantum-classical optimization framework for efficient and noise-tolerant post-quantum cryptographic systems. The framework addresses three primary objectives: (1) developing a unified hybrid quantum-classical optimization architecture that integrates variational quantum algorithms (VQE, QAOA) and QUBO/Ising formulations with classical PQC primitives based on the Learning With Errors (LWE) and Module-LWE problems; (2) designing noise-tolerant PQC protocols through multi-layer noise modeling that characterizes cryptographic, quantum hardware, and classical implementation noise; and (3) enabling resource-aware deployment on constrained platforms including embedded systems, IoT devices, and edge computing nodes. Experimental evaluation demonstrates that the QUBO formulation achieves coefficient ranges suitable for NISQ devices with 99.2% of coefficients within [-1, 1] after normalization. The adaptive partitioning algorithm achieves time-to-solution improvements of 42% for large problem instances compared to classical-only execution. The noise-aware optimization framework achieves decryption failure rate improvements ranging from 2^10.8 to 2^16.8, with combined noise tolerance success rates exceeding 94.56% under severe conditions. Side-channel countermeasures achieve 82.6% reduction in exploitable information leakage, with power leakage correlation reduced from 0.23 to 0.04. The unified Kyber-Dilithium architecture achieves 21% memory savings and 10-11% performance improvements. Reinforcement learning-based scheduling reduces latency by 37% and energy consumption by 39% compared to static scheduling. End-to-end deployment evaluation across smart home, industrial IoT, healthcare, and autonomous vehicle scenarios demonstrates that the hybrid PQC system meets latency and energy requirements while maintaining target security levels. This research provides a practical pathway toward secure communication in the quantum era, bridging the gap between current classical systems and future quantum-enabled solutions.

Acta Innovations•Sep 25, 2026•0 citations

Cryptanalysis of LWE and SIS-based cryptosystems by using quantum annealing

A. Qayyum, M. S. (M. ) Haris

In the paper, we study lattice-based cryptographic problems, in particular Learning With Errors (LWE) and Short Integer Solution (SIS) lattice problems, which are considered to be known cryptographic primitives that are supposed to be secure against both classical and quantum attacks. We formulated the LWE and SIS problems as Mixed-Integer Programming (MIP) model and then converted them to Quadratic Unconstrained Binary Optimization (QUBO) problem, which can be solved by using a quantum annealer. Quantum annealing searches for the global minimum of an input objective function subjected to the given constraints to optimize the given model. We have estimated the q-bits required for the Quantum Processing Unit (QPU). Our results show that this approach can solve certain instances of the LWE and SIS problems efficiently.

•Jan 1, 2023•0 citations

Using Variational Quantum Algorithm to Solve the LWE Problem

Lihui Lv, Bao Yan, Hong Wang +4 more

The variational quantum algorithm (VQA) is a hybrid classical-quantum algorithm. It can actually run in an intermediate-scale quantum device where the number of available qubits is too limited to perform quantum error correction, so it is one of the most promising quantum algorithms in the noisy intermediate-scale quantum era. In this paper, two ideas for solving the learning with errors problem (LWE) using VQA are proposed. First, after reducing the LWE problem into the bounded distance decoding problem, the quantum approximation optimization algorithm (QAOA) is introduced to improve classical methods. Second, after the LWE problem is reduced into the unique shortest vector problem, the variational quantum eigensolver (VQE) is used to solve it, and the number of qubits required is calculated in detail. Small-scale experiments are carried out for the two LWE variational quantum algorithms, and the experiments show that VQA improves the quality of the classical solutions.

Entropy•Oct 8, 2022•9 citations

Quantum Search-to-Decision Reduction for the LWE Problem

Kyohei Sudo, Keisuke Hara, Masayuki Tezuka +1 more

The learning with errors (LWE) problem is one of the fundamental problems in cryptography and it has many applications in post-quantum cryptography. There are two variants of the problem, the decisional-LWE problem, and the search-LWE problem. LWE search-to-decision reduction shows that the hardness of the search-LWE problem can be reduced to the hardness of the decisional-LWE problem. The efficiency of the reduction can be regarded as the gap in difficulty between the problems. We initiate a study of quantum search-to-decision reduction for the LWE problem and propose a reduction that satisfies sample-preserving. In sample-preserving reduction, it preserves all parameters even the number of instances. Especially, our quantum reduction invokes the distinguisher only 2 times to solve the search-LWE problem, while classical reductions require a polynomial number of invocations. Furthermore, we give a way to amplify the success probability of the reduction algorithm. Our amplified reduction is incomparable to the classical reduction in terms of sample complexity and query complexity. Our reduction algorithm supports a wide class of error distributions and also provides a search-to-decision reduction for the learning parity with noise problem. In the process of constructing the search-to-decision reduction, we give a quantum Goldreich-Levin theorem over ℤq where q is a prime. In short, this theorem states that, if a hardcore predicate a・s (mod q) can be predicted with probability distinctly greater than (1/q) with respect to a uniformly random a ∈ ℤqn, then it is possible to determine s ∈ ℤqn.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Aug 15, 2024•0 citations
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 qqq-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 (TearlyT_{\text{early}}Tearly​) 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 404040-dimensional instance on the Coherent Ising Machine CPQC-550. This work establishes a new algorithm-hardware co-design paradigm for quantum-classical hybrid cryptanalysis.
The Learning-With-Errors (LWE) problem is a fundamental computational challenge with implications for post-quantum cryptography and computational learning theory. Here we propose a quantum-classical hybrid algorithm with Ising model to address LWE, transforming it into the Shortest Vector Problem and using variable qubits to encode lattice vectors into an Ising Hamiltonian. By identifying low-energy Hamiltonian levels, the solution is extracted, making the method suitable for noisy intermediate-scale quantum devices. The required number of qubits is less than m(m + 1), where m is the number of samples. Our heuristic algorithm’s time complexity depends on the specific quantum eigensolver used to find low-energy levels, and the performance when using the Quantum Approximate Optimization Algorithm is investigated. We validate the algorithm by solving a 2-dimensional LWE problem on a 5-qubit quantum device, demonstrating its potential for solving meaningful LWE instances on near-term quantum devices. Evaluating the security of post-quantum cryptography is critically important to ensure resilience against quantum attacks. In this paper, the authors study a complex computational task at the heart of post-quantum cryptography with a hybrid quantum-classical algorithm, heuristically finding some advantages.
Lattice-based post-quantum cryptography relies on the hardness of the Learning With Errors (LWE) and Module Learning With Errors (MLWE) problems. This work introduces a constructive framework for encoding small MLWE instances as Quadratic Unconstrained Binary Optimization (QUBO) models suitable for quantum annealing. The formulation jointly represents secret coefficients and explicit error variables within a unified binary optimization structure, enabling their simultaneous recovery from the ground-state solution. Beyond the encoding, we develop a stability analysis of the resulting optimization landscape under additive perturbations. We show that the admissible noise region forms a convex polytope defined by competing candidate secrets, and establish an equivalent characterization in terms of the QUBO energy gap between the optimal and second-best solutions. Numerical experiments on low-dimensional benchmark instances using exact simulation demonstrate correct recovery of both secret and discretized error vectors, and confirm consistency between geometric stability regions and energy-gap behavior. We further quantify the scaling of logical variables and embedding overhead with increasing MLWE dimensions to assess feasibility on quantum annealing architectures. The results establish a systematic connection between MLWE problems and quantum optimization while providing a framework for analyzing robustness properties of QUBO formulations. Although current quantum annealing hardware remains insufficient for cryptographically relevant parameters, the proposed methodology offers a structured basis for studying lattice-based problems in quantum optimization settings without implying a practical threat to standardized post-quantum schemes.
The rapid advancement of quantum computing poses an existential threat to classical public-key cryptographic systems, necessitating the transition to post-quantum cryptography (PQC). However, the deployment of lattice-based PQC schemes such as CRYSTALS-Kyber and CRYSTALS-Dilithium faces significant challenges including computational complexity, noise sensitivity, resource constraints, and security vulnerabilities. This research presents a comprehensive hybrid quantum-classical optimization framework for efficient and noise-tolerant post-quantum cryptographic systems. The framework addresses three primary objectives: (1) developing a unified hybrid quantum-classical optimization architecture that integrates variational quantum algorithms (VQE, QAOA) and QUBO/Ising formulations with classical PQC primitives based on the Learning With Errors (LWE) and Module-LWE problems; (2) designing noise-tolerant PQC protocols through multi-layer noise modeling that characterizes cryptographic, quantum hardware, and classical implementation noise; and (3) enabling resource-aware deployment on constrained platforms including embedded systems, IoT devices, and edge computing nodes. Experimental evaluation demonstrates that the QUBO formulation achieves coefficient ranges suitable for NISQ devices with 99.2% of coefficients within [-1, 1] after normalization. The adaptive partitioning algorithm achieves time-to-solution improvements of 42% for large problem instances compared to classical-only execution. The noise-aware optimization framework achieves decryption failure rate improvements ranging from 2^10.8 to 2^16.8, with combined noise tolerance success rates exceeding 94.56% under severe conditions. Side-channel countermeasures achieve 82.6% reduction in exploitable information leakage, with power leakage correlation reduced from 0.23 to 0.04. The unified Kyber-Dilithium architecture achieves 21% memory savings and 10-11% performance improvements. Reinforcement learning-based scheduling reduces latency by 37% and energy consumption by 39% compared to static scheduling. End-to-end deployment evaluation across smart home, industrial IoT, healthcare, and autonomous vehicle scenarios demonstrates that the hybrid PQC system meets latency and energy requirements while maintaining target security levels. This research provides a practical pathway toward secure communication in the quantum era, bridging the gap between current classical systems and future quantum-enabled solutions.
In the paper, we study lattice-based cryptographic problems, in particular Learning With Errors (LWE) and Short Integer Solution (SIS) lattice problems, which are considered to be known cryptographic primitives that are supposed to be secure against both classical and quantum attacks. We formulated the LWE and SIS problems as Mixed-Integer Programming (MIP) model and then converted them to Quadratic Unconstrained Binary Optimization (QUBO) problem, which can be solved by using a quantum annealer. Quantum annealing searches for the global minimum of an input objective function subjected to the given constraints to optimize the given model. We have estimated the q-bits required for the Quantum Processing Unit (QPU). Our results show that this approach can solve certain instances of the LWE and SIS problems efficiently.
The variational quantum algorithm (VQA) is a hybrid classical-quantum algorithm. It can actually run in an intermediate-scale quantum device where the number of available qubits is too limited to perform quantum error correction, so it is one of the most promising quantum algorithms in the noisy intermediate-scale quantum era. In this paper, two ideas for solving the learning with errors problem (LWE) using VQA are proposed. First, after reducing the LWE problem into the bounded distance decoding problem, the quantum approximation optimization algorithm (QAOA) is introduced to improve classical methods. Second, after the LWE problem is reduced into the unique shortest vector problem, the variational quantum eigensolver (VQE) is used to solve it, and the number of qubits required is calculated in detail. Small-scale experiments are carried out for the two LWE variational quantum algorithms, and the experiments show that VQA improves the quality of the classical solutions.
The learning with errors (LWE) problem is one of the fundamental problems in cryptography and it has many applications in post-quantum cryptography. There are two variants of the problem, the decisional-LWE problem, and the search-LWE problem. LWE search-to-decision reduction shows that the hardness of the search-LWE problem can be reduced to the hardness of the decisional-LWE problem. The efficiency of the reduction can be regarded as the gap in difficulty between the problems. We initiate a study of quantum search-to-decision reduction for the LWE problem and propose a reduction that satisfies sample-preserving. In sample-preserving reduction, it preserves all parameters even the number of instances. Especially, our quantum reduction invokes the distinguisher only 2 times to solve the search-LWE problem, while classical reductions require a polynomial number of invocations. Furthermore, we give a way to amplify the success probability of the reduction algorithm. Our amplified reduction is incomparable to the classical reduction in terms of sample complexity and query complexity. Our reduction algorithm supports a wide class of error distributions and also provides a search-to-decision reduction for the learning parity with noise problem. In the process of constructing the search-to-decision reduction, we give a quantum Goldreich-Levin theorem over ℤq where q is a prime. In short, this theorem states that, if a hardcore predicate a・s (mod q) can be predicted with probability distinctly greater than (1/q) with respect to a uniformly random a ∈ ℤqn, then it is possible to determine s ∈ ℤqn.