Warm-Starting MaxCut Relaxation via Low-Depth Quantum Approximate Optimization Algorithm

AI summary

Overview

Research area: quantum optimization, specifically hybrid quantum-classical algorithms for combinatorial optimization (MaxCut), combining the Quantum Approximate Optimization Algorithm (QAOA) with the classical Burer–Monteiro rank-two relaxation. Technical level: Intermediate (readers should know basic QAOA structure and semidefinite relaxation concepts). Scope: this paper proposes and numerically tests a way to use depth-one QAOA correlation data to initialize a leading classical MaxCut heuristic, and compares this warm start against random multi-start initialization on Erdős–Rényi and Sherrington–Kirkpatrick instances at n = 500 and n = 1000.

What This Paper Is About

State-of-the-art classical MaxCut solvers, especially the rank-two Burer–Monteiro (BM) relaxation, are strong enough that directly outperforming them with low-depth quantum circuits is very difficult. The authors ask a narrower question: can shallow quantum circuits supply useful structural information that makes a strong classical solver converge faster? Their answer is a warm-start procedure that converts depth-one QAOA pairwise correlators into initial angles for BM, which they benchmark against standard random multi-start initialization.

Key Contributions

1. A warm-start strategy for the rank-two Burer–Monteiro heuristic for weighted MaxCut that uses QAOA pairwise cut probabilities to propose initial points for the solver.
2. A concrete construction to realize this: correlators ⟨Z_i Z_j⟩ are mapped through a Goemans–Williamson-inspired trigonometric function into a matrix Q̃, the two largest positive eigenvectors of Q̃ give an initial angle ansatz, and a nonlinear least-squares problem (solved with the Armijo gradient line search as implemented in MQLib) refines those angles so that the rank-two correlation structure is as close as possible to the QAOA-derived Q̃.
3. Numerical evidence that this quantum-informed initialization, using only depth-one QAOA, gives BM a substantial head start at small iteration budgets on ER-10 graphs and SK spin glasses at n = 500 and n = 1000.
4. An analysis of the exploitation/exploration tradeoff: with enough iterations a random multi-start baseline often catches up and slightly outperforms the warm start, and this effect is visibly weaker at n = 1000 than at n = 500. The paper also introduces a RandomLocal control (random fixed initial point with restarts back to it) to separate the benefit of the QAOA information from the benefit of simply not re-randomizing.

Main Findings

• Faster early convergence: warm-started BM reaches low energies and high win rates at small iteration budgets, well ahead of the Random MultiStart baseline, on ER-10 at both n = 500 and n = 1000.
• Crossover points on ER-10: the MultiStart baseline crosses the warm-start performance at about 159 iterations for WS-AllPairs and 182 iterations for WS-GraphOnly at n = 500, and at 674 iterations for WS-AllPairs and 925 iterations for WS-GraphOnly at n = 1000.
• Win rates at the maximal budget: at the maximum budget of 1000 iterations, the warm-start win rate reaches around 50% for n = 500 and ends closer to 60% for n = 1000.
• GraphOnly versus AllPairs: on ER-10, WS-AllPairs starts in a better region initially, but WS-GraphOnly eventually catches up and ends up the better strategy at higher iteration budgets.
• Weaker advantage on SK: for the fully connected Sherrington–Kirkpatrick model the warm start performs generally worse than on ER-10, with crossover at roughly 100 iterations for n = 500 and roughly 600 iterations for n = 1000.
• Better relative behavior at larger size: for both problem classes the warm start appears generally more effective at n = 1000 than at n = 500, which the authors flag as a potentially favorable scaling signal to be investigated in future work.
• Ties differ by size: there is a large number of ties at n = 500 but none or almost none at n = 1000, meaning that at the larger size, when the warm start wins, it achieves a genuinely better energy than the baseline.
• Control result: the RandomLocal control indicates the improvement is attributable to the information in the QAOA-derived seeds rather than merely to keeping a fixed initial point.

Methodology in Plain English

The authors target weighted MaxCut, where the goal is to split graph vertices into two groups so that the total weight of edges crossing the split is as large as possible. Classical practice has a strong heuristic for this: place every vertex on a circle, adjust the angles so that the cost function of cosines of angle differences is minimized, then sweep a diameter around the circle and take the best binary cut; the solver is restarted repeatedly from perturbed copies of the current best cut.

The quantum ingredient is depth-one QAOA. Rather than sampling from the quantum state, the authors use known closed-form expressions for the two-point correlators ⟨Z_i Z_j⟩ of depth-one QAOA, which can be evaluated efficiently in classical simulation. Each correlator gives the marginal probability that edge (i, j) is cut, p_ij = (1 − ⟨Z_i Z_j⟩)/2. Drawing on the Goemans–Williamson relation between cut probability and angle, they build the matrix Q̃_ij = cos(π p_ij) = sin((π/2)⟨Z_i Z_j⟩), then search for angles whose pairwise cosines match Q̃ by nonlinear least squares. That minimization is initialized from the two largest positive eigenvectors of Q̃, and the result supplies the starting angles for BM, which then runs its usual optimization, rounding by diameter sweep, and 2-local bit-flip sweep.

