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

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> </mml:math> -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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:math> (QAOA <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi/> <mml:mn>1</mml:mn> </mml:msub> </mml:math> ), we show that tuning the two angles <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>&amp;#x03B3;</mml:mi> <mml:mo>,</mml:mo> <mml:mi>&amp;#x03B2;</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> for weighted Ising models is not a black-box search but a structured signal-processing problem. We prove that the QAOA <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi/> <mml:mn>1</mml:mn> </mml:msub> </mml:math> expectation value is a partial Fourier series in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>&amp;#x03B3;</mml:mi> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>&amp;#x03B2;</mml:mi> <mml:mo>&amp;#x2217;</mml:mo> </mml:msup> <mml:mo stretchy="false">(</mml:mo> <mml:mi>&amp;#x03B3;</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> in closed form to reduce the search to one dimension, and apply a subdivision algorithm that locates the globally optimal <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>&amp;#x03B3;</mml:mi> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>&amp;#x03B3;</mml:mi> <mml:mo>&amp;#x2217;</mml:mo> </mml:msup> <mml:mo>&amp;#x2208;</mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mo>+</mml:mo> </mml:msup> </mml:math> 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.