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.
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 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
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.
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.
This paper presents a hybrid computational framework that integrates classical and quantum optimization techniques to improve the efficiency of Huffman encoding and string-matching algorithms.On the classical side, performance is enhanced through SIMD (Single Instruction, Multiple Data) parallelism, bitlevel operations, and cache-aware data structures.On the quantum side, we investigate Grover-based string search using amplitude amplification, approximate reflection operators, and entropy-aware circuit design tailored for Noisy Intermediate-Scale Quantum (NISQ) constraints.The primary contribution of this work is a hybrid visualization framework that synchronizes classical algorithmic flowcharts with real-time quantum circuit representations, enabling unified debugging, execution tracing, and performance analysis across both domains.Experimental evaluations conducted using optimized classical implementations and quantum simulators with noise models demonstrate up to a 65% reduction in runtime for quantum-enhanced string search and over a 30% speedup in classical SIMD-accelerated Huffman encoding.The proposed quantum optimizations maintain an accuracy above 97% while reducing circuit depth, indicating practical feasibility under current NISQ limitations.By improving both algorithmic performance and developer interpretability, this hybrid framework serves as an effective tool for algorithm design, analysis, and education.The results highlight the potential of tightly coupled classical-quantum workflows and motivate further research into scalable, NISQ-compatible hybrid algorithm development.
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 The arrival of noisy intermediate-scale quantum (NISQ) devices defines an era in which quantum utility is fundamentally constrained by finite coherence times, limited qubit counts, gate infidelities, restricted connectivity, and measurement noise. Within this regime, hybrid quantum-classical frameworks have emerged as the dominant operational paradigm, particularly for quantum machine learning (QML). This review identifies a fundamental trade-off between expressivity, trainability, and noise resilience that governs the performance and scalability of NISQ-era QML systems. To contextualize these challenges, we introduce the resource-constrained iterative routing framework, a hardware-aware conceptual architecture that integrates topology-aware classical compression and distributed quantum orchestration to maintain circuit depths within device-dependent limits while routing representations toward symmetry-constrained Hilbert subspaces to mitigate noise-induced barren plateaus. Furthermore, we shift the discussion of quantum advantage away from asymptotic fault-tolerant complexity toward the notion of operational NISQ advantage based on finite-resource scaling, trainability preservation, and sampling complexity. We evaluate the practical resource efficiency of variational quantum algorithms, quantum kernel methods, and quantum neural networks across superconducting, trapped-ion, neutral-atom, and photonic platforms. The review also examines reproducibility challenges, emphasizing benchmarking against optimized classical baselines, and discusses strategies for managing the sampling overhead of error mitigation alongside distributed execution and quantum circuit compilation. Ultimately, NISQ in Practice positions hybrid QML as a physically constrained computational paradigm while outlining a pathway from contemporary noisy workflows toward early fault-tolerant quantum architectures.