Quantum-Classical Hybrid Variational Algorithms for Large-Scale Combinatorial Optimization on NISQ Devices

Abstract

Combinatorial optimization problems — vehicle routing, portfolio optimization, network design — are ubiquitous in industry yet NP-hard in general. Quantum approximate optimization algorithms (QAOA) promise quantum advantage but are limited to small problem sizes on current noisy intermediate-scale quantum (NISQ) devices. We present HybridQOpt, a divide-and-conquer framework that decomposes large problems (up to 10,000 variables) into quantum-solvable subproblems (50-100 qubits) while maintaining solution quality through a classical message-passing coordination layer. Benchmarked on MaxCut, Traveling Salesman, and portfolio optimization, HybridQOpt achieves approximation ratios within 2-5% of the best classical solvers while demonstrating 3.2× speedup on a 127-qubit IBM Eagle processor for the quantum subroutine.