Abstract
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm for solving combinatorial optimization problems. QAOA encodes solutions into the ground state of a Hamiltonian, approximated by a $p$-level parameterized quantum circuit composed of problem and mixer Hamiltonians, with parameters optimized classically. While deeper QAOA circuits can offer greater accuracy, practical applications are constrained by complex parameter optimization and physical limitations such as gate noise, restricted qubit connectivity, and state-preparation-and-measurement errors, limiting implementations to shallow depths.
This work focuses on QAOA$_1$ (QAOA at $p=1$) for QUBO problems, represented as Ising models. Despite QAOA$_1$ having only two parameters, $(\eta, \eta)$, we show that their optimization is challenging due to a highly oscillatory landscape, with oscillation rates increasing with the problem size, density, and weight. This behavior necessitates high-resolution grid searches to avoid distortion of cost landscapes that may result in inaccurate minima.
We propose an efficient optimization strategy that reduces the two-dimensional $(\eta, \eta)$ search to a one-dimensional search over $\eta$, with $\eta^*$ computed analytically. We establish the maximum permissible sampling period required to accurately map the $\eta$ landscape and provide an algorithm to estimate the optimal parameters in polynomial time. Furthermore, we rigorously prove that for regular graphs on average, the globally optimal $\eta^* \in \mathbb{R}^+$ values are concentrated very close to zero and coincide with the first local optimum, enabling gradient descent to replace exhaustive line searches. This approach is validated using Recursive QAOA (RQAOA), where it consistently outperforms both coarsely optimized RQAOA and semidefinite programs across all tested QUBO instances.
Blogger's Review: The intersection of quantum computing advancements with classical optimization techniques provides new avenues for tackling complex combinatorial optimization problems. The effective tuning of parameters not only enhances algorithm performance but also lays the groundwork for the practical application of quantum computing. Future research could further explore deeper QAOA circuits and their performance in real-world applications.