Experiments compare three restart policies: Warm-Start (restarts return to the QAOA-derived point with new random perturbations), Random MultiStart (the baseline, with fresh random initial points on restart), and RandomLocal (a control with a fixed random initial point). BM is capped at 1000 iterations, restarting if 11 consecutive iterations fail to improve the energy. Two instance classes are used: Erdős–Rényi graphs with 10% edge density (ER-10) and fully connected Sherrington–Kirkpatrick spin glasses, both with edge weights drawn from a normal distribution with mean 0.0 and standard deviation 1. They generate 500 random instances for ER-10 at both sizes and for SK at n = 500, and 300 for SK at n = 1000. Each strategy is run with 3 different initialization seeds per instance and averaged. Results are reported as best-found energy, paired energy difference versus the Random MultiStart baseline, and WinRate, all as functions of iteration budget, with 95% confidence intervals from cluster bootstrapping with s = 10^4 resamples.

Why This Matters

The work reframes near-term quantum utility in optimization as quantum-assisted initialization rather than end-to-end quantum replacement of classical solvers, and it provides a concrete, reproducible pipeline for feeding shallow-circuit correlation data into one of the strongest practical MaxCut heuristics. The authors are explicit that this is an improvement in the BM refinement stage, not an end-to-end quantum computational advantage: the depth-one correlators are evaluated classically, and the reported iteration budgets exclude QAOA optimization and warm-start construction, though the preparation cost is described as a modest fraction of a full run.

Real-world applications of MaxCut cited by the paper:

• Finance.
• Graph partitioning.
• Statistical physics (spin glasses, via the Ising mapping).
• General QUBO benchmarking, since any n-variable QUBO maps to an (n+1)-variable MaxCut.

Industry relevance: the results give quantum hardware and hybrid-algorithm groups a low-depth, classically simulable use case for QAOA-style circuits that plugs into existing mature classical infrastructure (the authors build on the MQLib implementation), which is directly relevant to teams evaluating whether near-term devices can contribute value to optimization pipelines before fault tolerance.

Future Directions

• Investigate the apparent favorable scaling of the warm start with system size, since the strategy was generally more effective at n = 1000 than at n = 500 for both problem classes.
• Account for the full cost of the QAOA optimization and warm-start construction inside the comparison budget, which the reported iteration budgets currently exclude.
• Understand and mitigate why the advantage is weaker on fully connected Sherrington–Kirkpatrick instances than on sparse ER-10 graphs, and clarify the GraphOnly versus AllPairs tradeoff at larger budgets.
• Extend the approach beyond depth-one QAOA and to other classical solvers or relaxations, and explore combinations with related quantum-assisted ideas such as quantum preconditioning and relax-and-round.

Target Audience

Researchers and practitioners in quantum optimization and hybrid quantum-classical algorithms, especially those interested in warm-starting and preconditioning strategies; classical optimization researchers working on semidefinite and low-rank MaxCut heuristics who want to know where quantum-derived correlations could add value; and industry or hardware teams assessing realistic near-term use cases for low-depth QAOA. Readers without background in QAOA or SDP relaxations will need to consult the preliminaries, since the paper assumes familiarity with Goemans–Williamson rounding and the Burer–Monteiro parameterization.

Authors’ abstract

Quantum optimization has attracted growing interest as quantum hardware continues to improve, yet state-of-the-art classical solvers remain a formidable benchmark for practical utility. Rather than seeking a fully quantum replacement for classical optimization, we propose a hybrid strategy that uses quantum information to enhance leading classical heuristics. Specifically, we introduce a warm-start method based on local correlators obtained from the Quantum Approximate Optimization Algorithm (QAOA), and use this information to initialize the Burer-Monteiro (BM) rank-two relaxation. We demonstrate numerically that, compared to a random, multi-start initialization baseline (a standard strategy used for BM), this quantum-informed initialization offers a significant head start, i.e., high-quality solutions with very small number of iterations, for two problem classes -- random Erdős Rényi graphs with edge density of $10\%$ (ER-10) and fully-connected Sherrington Kirkpatrick (SK) spin glass models, at $n=500$ and $n=1000$ qubits. At the same time, given enough iterations, the random baseline often eventually catches up and slightly outperforms the warm-start strategy on average, an effect visibly stronger for $n=500$ than for $n=1000$. The results demonstrate an exploitation/exploration tradeoff of using WS to quickly arrive at very good solutions vs exploring slightly better solutions with a larger iterations budget via a standard strategy. Our results highlight how low-depth quantum circuits can provide useful structural information for classical optimization and suggest a promising route toward near-term quantum utility through quantum-assisted initialization.