الملخص
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.
الكلمات المفتاحية
الموضوع
بيانات النشر
- المجلة
- غير متاح
- وصول مفتوح
- وصول مفتوح أخضر
اقتبس هذه المقالة
APA 7
Koh, D. E., Mundo, T., Sakos, I., & Varvitsiotis, A. (2026). Training Variational Quantum Algorithms Is NP-Hard, Even Locally. https://omanscience.com/ar/articles/training-variational-quantum-algorithms-is-np-hard-even-locally
MLA 9
Koh, Dax Enshan, et al. "Training Variational Quantum Algorithms Is NP-Hard, Even Locally." https://omanscience.com/ar/articles/training-variational-quantum-algorithms-is-np-hard-even-locally.
شيكاغو (المؤلف–التاريخ)
Koh, Dax Enshan, Triscia Mundo, Iosif Sakos, and Antonios Varvitsiotis. 2026. "Training Variational Quantum Algorithms Is NP-Hard, Even Locally." https://omanscience.com/ar/articles/training-variational-quantum-algorithms-is-np-hard-even-locally.
هارفارد
Koh, D. E., Mundo, T., Sakos, I. and Varvitsiotis, A. (2026) 'Training Variational Quantum Algorithms Is NP-Hard, Even Locally', Available at: https://omanscience.com/ar/articles/training-variational-quantum-algorithms-is-np-hard-even-locally.
فانكوفر
Koh DE, Mundo T, Sakos I, Varvitsiotis A. Training Variational Quantum Algorithms Is NP-Hard, Even Locally. https://omanscience.com/ar/articles/training-variational-quantum-algorithms-is-np-hard-even-locally
IEEE
D. E. Koh, T. Mundo, I. Sakos, and A. Varvitsiotis, "Training Variational Quantum Algorithms Is NP-Hard, Even Locally," https://omanscience.com/ar/articles/training-variational-quantum-algorithms-is-np-hard-even-locally.