Quantum-Classical Hybrid Algorithms for Combinatorial Optimization: Benchmarking and Analysis

We conduct a systematic benchmarking study of quantum-classical hybrid algorithms against classical counterparts on combinatorial optimization benchmarks. We evaluate QAOA, VQE, QSVM, and Quantum Annealing across MAX-CUT, graph coloring, portfolio optimization, and vehicle routing problems, comparing against classical solvers including Gurobi, simulated annealing, and genetic algorithms. On near-term noisy intermediate-scale quantum (NISQ) hardware (IBM Quantum, IonQ), we observe quantum advantage emerging at n≥50 qubits for MAX-CUT problems, with 2.3× speedup. However, hardware noise significantly degrades performance for circuit depths >20, motivating our noise-aware compilation approach that extends practical quantum advantage regimes.