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.
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 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 (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 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.
Quantum Optimization (QO) is emerging as a promising approach to tackle hard combinatorial optimization problems by leveraging the unique computational properties of quantum hardware. In recent years, QO has gained traction in Machine Learning (ML), where problems such as clustering and vector quantization can be naturally expressed as Quadratic Unconstrained Binary Optimization (QUBO) problems. These ML applications often involve complex, high-dimensional data, which directly influences both the structure and scale of the resulting QUBO formulations. However, current quantum devices fall under the category of Noisy Intermediate-Scale Quantum (NISQ) hardware, which imposes significant limitations on qubit counts and small error rates. This dissertation investigates the impact of data complexity and data scale—as encountered in ML settings—on the effectiveness and feasibility of QO on NISQ devices. We propose novel, hardware-aware methods to overcome these challenges. The first part of this thesis focuses on the effect of data complexity for QO. We analyze how problem structure—particularly when QUBO formulations are derived from ML tasks—affects quantum solvability. We identify the spectral gap as a key factor in the success of adiabatic quantum algorithms and provide a theoretical and empirical analysis linking data-induced complexity to optimization performance.To address noise sensitivity and limited precision, we introduce a preprocessing framework based on a principled Branch-and-Bound algorithm that reduces dynamic range while preserving global optima. This improves robustness on both quantum annealers and classical solvers. In the second part, the thesis addresses challenges introduced by data scale. First, we propose a recursive Divide-and-Conquer strategy that breaks down large QUBO problems into tractable subproblems, demonstrated through an application to Bundle Adjustment in 3D scene reconstruction. Second, we introduce a variable and constraint generation method inspired by column generation for Integer Linear Programming, enabling dynamic QUBO size growth. This technique is successfully applied to Multi-Agent Pathfinding, where it scales well on NISQ devices while maintaining compatibility with classical solvers. Finally, we explore QUBO reformulations that reduce problem size through compact encodings and cyclic expansion, enabling the use of quantum hardware for tasks such as FPGA placement in chip design. Across all contributions, the developed algorithms are evaluated both theoretically and empirically, with experiments conducted on real quantum and quantum-inspired hardware. These methods significantly improve solution quality, scalability, and hardware compatibility, paving the way for more effective use of QO in practical settings. While tailored for NISQ era constraints, the results remain relevant for fault-tolerant quantum computing, offering insights into the long-term viability of QO across hardware generations.
Alignment-based conformance checking is a central task in process mining, but computing optimal alignments is computationally hard. This paper studies whether the alignment problem can be expressed directly as a Quadratic Unconstrained Binary Optimization problem and explored with quantum annealing. We present a direct QUBO formulation for optimal alignments on safe Petri nets, with a proof-of-concept implementation supporting exact solving, simulated annealing, and a D-Wave Advantage2 quantum processing unit. The study is intentionally preliminary: rather than claiming a practical quantum advantage, we test whether the formulation is semantically correct and where current hardware helps or fails. On small representative benchmarks, the QUBO recovers correct optimal alignments, including concurrency, loops, silent transitions, and duplicate labels. On loop-heavy instances, the quantum annealer can outperform simulated annealing on success probability. Scalability, however, is strongly limited by hardware connectivity and embedding overhead. Overall, direct QUBO-based alignment finding is feasible in principle, but still far from practical large-scale use.
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.
The increasing complexity of computational problems in various fields entails the development of efficient methods to solve them. Thus, the emerging technology of quantum computers comes with algorithms, such as quantum annealing, that could solve optimization problems exponentially faster. In particular, to solve the 3SAT problem on quantum annealers, it must be transformed into an instance of Quadratic Unconstrained Binary Optimization (QUBO). Given that the choice of 3SAT-to-QUBO transformation affects the solution quality on quantum annealing, an algorithmic method for creating numerous 3SAT-to-QUBO transformations has recently been proposed, aiming to investigate more deeply such effect. This represents a challenge when deciding which is the best performing 3SAT-to-QUBO transformation that should be used when solving a 3SAT instance on quantum annealing. To overcome this issue, this work investigates the impact of different 3SAT-to-QUBO transformations on the solution quality of simulated annealing, as a classical analogue to quantum annealing. We demonstrate that different QUBO encodings of the same 3SAT instance can lead to different outcomes in terms of energy and clause satisfaction. We also reveal some correlations between 3SAT features, QUBO structural properties, and solution quality. These findings underscore the importance of the choice of 3SAT-to-QUBO transformation in simulated annealing, and provide a foundation for the future development of machine learning models for guiding encoding choices in both classical and quantum environments.
Quantum error-correcting codes (QECCs) are at the heart of fault-tolerant quantum computing. As the size of quantum platforms is expected to grow, one of the open questions is to design new optimal codes of ever-increasing size. A related challenge is to certify the quality of a given code by evaluating its minimum distance, a quantity characterizing code's capacity to preserve quantum information. This problem is known to be NP-hard. Here we propose to harness the power of contemporary quantum platforms to address this question, and in this way help design quantum platforms of the future. Namely, we introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem and leveraging established QUBO algorithms and heuristics as well as quantum annealing (QA) to address the latter. The reformulation as a QUBO introduces only a logarithmic multiplicative overhead in the required number of variables. We demonstrate the formulation using the D-Wave Advantage 4.1 quantum annealer and the hybrid quantum-classical algorithm Qbsolv, and benchmark the resulting QUBO-based implementations against specialized classical distance-finding methods. The QA- and SA-assisted implementations show broadly comparable performance, while the classical comparison clarifies the relative strengths of heuristic optimization and exact distance certification. Our results establish a solver-independent QUBO formulation with only a logarithmic multiplicative overhead in the number of variables and characterize connectivity and minor embedding as central limitations of its present implementation on quantum-annealing hardware.