Training Variational Quantum Algorithms Is NP-Hard, Even Locally
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 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 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 ℓp-distance strictly less than π/2 of some local minimizer, for every p≥ 1. Our central technical result is that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly 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.
Related
- Krylov-Lie Algebras for Variational Quantum Algorithms: Geometric, Depth-Aware Insights into Expressivity and Trainability
- Scaled-Gradient Hard Thresholding Algorithms for Sparse Signal Recovery
- Some Properties of Mordukhovich Derivatives with Applications to Locally Variational Inequalities in Banach Spaces
- Fixed-Point Formulation and Parallel Averaged Operator Algorithms for Generalized Variational Inclusion Problems
- Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
BibTeX
@misc{koh2026training,
title = {{Training Variational Quantum Algorithms Is NP-Hard, Even Locally}},
author = {Dax Enshan Koh and Triscia Mundo and Iosif Sakos and Antonios Varvitsiotis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05128},
eprint = {2610.05128},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05128},
}
RIS
TY - UNPB
TI - Training Variational Quantum Algorithms Is NP-Hard, Even Locally
AU - Dax Enshan Koh
AU - Triscia Mundo
AU - Iosif Sakos
AU - Antonios Varvitsiotis
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05128
UR - https://arxiv.org/abs/2610.05128
AB - 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 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 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 ℓ_p-distance strictly less than π/2 of some local minimizer, for every p≥ 1. Our central technical result is that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly 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.
ER -