Training variational quantum algorithms is hard even around local minima
Training Variational Quantum Algorithms Is NP-Hard, Even Locally
Computational Complexity
Summary
Training quantum algorithms that use adjustable circuits is known to be very hard if you want the absolute best settings. This paper shows that even just finding a setting that is close to a good local solution is still very hard. The authors prove this remains true even when the function you’re trying to minimize can be calculated quickly using a classical computer. They demonstrate this hardness by connecting the problem to difficult mathematical cases tied to quantum circuit structures.
What this means in practice
- •For quantum software engineers: Avoid relying on guaranteed efficient training methods for variational quantum circuits as finding near-local minima may be computationally infeasible in some cases.
- •For algorithm designers: Recognize that designing classical optimizers for variational quantum training faces inherent worst-case hardness even for local optimization tasks.
A theory result. No direct application yet.
Authors
Dax Enshan Koh, Triscia Mundo, Iosif Sakos, Antonios Varvitsiotis
Abstract
Variational quantum algorithms (VQAs) generally rely on classical optimization to train parameterized quantum circuits. This training seeks to minimize an objective function, and its efficiency is central to the practical success of these algorithms. However, globally minimizing such training objectives over the circuit parameters is known to be $\mathsf{NP}$-hard, limiting the prospect of general guarantees for efficient training. In this Letter, we prove that even the weaker task of finding a local minimum of such VQA training objectives is strongly $\mathsf{NP}$-hard, including when the objective admits efficient classical evaluation. Moreover, we show that this hardness persists even for the task of finding a parameter vector within $\ell_p$-distance strictly less than $π/2$ of some local minimizer, for every $p\geq 1$. Our central technical result is that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly $\mathsf{NP}$-hard. By explicitly constructing quantum circuits whose training objectives reproduce these hard instances, we obtain a polynomial-time reduction to VQA training. Our results establish a fundamental computational barrier to variational quantum training: even reaching the vicinity of a local minimum remains hard in the worst case.