Demonstrating quantum heuristics that outperform strong classical solvers on large-scale optimization remains an open challenge. Here we introduce Regularized Warm-Started QAOA (RWS-QAOA), which initializes qubits by minimizing expected energy with a regularizer that penalizes near-bitstring states, preventing QAOA from stalling. We further propose a protocol that yields fixed, instance-independent parameters, enabling RWS-QAOA to operate as a non-variational algorithm in which the quantum circuit parameters are fixed and only a classical warm starting step is instance-dependent. We evaluate RWS-QAOA on the Max-Cut problem for random regular graphs, where this protocol yields a constant-depth quantum circuit, across three complementary settings. First, on Quantinuum's trapped-ion processor, RWS-QAOA outperforms the classical algorithms with the best provable guarantees for Max-Cut on
3-regular graphs, namely Goemans-Williamson and Halperin-Livnat-Zwick, on
96-node instances. Second, tensor-network simulations on graphs with up to
N=10,000 nodes show that depth-
6 RWS-QAOA, achieving an average cut fraction of
0.9167, surpasses the best classical heuristics under matched restrictions (no local-search post-processing and no iterative refinement). Third, we remove these restrictions and benchmark against the strongest unrestricted classical heuristics, including an optimized parallel Burer-Monteiro solver that improves upon the MQLib implementation. Even against this stronger baseline, we project that surface-code RWS-QAOA reaches a quantum-classical runtime crossover below
0.2 seconds on
3,000-node graphs with fewer than
1.3 million physical qubits. Our results show that constant-depth quantum circuits combined with a classical warm start have a credible potential to surpass classical solvers on the Max-Cut problem when executed on future quantum computers.
We develop new approximate compilation schemes that significantly reduce the expense of compiling the Quantum Approximate Optimization Algorithm (QAOA) for solving the Max-Cut problem. Our main focus is on compilation with trapped-ion simulators using Pauli- X operations and all-to-all Ising Hamiltonian H Ising evolution generated by Molmer-Sorensen or optical dipole force interactions, though some of our results also apply to standard gate-based compilations. Our results are based on principles of graph sparsification and decomposition; the former reduces the number of edges in a graph while maintaining its cut structure, while the latter breaks a weighted graph into a small number of unweighted graphs. Though these techniques have been used as heuristics in various hybrid quantum algorithms, there have been no guarantees on their performance, to the best of our knowledge. This work provides the first provable guarantees using sparsification and decomposition to improve quantum noise resilience and reduce quantum circuit complexity. For quantum hardware that uses edge-by-edge QAOA compilations, sparsification leads to a direct reduction in circuit complexity. For trapped-ion quantum simulators implementing all-to-all H I s i n g pulses, we show that for a ( 1 − ϵ ) factor loss in the Max-Cut approximation ( ϵ > 0 ) , our compilations improve the (worst-case) number of H I s i n g pulses from O ( n 2 ) to O ( n log ( n / ϵ ) ) and the (worst-case) number of Pauli- X bit flips from O ( n 2 ) to O ( n log ( n / ϵ ) ϵ 2 ) for n -node graphs. This is an asymptotic improvement for any constant ϵ > 0 . We demonstrate that significant improvements to the approximation ratio are obtained using decomposition in simulated trapped-ion experiments with dephasing noise. We further present a generic argument showing that sparsification results in an exponentially improved circuit fidelity lower bound in digital computing schemes based on one- and two-qubit gates, which are relevant to a wide variety of hardwares such as superconducting qubits and certain neutral atom or trapped ion setups, and more sophisticated noise models. We anticipate these approximate compilation techniques will be useful tools in a variety of future quantum computing experiments.
The p -stage Quantum Approximate Optimization Algorithm (QAOA p ) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond p=1 . We analyze QAOA 2 for the maximum cut problem (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any D -regular graph of girth >5 (i.e. without triangles, squares, or pentagons).We show that for all degrees D≥2 and every D -regular graph G of girth >5 , QAOA 2 has a larger expected cut fraction than QAOA 1 on G . However, we also show that there exists a 2 -local randomized classical algorithm A such that A has a larger expected cut fraction than QAOA 2 on all G . This supports our conjecture that for every constant p , there exists a local classical MAX-CUT algorithm that performs as well as QAOA p on all graphs.
Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising solution for combinatorial optimization problems using a hybrid quantum-classical framework. Among combinatorial optimization problems, the Maximum Cut (Max-Cut) problem is particularly important due to its broad applicability in various domains. While QAOA-based Max-Cut solvers have been developed, they primarily favor solution accuracy over execution efficiency, which significantly limits their practicality for large-scale problems. To address the limitation, we propose ParaQAOA, a parallel divide-and-conquer QAOA framework that leverages parallel computing hardware to efficiently solve large Max-Cut problems. ParaQAOA significantly reduces runtime by partitioning large problems into subproblems and solving them in parallel while preserving solution quality. This design not only scales to graphs with tens of thousands of vertices but also provides tunable control over accuracy-efficiency trade-offs, making ParaQAOA adaptable to diverse performance requirements. Experimental results demonstrate that ParaQAOA achieves up to 1,600x speedup over state-of-the-art methods on Max-Cut problems with 400 vertices while maintaining solution accuracy within 2% of the best-known solutions. Furthermore, ParaQAOA solves a 16,000-vertex instance in 19 minutes, compared to over 13.6 days required by the best-known approach. These findings establish ParaQAOA as a practical and scalable framework for large-scale Max-Cut problems under stringent time constraints.