Training variational quantum algorithms is NP-hard

Abstract

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 $\ne$ 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.

arXiv comment8+4 pages, 1 Figure

References in corpus (12)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Barren plateaus in quantum neural network training landscapes
• Adiabatic Quantum Computing
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• Quantum Natural Gradient
• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• Estimating the gradient and higher-order derivatives on quantum hardware
• Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
• Higher Order Derivatives of Quantum Neural Networks with Barren Plateaus
• Computational Difficulty of Global Variations in the Density Matrix Renormalization Group

Cited by in corpus (210)

• Variational Quantum Algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• The Variational Quantum Eigensolver: a review of methods and best practices
• Challenges and Opportunities in Quantum Machine Learning
• Quantum computing for finance
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Barren Plateaus in Variational Quantum Computing
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Quantum circuit architecture search for variational quantum algorithms
• Challenges and Opportunities in Quantum Optimization
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Theory of overparametrization in quantum neural networks
• Digital quantum simulation of open quantum systems using quantum imaginary time evolution
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• Qubit-excitation-based adaptive variational quantum eigensolver
• Avoiding barren plateaus using classical shadows
• Quantum Krylov subspace algorithms for ground and excited state energy estimation
• Benchmarking the performance of portfolio optimization with QAOA
• Theory for Equivariant Quantum Neural Networks
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks
• ADAPT-VQE is insensitive to rough parameter landscapes and barren plateaus
• Quantum Assisted Simulator
• Does provable absence of barren plateaus imply classical simulability?
• Barren plateaus in quantum tensor network optimization
• Prospects of Quantum Computing for Molecular Sciences
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Experimental quantum computational chemistry with optimised unitary coupled cluster ansatz
• Feedback-based quantum optimization
• Iterative Quantum Assisted Eigensolver
• Constrained mixers for the quantum approximate optimization algorithm
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• KANQAS: Kolmogorov-Arnold Network for Quantum Architecture Search
• Can Error Mitigation Improve Trainability of Noisy Variational Quantum Algorithms?
• Quantum approximate optimization via learning-based adaptive optimization
• Quantum Algorithm for Fidelity Estimation
• Towards large-scale quantum optimization solvers with few qubits
• Mitigating Barren Plateaus with Transfer-learning-inspired Parameter Initializations
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Quantum-Informed Recursive Optimization Algorithms
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• High-fidelity realization of the AKLT state on a NISQ-era quantum processor
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• Trainability Enhancement of Parameterized Quantum Circuits via Reduced-Domain Parameter Initialization
• Quantum Computing for Fusion Energy Science Applications
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Generalized Quantum Assisted Simulator
• Quantum Deep Reinforcement Learning for Robot Navigation Tasks
• Noisy intermediate-scale quantum algorithm for semidefinite programming
• Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits
• Fock State-enhanced Expressivity of Quantum Machine Learning Models
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Quantum Mixed State Compiling
• Variational thermal quantum simulation of the lattice Schwinger model
• Fourier expansion in variational quantum algorithms
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Variational quantum simulation: a case study for understanding warm starts
• Training variational quantum circuits with CoVaR: covariance root finding with classical shadows
• Reinforcement Learning Assisted Recursive QAOA
• Efficient variational synthesis of quantum circuits with coherent multi-start optimization
• Effects of noise on the overparametrization of quantum neural networks
• An evolving objective function for improved variational quantum optimisation
• One-particle Green's functions from the quantum equation of motion algorithm
• Training variational quantum algorithms with random gate activation
• Quantum simulation of molecules in solution
• Neural network encoded variational quantum algorithms
• Efficient estimation of trainability for variational quantum circuits
• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• Stochastic noise can be helpful for variational quantum algorithms
• Using Differential Evolution to avoid local minima in Variational Quantum Algorithms
• Lie-algebraic classical simulations for quantum computing
• Isometric tensor network optimization for extensive Hamiltonians is free of barren plateaus
• Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
• Here comes the SU(N): multivariate quantum gates and gradients
• Quantum Receiver Enhanced by Adaptive Learning
• Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Doped stabilizer states in many-body physics and where to find them
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Testing symmetry on quantum computers
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Large-scale quantum hybrid solution for linear systems of equations
• Guaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGrouping
• Double-bracket quantum algorithms for diagonalization
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Natural parameterized quantum circuit
• EHA: Entanglement-variational Hardware-efficient Ansatz for Eigensolvers
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Randomized adaptive quantum state preparation
• Boundary Treatment for Variational Quantum Simulations of Partial Differential Equations on Quantum Computers
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Sampling Error Analysis in Quantum Krylov Subspace Diagonalization
• Variational quantum eigensolver with linear depth problem-inspired ansatz for solving portfolio optimization in finance
• Dissipative variational quantum algorithms for Gibbs state preparation
• Impact of the form of weighted networks on the quantum extreme reservoir computation
• Expressivity of Variational Quantum Machine Learning on the Boolean Cube
• Beyond MP2 initialization for unitary coupled cluster quantum circuits
• Coarse grained intermolecular interactions on quantum processors
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
• Trainability Barriers in Low-Depth QAOA Landscapes
• Large-scale simulations of Floquet physics on near-term quantum computers
• Resource frugal optimizer for quantum machine learning
• Fast-forwarding quantum simulation with real-time quantum Krylov subspace algorithms
• Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey
• Quantum Eigenvector Continuation for Chemistry Applications
• Convex Optimization for Nonequilibrium Steady States on a Hybrid Quantum Processor
• Faster variational quantum algorithms with quantum kernel-based surrogate models
• Toward hybrid quantum simulations with qubits and qumodes on trapped-ion platforms
• Towards Efficient Quantum Computing for Quantum Chemistry: Reducing Circuit Complexity with Transcorrelated and Adaptive Ansatz Techniques
• Protocols for Trainable and Differentiable Quantum Generative Modelling
• Barren plateaus are swamped with traps
• Workflow for practical quantum chemical calculations with quantum phase estimation algorithm: electronic ground and π-π* excited states of benzene and its derivatives†
• Improved iterative quantum algorithm for ground-state preparation
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Variational quantum computing for quantum simulation: principles, implementations, and challenges
• Hybrid quantum-classical algorithm for the transverse-field Ising model in the thermodynamic limit
• Applicability of Measurement-based Quantum Computation towards Physically-driven Variational Quantum Eigensolver
• Experimental quantum natural gradient optimization in photonics
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• State preparation of lattice field theories using quantum optimal control
• Genuine Multipartite Entanglement in Quantum Optimization
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Gradients and frequency profiles of quantum re-uploading models
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing
• Fast gradient-free optimization of excitations in variational quantum eigensolvers
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Diagrammatic Analysis for Parameterized Quantum Circuits
• Efficient and quantum-adaptive machine learning with fermion neural networks
• Efficient ground-state energy estimation and certification on early fault-tolerant quantum computers
• Many bounded versions of undecidable problems are NP-hard
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Efficient Quantum Circuits based on the Quantum Natural Gradient
• Quantum techniques for eigenvalue problems
• Exploring Ground States of Fermi-Hubbard Model on Honeycomb Lattices with Counterdiabaticity
• On the Baltimore Light RailLink into the quantum future
• Shallow quantum circuits for efficient preparation of Slater determinants and correlated states on a quantum computer
• Quantum computing quantum Monte Carlo algorithm
• Quantum Computing for Data Centric Engineering and Science
• Iterative Quantum Optimization with Adaptive Problem Hamiltonian
• Limitations of variational quantum algorithms: a quantum optimal transport approach
• Quantum Circuit Design using a Progressive Widening Enhanced Monte Carlo Tree Search
• Energy Landscape Plummeting in Variational Quantum Eigensolver: Subspace Optimization, Non-iterative Corrections and Generator-informed Initialization for Improved Quantum Efficiency
• Photonic variational quantum eigensolver using entanglement measurements
• Noise-aware variational eigensolvers: a dissipative route for lattice gauge theories
• The 7 faces of quantum NP
• Quantum mean value approximator for hard integer value problems
• Efficient Quantum Cooling Algorithm for Fermionic Systems
• Variational Quantum Simulation of Valence-Bond Solids
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• Information scrambling and entanglement in quantum approximate optimization algorithm circuits
• Perturbative gadgets for gate-based quantum computing: Non-recursive constructions without subspace restrictions
• Deep Unfolded Local Quantum Annealing
• Variational post-selection for ground states and thermal states simulation
• Simulation of open quantum systems on universal quantum computers
• Efficient preparation of the AKLT State with Measurement-based Imaginary Time Evolution
• Estimating many properties of a quantum state via quantum reservoir processing
• Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
• Universal Resources for QAOA and Quantum Annealing
• Parent Hamiltonian as a benchmark problem for variational quantum eigensolvers
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• Exploring nontrivial topology at quantum criticality in a superconducting processor
• Addition and Differentiation of ZX-diagrams
• Optimization via Quantum Preconditioning
• Adiabatic quantum computing with parameterized quantum circuits
• Regularizing quantum loss landscapes by noise injection
• Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes
• Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
• Quantum Curriculum Learning
• Q-Profile: Profiling Tool for Quantum Control Stacks applied to the Quantum Approximate Optimization Algorithm
• The Levy-Lieb embedding of density functional theory and its Quantum Kernel: Illustration for the Hubbard Dimer using near-term quantum algorithms
• Mitigating the measurement overhead of ADAPT-VQE with optimised informationally complete generalised measurements
• Learning quantum symmetries with interactive quantum-classical variational algorithms
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Batched Line Search Strategy for Navigating through Barren Plateaus in Quantum Circuit Training
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem
• Efficient Estimation and Sequential Optimization of Cost Functions in Variational Quantum Algorithms
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Quantum natural gradient with thermal-state initialization
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Block Lanczos method for excited states on a quantum computer
• Generative flow-based warm start of the variational quantum eigensolver
• The Dual Role of Low-Weight Pauli Propagation: A Flawed Simulator but a Powerful Initializer for Variational Quantum Algorithms
• From barren plateaus through fertile valleys: Conic extensions of parameterised quantum circuits
• Counting with the quantum alternating operator ansatz
• Qubit-efficient quantum combinatorial optimization solver
• Shot-Efficient ADAPT-VQE via Reused Pauli Measurements and Variance-Based Shot Allocation
• Ancillary entangling Floquet kicks for accelerating quantum algorithms
• Decoded Quantum Interferometry Under Noise
• Quantum approximate optimization of finite-state bosonic systems
• Pulse engineering via projection of response functions
• Feedback-Based Quantum Control for Safe and Synergistic Drug Combination Design
• Interpolation-based coordinate descent method for parameterized quantum circuits
• Schmidt quantum compressor
• A loop Quantum Approximate Optimization Algorithm with Hamiltonian updating
• Quantum Compressive Sensing: Mathematical Machinery, Quantum Algorithms, and Quantum Circuitry
• Toward Density Functional Theory on Quantum Computers?
• Variational Quantum Subspace Construction via Symmetry-Preserving Cost Functions
• From Hope to Heuristic: Realistic Runtime Estimates for Quantum Optimisation in NHEP
• Double-bracket quantum algorithms for high-fidelity ground state preparation
• A variational quantum eigensolver tailored to multi-band tight-binding simulations of electronic structures