Iterative Interpolation Schedules for Quantum Approximate Optimization Algorithm
This work addresses the challenge of optimizing many parameters in deep QAOA circuits, which is a key bottleneck for practical quantum optimization.
The authors present an iterative interpolation method for QAOA that constructs high-quality parameter schedules for large circuit depths by expressing them in a basis of orthogonal functions. Their method achieves better performance with fewer optimization steps than existing methods, and for the largest LABS instance they achieve near-optimal merit factors with schedules exceeding 1000 layers, an order of magnitude beyond previous methods.
Quantum Approximate Optimization Algorithm (QAOA) is a promising quantum heuristic with empirical evidence of speedup over classical state-of-the-art for some problems. QAOA uses a parameterized circuit with $p$ layers, where higher $p$ yields better solutions, but requires optimizing $2p$ independent parameters, which is challenging at large $p$. We present an iterative interpolation method that exploits the smoothness of optimal parameter schedules by expressing them in a basis of orthogonal functions, generalizing the work of Zhou et al. By optimizing a small number of basis coefficients and iteratively increasing both circuit depth and coefficient count until convergence, our method constructs high-quality schedules for large $p$. We provide theoretical justification using Jackson's theorem and Lipschitz continuity to bound the required number of basis coefficients for a given accuracy. Our approach achieves better performance with fewer optimization steps than existing methods across three benchmark problems: the Sherrington-Kirkpatrick (SK) model, portfolio optimization, and Low Autocorrelation Binary Sequences (LABS). For the largest LABS instance, we achieve near-optimal merit factors with schedules exceeding 1000 layers, an order of magnitude beyond previous methods. Additionally, we observe that a mild growth in QAOA depth suffices to solve the SK model exactly, a result of independent theoretical interest.