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

• URL: http://arxiv.org/abs/2607.05973v1
• Date: Tue, 07 Jul 2026 08:05:45 GMT
• Title: QUBO Modeling of Module Learning With Errors: Stability and Scaling in Post-Quantum Cryptography
• Abstract summary: Post-quantum cryptography relies on the hardness of the Learning With Errors (LWE) and Module Learning With Errors (MLWE) problems.<n>This work introduces a constructive framework for encoding small MLWE instances as Quadratic Unconstrained Binary Optimization (QUBO) models.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Measurement-Efficient Variational Quantum Linear Solver for Carleman-Linearized Nonlinear Dynamics [1.4180331276028664]
  We show that Carleman linearization accurately approximates the weakly nonlinear Duffing equation.<n>We deploy VQLS with symmetry-grouped Hadamard Test evaluations under both global and local cost formulations.<n>Across block-banded test cases, each method achieves near-unity fidelity and vanishing relative residuals.
  arXiv  Detail & Related papers  (2026-05-14T19:45:27Z)
• Quantum Optimization in Loc(Q)ation Science: QUBO Formulations, Benchmark Problems, and a Computational Study [0.0]
  Quadratic Unconstrained Binary Optimization provides a unifying modeling framework for a broad class of $mathbfNP$-hard problems.<n>We develop QUBO formulations for several fundamental problems in location science, network design, and logistics.<n>These QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware.
  arXiv  Detail & Related papers  (2026-02-11T15:39:26Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• A Quantum Model for Constrained Markowitz Modern Portfolio Using Slack Variables to Process Mixed-Binary Optimization under QAOA [0.0]
  A quantum model for Markowitz portfolio optimization is presented.<n>The method maps each slack variable to a dedicated ancilla qubit, transforming the problem into a Quadratic Unconstrained Binary Optimization (QUBO) formulation.<n>A fundamental quantum limit on the simultaneous precision of portfolio risk and return is also posited.
  arXiv  Detail & Related papers  (2025-12-29T20:40:16Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Quantum Alternating Direction Method of Multipliers for Semidefinite Programming [9.11785675254736]
  We present a quantum alternating direction method of multipliers (QADMM) for SDPs.<n>An inexact ADMM framework is developed, which tolerates errors in the iterate approximations arising from block-encoding approximations and quantum measurement.<n>We prove that the scheme converges to an $$-optimal solution of the SDP problem under the strong duality assumption.
  arXiv  Detail & Related papers  (2025-10-11T06:44:33Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Hybrid quantum-classical algorithm for near-optimal planning in POMDPs [39.682133213072554]
  Reinforcement learning (RL) provides a principled framework for decision-making in partially observable environments.<n>Recent advances demonstrate that inference on sparse Bayesian networks can be accelerated using quantum rejection sampling combined with amplitude amplification.<n>We introduce Quantum Bayesian Reinforcement Learning (QBRL), a hybrid quantum-classical look-ahead algorithm for model-based RL in partially observable environments.
  arXiv  Detail & Related papers  (2025-07-24T17:42:30Z)
• Solving wave equation problems on D-Wave quantum annealers [44.99833362998488]
  We solve the one-dimensional Helmholtz equation in several scenarios using the quantum annealer provided by the D-Wave systems within a pseudospectral scheme.<n>We assess the performance of different strategies of encoding based on algebraic arguments and the adiabatic condition.
  arXiv  Detail & Related papers  (2025-07-18T08:06:43Z)
• Quantum-Classical Hybrid Quantized Neural Network [8.382617481718643]
  We present a novel Quadratic Binary Optimization (QBO) model for quantized neural network training, enabling the use of arbitrary activation and loss functions.<n>We employ the Quantum Gradient Conditional Descent (QCGD) algorithm, which leverages quantum computing to directly solve the QCBO problem.
  arXiv  Detail & Related papers  (2025-06-23T02:12:36Z)
• Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
  We propose an iterative-based algorithm that jointly updates the decision and the IS distribution without requiring time-scale separation between the two.<n>Our method achieves the lowest possible variable variance and guarantees global convergence under convexity of the objective and mild assumptions on the IS distribution family.
  arXiv  Detail & Related papers  (2025-04-04T16:10:18Z)
• Revisiting Gaussian genuine entanglement witnesses with modern software [0.0]
  Continuous-variable Gaussian entanglement is an attractive concept in quantum information theory.<n>We present several approaches to reconstruct the most probable physical covariance matrix from a measured non-physical one.<n>We derive an explicit analytical expression for the symplectic trace of a positive definite matrix, which can serve as a simple witness of an entanglement witness.
  arXiv  Detail & Related papers  (2024-12-12T23:33:52Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.