Undecidable problems associated with variational quantum algorithms

• URL: http://arxiv.org/abs/2503.23723v1
• Date: Mon, 31 Mar 2025 04:52:43 GMT
• Title: Undecidable problems associated with variational quantum algorithms
• Authors: Georgios Korpas, Vyacheslav Kungurtsev, Jakub Mareček,
• Abstract summary: Variational Quantum Algorithms (VQAs) are widely studied as candidates for near-term quantum advantage.<n>Recent work has shown that training VQAs is NP-hard in general.<n>We present a conditional result suggesting that the training of VQAs is undecidable, even in idealized, noiseless settings.
• Score: 2.8166046619628315
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA), are widely studied as candidates for near-term quantum advantage. Recent work has shown that training VQAs is NP-hard in general. In this paper, we present a conditional result suggesting that the training of VQAs is undecidable, even in idealized, noiseless settings. We reduce the decision version of the digitized VQA training problem-where circuit parameters are drawn from a discrete set-to the question of whether a universal Diophantine equation (UDE) has a root. This reduction relies on encoding the UDE into the structure of a variational quantum circuit via the matrix exponentials. The central step involves establishing a correspondence between the objective function of the VQA and a known UDE of 58 variables and degree 4. Our main result is conditional on a natural conjecture: that a certain system of structured complex polynomial equations-arising from the inner product of a VQA circuit output and a fixed observable-has at least one solution. We argue this conjecture is plausible based on dimension-counting arguments (degrees of freedom in the Hamiltonians, state vector, and observable), and the generic solvability of such systems in algebraic geometry over the complex numbers. Under this assumption, we suggest that deciding whether a digitized VQA achieves a given energy threshold is undecidable. This links the limitations of variational quantum algorithms to foundational questions in mathematics and logic, extending the known landscape of quantum computational hardness to include uncomputability. Additionally, we establish an unconditional undecidability result for VQA convergence in open quantum systems.

Related papers

• Quantum Computing for Optimizing Aircraft Loading [1.055551340663609]
  The aircraft loading optimization problem is a computationally hard problem with the best known classical algorithm scaling exponentially with the number of objects. We propose a quantum approach based on a multi-angle variant of the QAOA algorithm (MAL-VQA) designed to utilize a smaller number of two qubit gates in the quantum circuit. We demonstrate the performance of the algorithm on different instances of the aircraft loading problem by execution on IonQ QPUs Aria and Forte.
  arXiv  Detail & Related papers  (2025-04-02T10:10:11Z)
• Quantum computation of a quasiparticle band structure with the quantum-selected configuration interaction [0.0]
  We propose a hybrid approach that combines the quantum subspace expansion (QSE) method with the quantum-selected configuration interaction (QSCI) method for calculating quasiparticle band structures. We demonstrate the quantum computation of the quasiparticle band structure of a silicon using 16 qubits on an IBM quantum processor.
  arXiv  Detail & Related papers  (2025-04-01T00:25:19Z)
• Generic and Scalable Differential Equation Solver for Quantum Scientific Computing [4.067407250874754]
  One of the most important topics in quantum scientific computing is solving differential equations. In this paper, a generalized quantum functional expansion framework is proposed. Four example differential equations are solved to demonstrate the generic QFE framework.
  arXiv  Detail & Related papers  (2024-09-24T21:09:54Z)
• Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
  Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization. We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
  arXiv  Detail & Related papers  (2024-07-08T22:02:39Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Variational Quantum Eigensolver with Constraints (VQEC): Solving Constrained Optimization Problems via VQE [0.0]
  Variational quantum approaches have shown great promise in finding near-optimal solutions to computationally challenging tasks. This work proposes a hybrid quantum-classical algorithmic paradigm termed VQEC to handle optimization with constraints.
  arXiv  Detail & Related papers  (2023-11-14T19:49:09Z)
• QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
  We focus on variational quantum circuits (VQC), which emerged as the most promising candidates for the quantum counterpart of neural networks. Although showing promising results, VQCs can be hard to train because of different issues, e.g., barren plateau, periodicity of the weights, or choice of architecture. We propose a gradient-free algorithm inspired by natural evolution to optimize both the weights and the architecture of the VQC.
  arXiv  Detail & Related papers  (2023-04-14T08:03:20Z)
• Fundamental limitations on optimization in variational quantum algorithms [7.165356904023871]
  A leading paradigm to establish such near-term quantum applications is variational quantum algorithms (VQAs) We prove that for a broad class of such random circuits, the variation range of the cost function vanishes exponentially in the number of qubits with a high probability. This result can unify the restrictions on gradient-based and gradient-free optimizations in a natural manner and reveal extra harsh constraints on the training landscapes of VQAs.
  arXiv  Detail & Related papers  (2022-05-10T17:14:57Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Efficient measure for the expressivity of variational quantum algorithms [72.59790225766777]
  We exploit an advanced tool in statistical learning theory, i.e., covering number, to study the expressivity of variational quantum algorithms. We first exhibit how the expressivity of VQAs with an arbitrary ansatze is upper bounded by the number of quantum gates and the measurement observable. We then explore the expressivity of VQAs on near-term quantum chips, where the system noise is considered.
  arXiv  Detail & Related papers  (2021-04-20T13:51:08Z)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form. Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries. This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
  arXiv  Detail & Related papers  (2020-08-03T18:00:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.