PaperlayerView exact revision on arXiv

Source-linked AI summary

Training variational quantum algorithms is NP-hard

Lennart Bittel, Martin Kliesch

arXiv:2101.07267v2quant-ph

TL;DR

The paper asks whether the classical training problem in variational quantum algorithms is tractable, including when the underlying quantum systems are classically easy. By encoding NP-hard problems into VQA optimization landscapes, it shows NP-hardness across oracle-based, logarithmic-qubit, free-fermionic, and QAOA settings, with persistent far-from-optimal local minima affecting descent methods.

  • Problem

    VQAs require a classical computer to optimize parametrized quantum circuits on near-term devices, but the tractability of this classical optimization is the central challenge studied here.

  • Method

    The paper encodes NP-hard MaxCut instances into VQA optimization tasks and analyzes oracle-based, logarithmic-qubit, QAOA, and free-fermionic settings.

  • Results

    VQA classical optimization is NP-hard even for logarithmically many qubits or free fermions, and the landscapes can contain many far-from-optimal persistent local minima.

  • Takeaways & Limitations

    Gradient and higher-order descent methods can converge to initialization-dependent local minima with far-from-optimal solutions, motivating effective initialization and non-local heuristics.

Abstract

from arXiv · show

Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum ap- proximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parameterized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming P $\neq$ NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima. This means that gradient and higher order descent algorithms will generally converge to far from optimal solutions.

I. INTRODUCTION

The paper studies the classical optimization challenge in variational quantum algorithms and shows that it is intrinsically hard across several settings, with persistent local minima limiting descent-based training.

  • Motivation: Near-term quantum devices use shallow circuits because noisy gates and the overhead of noise reduction and error correction remain limiting factors.
  • Motivation: VQAs train parametrized quantum circuits by classically optimizing expectation-value loss functions, including VQEs and QAOAs.
  • Problem: Classical parameter optimization is the paper’s focus because it must be both sufficiently accurate and fast, beyond the separate challenge of circuit expressivity.
  • Problem: Training can encounter barren plateaus with vanishing gradients, caused by random initialization, observable nonlocality, or gate noise, and higher-order methods do not fully resolve them.
  • Contribution: The authors encode NP-hard MaxCut instances into several VQA optimization tasks and find many local minima that are far from optimal.
  • Results: The optimization is NP-hard even at constant relative precision with oracle access, and remains hard for logarithmically many qubits, free fermions, and QAOA settings.

III. Variational quantum algorithms

The paper frames VQA as hybrid optimization of parametrized quantum circuits and analyzes the classical training problem across oracle-based, efficiently simulable, QAOA, and free-fermionic settings.

  • VQA uses classically tunable circuit parameters to minimize an observable’s expectation value.
  • The analysis covers qubit systems with oracle access, logarithmically many qubits with efficient classical simulation, QAOA instances, and free-fermionic systems.

A. VQA optimization with quantum computer access

The paper formulates VQA training as classical optimization assisted by oracle expectation-value queries and reduces continuous optimization to MaxCut. It proves that no deterministic polynomial-time classical algorithm can solve the formulation under P ≠ NP, even with bounded optimization error guarantees.

  • Problem formulation: VQA training uses classical optimization of expectation values returned by an oracle for parameterized quantum circuits.The oracle supplies expectation values to the classical algorithm, isolating the classical optimization effort in hybrid quantum computation.
  • Hardness result: The oracular VQA minimization problem is NP-hard under the assumption P ≠ NP.The proof reduces a continuous MaxCut optimization problem to VQA minimization using an Ising observable and circuit generators.
  • Error measure: The optimization error separates ansatz model mismatch from failure of the classical optimizer to reach the best value within the ansatz class.The error is normalized using the observable’s spectral width, and the optimization component is defined across all considered instances.
  • Approximation guarantee: No polynomial-time algorithm can guarantee optimization error Δ < 1 for all VQAs if P ≠ NP.Such a guarantee would imply the ability to solve the underlying continuous MaxCut problem to arbitrary precision.
  • Reduction: The reduction preserves MaxCut approximation behavior by mapping the VQA objective and optimum to the continuous and discrete MaxCut values.The construction has no model mismatch, so the algorithm’s VQA output directly yields an approximation to MaxCut.

B. Logarithmic number of qubits — polynomial Hilbert space dimension

