Undecidable problems associated with variational quantum algorithms

Georgios Korpas, Vyacheslav Kungurtsev, Jakub Mareček · 2025

Read Undecidable problems associated with variational quantum algorithms by Georgios Korpas, Vyacheslav Kungurtsev, Jakub Mareček (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23723.txt.

Description

Georgios Korpas, Vyacheslav Kungurtsev, and Jakub Mareček study undecidable problems for variational quantum algorithms in two thousand twenty-five. Such algorithms are top bets for near term quantum gain. Past work showed their training is NP-hard in general. The team asks if it may be worse than hard: impossible to decide at all.

They reduce a digitized training question to a Diophantine root question. Matrix exponentials encode that equation inside a quantum circuit. The result rests on a stated conjecture about a system of equations. They back it with dimension counts and generic solvability in geometry. An unconditional result covers open quantum systems as well.

Catalog record

CREATORGeorgios Korpas, Vyacheslav Kungurtsev, Jakub Mareček
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-23723

Browse the full library · About the Tower of Babel