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

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.