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.

8+4 pages, 1 Figure

Cited by in corpus (209)

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