Description
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, and worst-case results showing that training QAOA is NP-hard are often read as evidence that even the shallowest circuits are hard to tune. We argue that this picture does not capture the practically relevant regime. 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 as the landscape's oscillation rate grows with problem size, density, and weight. 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. The residual hardness is thus confined to pathological instances---those with incommensurable or exponentially scaling weights---rather than arbitrary Ising Hamiltonians. 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 small-angle initialisation and allowing gradient descent to replace exhaustive line searches. Validated within Recursive QAOA (RQAOA) on weighted Erdos-Renyi instances of 128 and 256 qubits, our method consistently outperforms both coarsely optimised RQAOA and semidefinite programming.
| I am the presenting author | Yes |
|---|