Metraipolis › archive › dc_0a596fa06064
Training Variational Quantum Algorithms Is NP-Hard, Even Locally — arXiv:2610.05128
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.05128
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T13:07:02.829Z
- SHA-256 of the archived text
1a8df4fe197df936ec8d68e8cb3e638ab4be3cf79d4c9b14c858609bdf603270- Stable URL of this page
https://metraipolis.com/documento/dc_0a596fa06064
How to cite
Training Variational Quantum Algorithms Is NP-Hard, Even Locally — arXiv:2610.05128 — arXiv (en), https://arxiv.org/abs/2610.05128 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0a596fa06064 (Metraipolis archive dc_0a596fa06064, sha256 1a8df4fe197df936ec8d68e8cb3e638ab4be3cf79d4c9b14c858609bdf603270)
BibTeX
@misc{dc0a596fa06064,
title = {Training Variational Quantum Algorithms Is NP-Hard, Even Locally — arXiv:2610.05128},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.05128},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0a596fa06064; sha256 1a8df4fe197df936ec8d68e8cb3e638ab4be3cf79d4c9b14c858609bdf603270},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.05128. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\pi/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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.05128 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T11:21:31.936Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).