MillionQAOA: A Dividable QAOA Framework for Solving Million-Vertex-Scale Max-Cut Problems

Abstract

Hybrid quantum-classical optimization has made the Quantum Approximate Optimization Algorithm (QAOA) a leading candidate for combinatorial optimization tasks, and Max-Cut stands out among them for its broad practical footprint and its clean reduction to QUBO and Ising form. Prior divide-and-conquer adaptations push QAOA toward larger inputs, yet they stay capped at tens of thousands of vertices and never engage modern GPU cluster hardware, leaving million-scale instances out of reach. This work closes that gap with MillionQAOA, a GPU-accelerated divide-and-conquer framework capable of solving Max-Cut instances of up to one million vertices on multi-node H100 GPU clusters. The framework is organized as a four-phase, topology-aware pipeline: parallel graph synthesis, solver-shard formation, concurrent GPU-parallel circuit solving, and candidate consolidation through boundary binning paired with a layer-wise frontier expansion. On a testbed of 8 DGX-H100 nodes (64 GPUs in total), MillionQAOA scales near-linearly from 62.5K through 1M vertices, matches classical greedy solvers in cut quality at the 50K-vertex mark (within 0.2% higher), and cuts execution time by up to 13.6 × , making it a deployable route to million-vertex Max-Cut at scale.