{"id":"arxiv/2610.05128","url":"https://arxiv.org/abs/2610.05128","tags":["quant-ph","cs.CC","math.OC"],"score":0,"title":"Training Variational Quantum Algorithms Is NP-Hard, Even Locally","domain":"quant-ph","source":"arxiv","authors":["Dax Enshan Koh","Triscia Mundo","Iosif Sakos","Antonios Varvitsiotis"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-04","reactions":{}}