Undecidable Problems Associated with Variational Quantum Algorithms

Variational Quantum Algorithms (VQAs) are prime candidates for near-term quantum advantage, yet training them is known to be NP-hard. Here we prove a conditional undecidability result for noiseless, digitized VQA training by reducing it to the solvability of a universal Diophantine equation (UDE). Under this conjecture, deciding whether a digitized VQA reaches a given energy threshold is undecidable. We hint that an algebraic proof could proceed by explicitly constructing the polynomial system and applying Hilbert’s tenth problem machinery, while we also provide a pathway for a formal complexity-theoretic proof. Additionally, we prove unconditional undecidability of VQA convergence in open quantum systems. This ties VQA limitations to foundational uncomputability in mathematics and logic.

Georgios Korpas is a Senior Research Scientist in HSBC’s Quantum Technologies group in Singapore and a Senior Research Fellow and Lecturer at the Artificial Intelligence Center, Czech Technical University in Prague. He is also a lead researcher with Archimedes at the Athena Research Center in Athens. His work spans quantum computing, artificial intelligence, and optimization, with a focus on algorithms and financial applications. He holds a PhD in Mathematics from Trinity College Dublin and has published on quantum optimization and topological field theory.