The paper shows that VQA optimization remains NP-hard when the quantum system has only logarithmically many qubits and polynomial Hilbert-space dimension. This hardness also holds for a single-layer VQA and for minimizing time-evolved observables.

  • Polynomial Hilbert space dimension: With N ∈ O(log(d)) qubits, VQA expectation values and ground-state problems are efficiently computable, yet VQA optimization remains NP-hard.The result shows that the optimization difficulty is intrinsic rather than inherited solely from a hard ground-state problem.
  • Decision complexity: The logarithmic-qubit VQA minimization problem has a decision version that is NP-complete.A parameter vector serves as a polynomially verifiable proof because expectation values can be computed efficiently in polynomial-dimensional Hilbert spaces.
  • Single-layer hardness: One VQA layer is sufficient for NP-hard optimization.The construction uses efficiently expressible approximate ergodic energy spectra to reproduce the hard continuous optimization problem.
  • Single-layer hardness: The chosen energy spectra can approximate the continuous MaxCut objective to arbitrary precision within a single-layer VQA.The expectation value approximates the continuous objective after mapping the parameters through the energy spectrum.
  • Continuous-time evolution: For logarithmically many qubits, minimizing the expectation value of a unitarily time-evolved observable over t ∈ R+ is NP-hard.This follows by viewing the single-layer VQA construction as continuous-time evolution.

C. Quantum approximate optimization algorithms for a logarithmic number of qubits

The paper shows that QAOA optimization remains NP-hard with logarithmically many qubits, including under bounded Hamiltonian norms and even with one layer. Polynomial-time methods also face a nonzero optimization-error guarantee tied to MaxCut approximation hardness.

  • Hardness results: The hardness of VQA optimization for logarithmically many qubits also applies to QAOA problems.The construction embeds a modified continuous optimization problem into the QAOA circuit and penalizes deviations through the expectation value.
  • Hardness results: QAOA optimization is NP-hard even when restricted to a single layer.The result is obtained by reducing single-layer VQA optimization to QAOA.
  • Implementation scope: The initial QAOA hardness construction uses Hamiltonian energies spanning many orders of magnitude, requiring extremely precise implementation.The paper then establishes hardness under much simpler spectra with bounded Hamiltonian norms.
  • Hardness results: QAOA optimization remains NP-hard for periodic parameters β, γ ∈[0, 2π)^L with ∥Hb∥≤3 and ∥Hc∥≤3.The bounded norms restrict the Hamiltonian energies to values in {−3, −2, ..., 3}.
  • Approximation limits: All polynomial-time algorithms for QAOA, and therefore VQA optimization, have optimization error Δ≥(1−αmax)/2, where αmax is MaxCut’s approximation ratio.This lower bound follows from the reduction connecting the QAOA objective to MaxCut.
  • Approximation limits: For gradient-based methods on logarithmically many qubits, the optimization error satisfies Δ≥1/4 when the MaxCut approximation ratio is α=1/2.The bound uses the stated approximation ratio for the relevant local-minimum construction.

D. Free fermionic models

The free-fermion setting provides a classically tractable model in which VQA optimization is nevertheless NP-hard. The paper establishes this through a reduction from an NP-hard continuous optimization problem using quadratic fermionic dynamics and observables.

  • Model setting: Free fermionic models have no particle-particle interactions and can be simulated efficiently for Gaussian input states and observables.This motivates using them to test whether VQA optimization hardness persists in classically tractable systems.
  • Model setting: The free-fermion VQA uses quadratic observables defined by Hermitian coefficient matrices and evolves an initial state through quadratic generators.The optimization task is to choose parameters minimizing the expectation value of the evolved observable.
  • Hardness result: Problem 7 is NP-hard even when the initial state ρ0 is pure.The proof reduces the continuous optimization problem to a free-fermion VQA instance.
  • Reduction: The construction uses n=d×2 fermionic modes and L=d layers to encode a Hermitian adjacency matrix A into the observable.The coefficient matrix is defined using the matrix construction employed for the NP-hard objective.
  • Reduction: The evolved observable is represented in the Heisenberg picture by conjugating its coefficient matrix with the layer unitaries.The resulting expectation value reproduces the objective from the source optimization problem, completing the reduction.

IV. CONCLUSION AND OUTLOOK

