Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.
Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.
This paper addressed the computational challenges of solving large-scale fuzzy 0-1 Integer Linear Programming (ILP) problems by proposing a Fuzzy-Hybrid Quantum-Classical Optimization Algorithm (F-HQCOA).The novel approach employed α-cut based transformations to convert fuzzy ILP models into a family of crisp Quadratic Unconstrained Binary Optimization (QUBO) problems, which were then solved using hybrid quantumclassical techniques.Unlike multi-objective formulations, the proposed framework performed a parametric analysis over α-levels to generate a spectrum of solutions that reflected trade-offs between objective optimality and feasibility satisfaction under uncertainty.The degree of satisfaction (µ) was adopted as an evaluation metric to assess solution quality rather than as an independent optimization objective.The method was evaluated on fuzzy Multi-Dimensional Knapsack and Set Covering problems.Results showed that the proposed approach could efficiently handle larger instances and provided a diverse set of solutions across α-levels.While quantum-assisted methods demonstrated reduced Time-to-Solution (TTS) in certain settings, comparisons were presented with careful consideration of differences in computational paradigms.The proposed framework offers a practical decision-support tool for optimization under uncertainty and establishes a foundation for future extensions toward true multi-objective fuzzy quantum optimization.
Widely used quantum optimization algorithms such as quantum annealing and quantum approximate optimization algorithm (QAOA) for quadratically unconstrained binary optimization (QUBO) problems cannot systematically and efficiently handle constraints and mixed discrete and continuous decision variables. To address this, we present a novel hybrid classicalquantum approach which combines classical alternating direction method of multipliers (ADMM) with QAOA. Compared to conventional penalty-based method, this approach avoids quantization of continuous variables, eliminates the need for additional qubits to capture constraints on a quantum device and leads to reduced QAOA circuit depth suitable for near term implementation. We illustrate the efficacy of our approach on several constrained mixed integer optimization problems.
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.
Abstract As interest in quantum and related optimization paradigms continues to grow, fairly and systematically comparing their performance across practical problem settings remains challenging. This challenge arises because these approaches often target different problem classes, use different mathematical representations, and are affected differently by modeling choices. As a result, observed performance depends not only on the solver itself, but also on how a problem is formulated, reformulated, and translated into a solver-specific input language. This work presents a publicly available and extensible benchmarking framework that unifies advances in quantum, quantum-hybrid, quantum-inspired, and classical optimization by enabling consistent comparison across use cases, solvers, and models. We address the diversity of solver “languages”—from mixed-integer programming (MIP) formulations for branch-and-bound methods over quadratic unconstrained binary optimization (QUBO) models for quantum annealers to constrained quadratic models (CQM) for hybrid approaches — as well as the influence of modeling choices, such as binary encodings and penalty formulations, on both performance and solution fidelity. By supporting systematic variation across the three dimensions of use case, solver, and model, the framework reveals trade-offs that single-dimension benchmarks overlook, clarifies when native formulations are preferable, and enables rigorous evaluation of practical combinatorial optimization problems. The two case studies, vehicle routing and maximum cut, illustrate this principle: their contrasting outcomes show that the effectiveness of a solver depends strongly on how well the chosen model representation matches the solver backend and the use case.
As quantum computing advances, quantum approximate optimization algorithms (QAOA) have shown promise in addressing combinatorial optimization problems. However, the limitations of Noisy Intermediate Scale Quantum (NISQ) devices hinder the scalability of QAOA for large-scale optimization tasks. To overcome these challenges, we propose Backbone-Driven QAOA, a hybrid framework that leverages adaptive Tabu search for classical preprocessing to decompose large-scale quadratic unconstrained binary (QUBO) problems into NISQ-compatible subproblems. In our approach, adaptive Tabu search dynamically identifies and fixes backbone variables to construct reduced-dimensional subspaces that preserve the critical optimization landscape. These quantum-tractable subproblems are then solved via QAOA, with the resulting solutions iteratively refining the backbone selection in a closed-loop quantum-classical cycle. Experimental results demonstrate that our approach not only competes with, and in some cases surpasses, traditional classical algorithms but also performs comparably with recently proposed hybrid classical-quantum algorithms. Our proposed framework effectively orchestrates the allocation of quantum and classical resources, thereby enabling the solution of large-scale combinatorial optimization problems on current NISQ hardware.
The rapidly increasing number of heterogeneous data ecosystems, such as structured databases, semi-structured data lakes, real-time streams, distributed knowledge graphs, has further complicated the issue of query planning and optimization in modern information systems extensively. The optimization of queries is essentially an NP-hard combinatorial problem especially when based on multi-join queries, distributed execution plan, dynamic cost model, and uncertainty in the data access patterns. Even decades of concept and engineering advances, classical database optimizers are rapidly becoming unable to offer a globally optimal execution plan when faced with high-dimensional data, high data volatility, with a very tight latency constraint. Good news Recent breakthroughs in quantum computing propose promising computational paradigms that can be used to solve combinatorial optimization problems via quantum parallelism, superposition, and entanglement. Nevertheless, even the near-term quantum hardware is limited in the number of available qubits, noise, and decoherence, making it impractical to achieve fully quantum database systems in any perceived future. This is also the reason why quantum-classical hybrid algorithms are being developed: designed to add quantum optimization subroutines to classical database architectures is guaranteed without breaking their compatibility with existing execution engines. The following paper presents a framework of scalable quantum-classical hybrid computing of complex query planning in heterogeneous data ecosystems. The framework breaks down query optimization into classical and quantum-amenable optimization, which allows NP-hard subproblems, such as join ordering, operator placement, and cost minimization, to be transformed into quantum optimization models such as Quadratic Unconstrained Binary Optimization (QUBO) and Ising Hamiltonians. Classical elements handle query parsing, semantic analysis, constraint verification, and orchestration, whereas quantum processors are called selectively to solve combinatorial decision-making tasks. The suggested architecture will consist of a layered execution, hybrid execution, cost-model encoding approach, and adaptive fallback mechanisms to make them robust to quantum hardware variability. This has been experimentally tested with simulated quantum annealing and variational quantum algorithms that exhibit a quantifiable improvement in the quality and scalability of optimization and heuristics based on entirely classical algorithms, especially in high-dimensional query plans. The findings confirm the practicability of quantum query optimization and put down a feasible route to implement quantum algorithms in the serving machine of the next-generation data management systems.