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

Eddie Farhi1, Xiao Yuan2
1 Google Quantum AI, Mountain View, CA 94043, USA
2 Center on Frontiers of Computing Studies, Peking University, Beijing 100871, China
Published: 2026-05-10 · FAIDS Vol. 1, No. 1 (2026)

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.

Keywords: quantum computing, combinatorial optimization, QAOA, NISQ devices, hybrid algorithms

1. Introduction

Combinatorial optimization underlies some of the most economically significant computational problems: logistics companies solve vehicle routing problems daily to minimize fuel costs, financial institutions optimize portfolios across thousands of assets, and telecom operators design network topologies to maximize coverage while minimizing infrastructure. While classical heuristics (simulated annealing, genetic algorithms, Gurobi MIP solver) provide good practical solutions, the exponential worst-case complexity motivates the search for quantum speedups.

2. HybridQOpt Framework

HybridQOpt operates in three phases: (1) graph partitioning via spectral clustering decomposes the original problem into subproblems with minimized inter-partition coupling, (2) each subproblem is solved using QAOA with p = 5 layers on a quantum processor, and (3) a classical belief propagation algorithm coordinates solutions across partitions. The key insight is that many real-world optimization problems exhibit community structure that makes them naturally decomposable.

3. Experimental Results

We benchmark HybridQOpt on three problem families of varying size. For problems up to 100 variables, we compare directly against full QAOA on the quantum processor. For larger instances (1,000-10,000 variables), we compare against Gurobi, simulated annealing, and a neural combinatorial solver.

0.90.90.911HybridQOptGurobi (1h)Sim. Annealing10050010002000500010000Problem Size (variables)Approximation Ratio
Figure 1. Approximation ratio vs. problem size for MaxCut instances on random 3-regular graphs

4. Conclusions

HybridQOpt bridges the gap between small-scale QAOA demonstrations and industry-relevant problem sizes, achieving competitive solution quality with demonstrated quantum speedup in the subroutine. As quantum hardware scales beyond 1,000 qubits with improved error rates, the framework can naturally absorb larger subproblems, suggesting a practical path to quantum advantage in combinatorial optimization.

References

  1. Farhi, E.; Goldstone, J.; Gutmann, S. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028, 2014.
  2. Harrigan, M. P.; Sung, K. J.; Neeley, M.; et al. Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor. Nature Physics 2021, 17, 332-336.
  3. Abbas, A.; Sutter, D.; Zoufal, C.; Lucchi, A.; Figalli, A.; Woerner, S. The Power of Quantum Neural Networks. Nature Computational Science 2021, 1, 403-409.
  4. Cerezo, M.; Arrasmith, A.; Babbush, R.; et al. Variational Quantum Algorithms. Nature Reviews Physics 2021, 3, 625-644.

This article is published under the Creative Commons Attribution 4.0 International License (CC BY 4.0).