The conclusion argues that classical VQA training is intrinsically difficult: it is NP-hard, remains hard in simple systems, and can be obstructed by persistent far-from-optimal local minima. The authors therefore point toward better initialization and non-local optimization heuristics.

  • Conclusion: No polynomial-time algorithm can achieve optimization error Δ<1 on all instances assuming P≠NP.This hardness persists even for logarithmically many qubits and free fermions.
  • Conclusion: The hardness of VQA optimization does not merely arise from the difficulty of solving the underlying ground-state problem.The result already holds for systems whose ground-state problems are classically tractable.
  • Training landscapes: NP-hard problems can be encoded into local extrema of VQA optimization landscapes.Gradient descent and higher-order methods can converge to local minima determined largely by initialization.
  • Training landscapes: For logarithmically many qubits, gradient and higher-order methods can have approximation error Δ≥1/4.The paper notes that this is significantly worse than guarantees from modern efficient MaxCut solvers for the particular VQA.
  • Outlook: The paper emphasizes effective initialization procedures and non-local heuristics as directions for reaching smaller optimization errors.These directions target persistent local minima that can trap local optimization methods.

Appendix A: Proof of Lemma 2 on ergodic energy spectra

The appendix introduces a continuous trigonometric construction through a desired phase vector and concludes the associated argument.

  • Proof: The appendix begins from a definition of E and concludes after establishing the intended result.The supplied passages provide only the construction’s opening and closing statements.
  • Construction: The construction represents the desired phase vector as φ∈[0,2π)^n.The phases are introduced before defining the appendix’s continuous trigonometric object.

Appendix B: Proof of Theorem 4 on multilayer QAOAs

The appendix constructs a multilayer QAOA instance encoding MaxCut and shows that optimizing it reproduces the source optimization problem. The construction uses layered Hilbert-space dynamics and establishes bounded Hamiltonian norms.

  • Construction: The reduction uses a Hilbert space with 2d + 1 subspaces, each isomorphic to K, where d is the MaxCut matrix size and the QAOA depth.The basis states are indexed by graph vertices, auxiliary bits, and subspace labels.
  • Layered dynamics: The proof defines transfer Hamiltonians from two-level unitary evolutions whose eigenvalues determine the layered state transfer.The transfer terms are specified by cases involving indices i, j and auxiliary bits a, b.
  • Construction: The MaxCut solution is encoded in the final subspace H2d+1 through a problem Hamiltonian Hp.The construction begins with an adjacency matrix A for an unweighted graph with at least one edge.
  • Layered dynamics: Applying all d QAOA layers yields an expectation value containing a graph-dependent term plus a nonnegative remainder from the intermediate subspaces.The remainder is the expectation of Hc within H1 ⊕ ··· ⊕ H2d.
  • Reduction result: The objective is minimized at shifted local extrema βi ∈ {π/2, 3π/2}; choosing γi = π makes the relevant function equal 1 and sets ⟨Orest⟩ = 0.Under these settings, the QAOA optimization is equivalent to minimizing μ(β − π/2), and an approximation algorithm yields a lower bound to MaxCut(A).
  • Norm bounds: The constructed Hamiltonians satisfy the norm bounds ∥Hc∥ = 1 and ∥Hb∥ = 3.The appendix obtains these bounds by direct calculation from the ground-state Hamiltonian construction.

Appendix C: Free fermions

The appendix introduces particle-number-preserving free-fermion Hamiltonians and derives efficient descriptions of their dynamics, normal forms, and thermal-state covariance matrices.

  • Setup: The free-fermion setting consists of n fermionic modes with annihilation operators c1, …, cn.The discussion is restricted to particle-number-preserving Hamiltonians.
  • Time evolution: Time evolution of quadratic observables can be simulated through coefficient matrices in the Heisenberg picture.The relevant operator and Hamiltonian coefficient matrices are denoted o and h.
  • Time evolution: The Hilbert-space unitary eiHt is represented on second moments by the n × n unitary matrix eiht.This gives an efficient level of description for the evolution of second moments.
  • Normal form: Quadratic observables admit a normal form obtained by a unitary mode transformation that preserves the commutation relations.A transformation u ∈ U(n) diagonalizes the coefficient matrix as h = u†˜hu.
  • Normal form: The diagonal form describes n decoupled modes with eigenenergies Ei ∈ {0, λi}, so an eigenstate’s total energy is the sum of its mode energies.The ground-state energy is non-degenerate when every λi is nonzero.
Loading 2101.07267v2…