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.
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.
Scalable combinatorial optimization under resource-constrained quantum hardware remains a fundamental challenge in the Noisy Intermediate-Scale Quantum (NISQ) era, due to the mismatch between exponentially growing solution spaces and limited quantum computational capacity. In this work, we propose a NISQ-aware hybrid quantum-classical optimization framework that reformulates large-scale combinatorial optimization as a resource-bounded distribution evolution process. Instead of directly optimizing individual solutions, the proposed framework operates on a probabilistic representation of the solution space, enabling efficient exploration under hardware constraints. Specifically, large problem instances are decomposed into qubit-compatible subproblems via clustering-based decomposition, ensuring resource-bounded optimization. Within each subproblem, a quantum genetic algorithm evolves the solution distribution, while periodically embedded amplitude amplification acts as a controlled quantum enhancement mechanism that accelerates convergence without increasing circuit depth. A classical refinement stage ensures global solution consistency. Extensive experiments on benchmark and synthetic datasets demonstrate that the proposed framework consistently outperforms classical and quantum-inspired baselines, with performance gains that become more pronounced as problem scale increases. This scale-dependent behavior indicates that scalability is achieved through structured decomposition rather than increased quantum complexity. Noise simulations further confirm robustness under realistic NISQ conditions, and ablation studies validate that both quantum evolutionary search and amplitude amplification contribute significantly to performance improvements.
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.
Quantum computing promises computational advantages for solving complex optimization problems; however, current Noisy Intermediate-Scale Quantum (NISQ) devices suffer from limited qubit counts, short coherence times, and high error rates. Fully fault-tolerant quantum algorithms remain impractical in the near term, necessitating hybrid approaches that integrate classical and quantum computation. This paper proposes a Hybrid Quantum–Classical Machine Learning Framework (HQC-MLF) for large-scale combinatorial and continuous optimization tasks. The framework leverages parameterized quantum circuits (PQCs) embedded within classical optimization loops, enabling efficient search in high-dimensional spaces while mitigating hardware constraints. We introduce adaptive ansatz selection, classical preconditioning, error mitigation strategies, and resource-aware scheduling to enhance scalability. Experimental evaluations on logistics routing, portfolio optimization, and energy load balancing demonstrate improved convergence speed and solution quality compared to purely classical baselines under realistic NISQ simulations. The proposed architecture provides a practical pathway toward near-term quantum advantage in real-world optimization problems
Large-scale combinatorial optimization is a challenge for near-term quantum computing because dense Quadratic Unconstrained Binary Optimization (QUBO) formulations yield interaction graphs that exceed the limits of NISQ processors. This work introduces Hybrid Quantum Neighborhood Selection (HQNS), a hybrid framework mitigating this via stochastic frontier decomposition. Instead of encoding all N variables into a monolithic circuit, HQNS selects a compact frontier of F << N active variables per stage, freezing the rest into reduced QUBO coefficients. A multi-stage crawling procedure rotates these frontiers, letting local quantum subproblems refine a global solution. We evaluate HQNS on the Maximum Diversity Subset Selection Problem (MDSSP) across six scales, N up to 1000. Circuit burden is reduced from the dense QAOA requirement of O(N^2) two-qubit terms per layer to O(F^2) per stage, with total complexity governed by the number of stages and classical overhead. Benchmarks show that HQNS achieves competitive solution quality relative to parallel simulated annealing (SA) while maintaining bounded circuit width and stable QPU time. In the N=1000 benchmark over ten executions, HQNS preserves 99.9908% of the mean diversity score of an 11-restart parallel SA baseline, while reducing wall-clock time by 65.03%, peak CPU usage by 55.97%, and peak memory by 35.21%. Ablation shows performance depends on frontier size, warm-starts, CVaR filtering, and stochastic rotation. These results demonstrate that structured frontier decomposition makes variational optimization executable for dense QUBO instances unsuitable for direct QAOA on present hardware.
Solving optimization problems is critical across many research domains, but the high dimensionality of parameter spaces often poses significant challenges. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for accelerating optimization in the Noisy Intermediate-Scale Quantum (NISQ) era by leveraging both classical and quantum computational resources. However, its performance can vary depending on the underlying quantum hardware architecture. In this work, we evaluate the performance of QAOA on different quantum hardware platforms, specifically, superconducting transmon qubits and trapped-ion qubits, targetting real-world optimization problems formulated as fully connected Quadratic Unconstrained Binary Optimization (QUBO) instances. We evaluate both the solution quality and time-to-solution using dense QUBO matrices. Furthermore, we show that large-scale problems, such as a 100-bit QUBO instance, can be effectively tackled by integrating quantum computing with high-performance computing (HPC) resources. This study provides practical insights into the strengths and limitations of different qubit technologies and advances the application of quantum computing in solving real-world optimization problems.
The Quantum Approximate Optimization Algorithm (QAOA) is a well-known hybrid quantum-classical algorithm for combinatorial optimization problems. Improving QAOA involves enhancing its approximation ratio while addressing practical constraints of Noisy Intermediate Scale Quantum (NISQ) devices, such as minimizing the number of two-qubit gates and reducing circuit depth. Although existing research has optimized designs for phase and mixer operators to improve performance, challenges remain, particularly concerning the excessive use of two-qubit gates in the construction of phase operators. To address these issues, we introduce a Dynamic Adaptive Phase Operator (DAPO) algorithm, which dynamically constructs phase operators based on the output of previous layers and neighborhood search approach, optimizing the problem Hamiltonian more efficiently. By using solutions generated by QAOA itself to simplify the problem Hamiltonian at each layer, the algorithm captures the problem's structural properties more effectively, progressively steering the solution closer to the optimal target. Experimental results on MaxCut and NAE3SAT problems show that DAPO achieves higher approximation ratios and significantly reduces two-qubit RZZ gates, especially in dense graphs. Compared to vanilla QAOA, DAPO uses only 66% of RZZ gates at the same depth while delivering better results, demonstrating its potential for efficient combinatorial optimization in the NISQ era.