Training quantum algorithms is hard even near a local minimum
A proof showed that finding or even approaching a local minimum when training variational quantum circuits is computationally hard in the worst case.
Edited by Boris Djordjevic · Paperfoot
A mathematical proof in a preprint showed that finding a local minimum when training parameterized quantum circuits in variational quantum algorithms is strongly NP-hard. These quantum algorithms rely on classical optimization to tune circuit parameters to minimize an objective function. While finding the globally optimal parameters was already known to be NP-hard—a standard term for problems that lack fast general algorithms—the proof established that even finding a local minimum is intractable in the worst case, including when the objective can be evaluated efficiently.
The authors proved that this computational barrier persists even when attempting to find parameters within a specific distance of a local minimizer. To show this, they proved that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly NP-hard, and constructed quantum circuits that reproduce these hard instances.
Why it matters
The mathematical proof establishes a fundamental computational barrier for variational quantum algorithms by ruling out general guarantees of efficient training, even when algorithms only seek local improvements. It shows that the hardness of training persists in the worst case rather than stemming solely from the difficulty of finding a global optimum.
Caveats
The finding is a worst-case theoretical proof, meaning it does not rule out whether practical quantum algorithms might train successfully on specific typical problems. Additionally, the paper is a preprint that has not yet undergone formal peer review.
In this paper
variational quantum algorithm training
What it shows
- Approximating a local minimizer of an efficiently represented VQA training objective within l_p-distance strictly less than π/2 is strongly NP-hard for every p≥ 1.
More precisely, for every p≥ 1, it is strongly \mathsf{NP} -hard to find a parameter vector in [0,2\pi]^{n} within \ell_{p} -distance strictly less than \pi/2 of some local minimizer.
Theorem 1.
- Approximating a local minimizer of an efficiently represented Hermitian trigonometric polynomial of total Fourier degree at most 2 within l_p-distance strictly less than π/2 is strongly NP-hard for every p≥ 1.
For every p≥ 1, approximating a local minimizer of an efficiently represented Hermitian trigonometric polynomial of total Fourier degree at most 2 within \ell_{p} -distance strictly less than \pi/2 is strongly \mathsf{NP} -hard.
Proposition 2.
- The quadratic function associated with the Stable Set problem exhibits a dichotomy where the origin is the unique local minimizer if the stability number is less than k, and every local minimizer has at least one coordinate equal to 1 if it is at least k.
For a graph G and positive integer threshold k, the construction exhibits a sharp dichotomy: if the stability number \alpha(G)<k, then the origin is the unique local minimizer, whereas if \alpha(G)≥ k, then every local minimizer has at least one coordinate equal to 1.
I Introduction
- Hardness of approximating a local minimizer already arises for circuits consisting solely of single-qubit rotations with shared parameters and a commuting diagonal two-local observable.
Notably, this hardness already arises for circuits consisting solely of single-qubit rotations with shared parameters and a commuting diagonal two-local observable.
IV Concluding remarks
Quoted word for word from the full text on arXiv.
The paper
Training Variational Quantum Algorithms Is NP-Hard, Even Locally
arXiv, Oct 4, 2026, Open access, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.05128
arXiv:2610.05128v1 in quant-ph, also cs.CC, math.OC
Comments: 7 pages, 2 figures
Cite as BibTeX
@misc{koh2026training,
title = {Training Variational Quantum Algorithms Is NP-Hard, Even Locally},
author = {Koh, Dax Enshan and Mundo, Triscia and Sakos, Iosif and Varvitsiotis, Antonios},
year = {2026},
eprint = {2610.05128},
archivePrefix = {arXiv},
primaryClass = {quant-ph},
doi = {10.48550/arxiv.2610.05128},
url = {https://arxiv.org/abs/2610.05128}
}