arXiv:2610.05128
Training Variational Quantum Algorithms Is NP-Hard, Even Locally
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.
AI Summary
Does relaxing VQA training from global optimization to finding a local minimum remove its worst-case computational hardness? This paper proves that finding a local minimizer remains strongly $\mathsf{NP}$-hard, even when the objective is efficiently classically evaluable. More precisely, for every $p\geq 1$, finding parameters in $[0,2\pi]^n$ at $\ell_p$-distance strictly less than $\pi/2$ from some local minimizer is strongly $\mathsf{NP}$-hard. The reduction starts from Stable Set and constructs a quadratic form on $[0,1]^n$ whose local minima have a location dichotomy: if $\alpha(G)<k$, the origin is the unique local minimum; otherwise, every local minimum has a coordinate equal to one. Substituting $x_i=(1-\cos\theta_i)/2$ preserves local minimality and produces a Hermitian trigonometric polynomial of total Fourier degree at most two. The dichotomy becomes a separation between corner minima and minima with a coordinate equal to $\pi$, yielding the approximation bound. Polynomially bounded coefficients establish strong hardness. These objectives are realized exactly using $2n$ qubits, $2n$ single-qubit rotations with shared parameters, and a commuting diagonal two-local observable containing $O(n^2)$ Pauli terms. Thus, the barrier does not depend on measurement uncertainty or entangling circuits. The result concerns worst-case proximity to actual local minimizers, rather than approximate stationarity or typical training performance. The paper notes that structured VQA families can remain tractable, including certain level-one QAOA settings, and leaves characterization of the tractability boundary open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 7 pages, 2 figures