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

======= Abstract =======

Parameter optimization is widely regarded as one of the main classical bottlenecks of variational quantum algorithms, and general VQA training is known to be NP-hard. In this talk, I will show that this worst-case perspective is not the right lens for level-1 QAOA on many practically relevant weighted optimization problems. For arbitrary weighted Ising Hamiltonians, the QAOA₁ expectation landscape has a hidden Fourier structure: it can be written as a partial Fourier series whose accessible frequencies are determined explicitly by the problem coefficients. This viewpoint turns QAOA₁ tuning from a generic black-box optimization problem into a structured signal-processing problem. 

Using this Fourier representation, we derive instance-wise bandwidth bounds and a Nyquist-type sampling criterion, explaining why coarse grid search followed by local refinement can fail even when only two angles are being optimized. We then analytically eliminate the mixer angle, reducing the original two-parameter landscape to a one-dimensional optimization problem over the problem angle. By combining this reduction with a Fourier-analytic subdivision algorithm, we compute the globally optimal QAOA₁parameters to any desired precision, with a certificate of optimality, using a number of function evaluations that scales linearly with the relevant Fourier bandwidth for fixed precision. 

Beyond certified parameter tuning, the Fourier perspective also explains an empirical phenomenon often observed in large weighted instances: the optimal problem angle tends to concentrate near origin, and the first local optimum often coincides with the global optimum on average. Numerical experiments show that the resulting tuning method substantially improves QAOA₁ and RQAOA₁performance on dense weighted QUBO benchmarks. Overall, this work replaces heuristic QAOA₁ parameter search with a provably reliable, frequency-certified optimization framework for practically relevant weighted Ising models.

=============== About the Speaker ===============

V Vijendran recently began his PhD under the National Quantum Scholarship Scheme, jointly hosted by the Centre for Quantum Technologies at the National University of Singapore and the A*STAR Quantum Innovation Centre. He completed a dual Bachelor’s degree in Advanced Computing with Honours and Science at the Australian National University, graduating with First Class Honours. Prior to his PhD, Vijendran spent five years at the Centre for Quantum Computation and Communication Technology in Australia, working with Ping Koy Lam’s group as a research scholar. His research has spanned quantum foundations, machine learning for experimental quantum optics, and variational quantum algorithms for combinatorial optimisation, including both theoretical and industrially motivated problems. His current research focuses on identifying practical routes to quantum advantage in optimisation, machine learning, and learning theory, across both near-term and fault-tolerant quantum computing regimes.