Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models

Quantum 10, 2158 (2026).

https://doi.org/10.22331/q-2026-07-15-2158

The Quantum Approximate Optimisation Algorithm (QAOA) tackles combinatorial optimisation problems by encoding their solutions into the ground state of an Ising Hamiltonian prepared by a $p$-level parameterised circuit, with the angles tuned classically. Parameter optimisation is widely regarded as a central bottleneck, even for the shallowest circuits. Focusing on QAOA at $p=1$ (QAOA$_1$), we show that tuning the two angles $(gamma, beta)$ for weighted Ising models is not a black-box search but a structured signal-processing problem. We prove that the QAOA$_1$ expectation value is a partial Fourier series in $gamma$ whose frequencies are determined explicitly by the problem’s couplings and fields, giving instance-wise bandwidth bounds and, via the Nyquist–Shannon theorem, the sampling resolution needed to avoid the aliasing that causes coarse-grid searches to return spurious optima. We then eliminate the mixer angle analytically, computing $beta^*(gamma)$ in closed form to reduce the search to one dimension, and apply a subdivision algorithm that locates the globally optimal $gamma$ in polynomial time with a certificate of optimality when the weights are commensurable and bounded. For regular weighted graphs, we further prove the conventional wisdom that the globally optimal $gamma^* in mathbb{R}^+$ concentrates near zero and coincides with the first local optimum, giving a rigorous account of the empirical success of small-angle initialisation and allowing gradient descent to replace exhaustive line searches. Validated within Recursive QAOA (RQAOA) on weighted instances of 128 and 256 qubits, our method consistently outperforms both coarsely optimised RQAOA and semidefinite programming.