Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps

Abstract

One of the most important properties of classical neural networks is how surprisingly trainable they are, though their training algorithms typically rely on optimizing complicated, nonconvex loss functions. Previous results have shown that unlike the case in classical neural networks, variational quantum models are often not trainable. The most studied phenomenon is the onset of barren plateaus in the training landscape of these quantum models, typically when the models are very deep. This focus on barren plateaus has made the phenomenon almost synonymous with the trainability of quantum models. Here, we show that barren plateaus are only a part of the story. We prove that a wide class of variational quantum models -- which are shallow, and exhibit no barren plateaus -- have only a superpolynomially small fraction of local minima within any constant energy from the global minimum, rendering these models untrainable if no good initial guess of the optimal parameters is known. We also study the trainability of variational quantum algorithms from a statistical query framework, and show that noisy optimization of a wide variety of quantum models is impossible with a sub-exponential number of queries. Finally, we numerically confirm our results on a variety of problem instances. Though we exclude a wide variety of quantum algorithms here, we give reason for optimism for certain classes of variational algorithms and discuss potential ways forward in showing the practical utility of such algorithms.

46 pages, 12 figures

References in corpus (31)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• Quantum Circuit Learning
• Quantum Convolutional Neural Networks
• Quantum fingerprinting
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• Power of data in quantum machine learning
• Efficient Learning for Deep Quantum Neural Networks
• Quantum-assisted quantum compiling
• Information-theoretic bounds on quantum advantage in machine learning
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• Effect of barren plateaus on gradient-free optimization
• Theory of overparametrization in quantum neural networks
• Learning a local Hamiltonian from local measurements
• Tomography and Generative Data Modeling via Quantum Boltzmann Training
• Higher Order Derivatives of Quantum Neural Networks with Barren Plateaus
• Sample-efficient learning of quantum many-body systems
• Variational Quantum Boltzmann Machines
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Variational Quantum Singular Value Decomposition
• Learning quantum data with the quantum Earth Mover's distance
• Quantum advantages for Pauli channel estimation
• Analytic theory for the dynamics of wide quantum neural networks
• Universal Effectiveness of High-Depth Circuits in Variational Eigenproblems
• Quantum Energy Landscape and VQA Optimization
• On the Hardness of PAC-learning Stabilizer States with Noise
• Learnability of the output distributions of local quantum circuits

Cited by in corpus (132)

• Barren Plateaus in Variational Quantum Computing
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• Review of Distributed Quantum Computing. From single QPU to High Performance Quantum Computing
• Theory for Equivariant Quantum Neural Networks
• Quantum Vision Transformers
• Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks
• Does provable absence of barren plateaus imply classical simulability?
• Subtleties in the trainability of quantum machine learning models
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• Quantum Machine Learning for Digital Health? A Systematic Review
• Towards large-scale quantum optimization solvers with few qubits
• Artificial Intelligence for Quantum Computing
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Quantifying the effect of gate errors on variational quantum eigensolvers for quantum chemistry
• Trainability Enhancement of Parameterized Quantum Circuits via Reduced-Domain Parameter Initialization
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Interpretable Quantum Advantage in Neural Sequence Learning
• Quantum Deep Reinforcement Learning for Robot Navigation Tasks
• Efficient classical algorithms for simulating symmetric quantum systems
• A single $T$-gate makes distribution learning hard
• Entanglement entropy production in Quantum Neural Networks
• Fourier expansion in variational quantum algorithms
• On the Sample Complexity of Quantum Boltzmann Machine Learning
• Variational quantum simulation: a case study for understanding warm starts
• Retrieving information from a black hole using quantum machine learning
• Learning shallow quantum circuits
• Efficient variational synthesis of quantum circuits with coherent multi-start optimization
• Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits
• Neural network encoded variational quantum algorithms
• Efficient estimation of trainability for variational quantum circuits
• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• Variational Quantum Simulation of Partial Differential Equations: Applications in Colloidal Transport
• Using Differential Evolution to avoid local minima in Variational Quantum Algorithms
• Classical Splitting of Parametrized Quantum Circuits
• Lie-algebraic classical simulations for quantum computing
• Isometric tensor network optimization for extensive Hamiltonians is free of barren plateaus
• Networked Quantum Services
• An exponentially-growing family of universal quantum circuits
• Computing exact moments of local random quantum circuits via tensor networks
• Scalable Quantum Simulations of Scattering in Scalar Field Theory on 120 Qubits
• Symmetry breaking in geometric quantum machine learning in the presence of noise
• Q${}^2$Chemistry: A quantum computation platform for quantum chemistry
• Trainability and Expressivity of Hamming-Weight Preserving Quantum Circuits for Machine Learning
• VQC-Based Reinforcement Learning with Data Re-uploading: Performance and Trainability
• What can we learn from quantum convolutional neural networks?
• EHA: Entanglement-variational Hardware-efficient Ansatz for Eigensolvers
• Dynamic-ADAPT-QAOA: An algorithm with shallow and noise-resilient circuits
• Improving the speed of variational quantum algorithms for quantum error correction
• Algorithmic Shadow Spectroscopy
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Mitigated barren plateaus in the time-nonlocal optimization of analog quantum-algorithm protocols
• Hybrid quantum learning with data re-uploading on a small-scale superconducting quantum simulator
• Beyond MP2 initialization for unitary coupled cluster quantum circuits
• Dissipative variational quantum algorithms for Gibbs state preparation
• Constrained and Vanishing Expressivity of Quantum Fourier Models
• Trainability Barriers in Low-Depth QAOA Landscapes
• Large-scale simulations of Floquet physics on near-term quantum computers
• Energy-dependent barren plateau in bosonic variational quantum circuits
• Quantum Eigenvector Continuation for Chemistry Applications
• Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey
• Satellite image classification with neural quantum kernels
• Resource frugal optimizer for quantum machine learning
• Layering and subpool exploration for adaptive Variational Quantum Eigensolvers: Reducing circuit depth, runtime, and susceptibility to noise
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Splitting and Parallelizing of Quantum Convolutional Neural Networks for Learning Translationally Symmetric Data
• Barren plateaus are swamped with traps
• Image Classification with Rotation-Invariant Variational Quantum Circuits
• Hybrid Ground-State Quantum Algorithms based on Neural Schrödinger Forging
• Variational Quantum Circuit Design for Quantum Reinforcement Learning on Continuous Environments
• Unveiling quantum phase transitions from traps in variational quantum algorithms
• Variational quantum computing for quantum simulation: principles, implementations, and challenges
• Fast gradient-free optimization of excitations in variational quantum eigensolvers
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Practicality of quantum adiabatic algorithm for chemistry applications
• Gradients and frequency profiles of quantum re-uploading models
• The Wasserstein distance of order 1 for quantum spin systems on infinite lattices
• SHARC-VQE: Simplified Hamiltonian Approach with Refinement and Correction enabled Variational Quantum Eigensolver for Molecular Simulation
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• A Quantum Annealing Protocol to Solve the Nuclear Shell Model
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• Random Natural Gradient
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Quantum computing quantum Monte Carlo algorithm
• Energy Landscape Plummeting in Variational Quantum Eigensolver: Subspace Optimization, Non-iterative Corrections and Generator-informed Initialization for Improved Quantum Efficiency
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Deep Circuit Compression for Quantum Dynamics via Tensor Networks
• Backpropagation scaling in parameterised quantum circuits
• Channel Attention for Quantum Convolutional Neural Networks
• Hamiltonian-based graph-state ansatz for variational quantum algorithms
• On the average-case complexity of learning output distributions of quantum circuits
• Supervised Learning Guarantee for Quantum AdaBoost
• Pitfalls when tackling the exponential concentration of parameterized quantum models
• Trained quantum neural networks are Gaussian processes
• Perturbative gadgets for gate-based quantum computing: Non-recursive constructions without subspace restrictions
• Learning Fourier series with parametrized quantum circuits
• Learning quantum states prepared by shallow circuits in polynomial time
• Regularizing quantum loss landscapes by noise injection
• Quantum Curriculum Learning
• Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes
• Exponential distillation of dominant eigenproperties
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
• A Universal Quantum Computer From Relativistic Motion
• Adiabatic quantum computing with parameterized quantum circuits
• Dynamical transition in controllable quantum neural networks with large depth
• Exploiting many-body localization for scalable variational quantum simulation
• Making the cut: two methods for breaking down a quantum algorithm
• A coherent approach to quantum-classical optimization
• 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
• Quantum Glassiness From Efficient Learning
• An Empirical Study of Quantum Dynamics as a Ground State Problem with Neural Quantum States
• 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
• Schmidt quantum compressor
• Trainable Quantum Neural Network for Multiclass Image Classification with the Power of Pre-trained Tree Tensor Networks
• Quantum reservoir computing in Jaynes-Cummings models: Nonlinear memory and time-series prediction
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem
• Learning complexity gradually in quantum machine learning models
• Learning Feedback Mechanisms for Measurement-Based Variational Quantum State Preparation
• Pulse engineering via projection of response functions
• Double-bracket quantum algorithms for high-fidelity ground state preparation
• Learning Variational Quantum Circuit Parameters with Classical Artificial Intelligence for Quantum Phase Transition Detection
• Improving the trainability of VQE on NISQ computers for solving portfolio optimization using convex interpolation
• Variational decision diagrams for quantum-inspired machine learning applications
• Exploiting biased noise in variational quantum models
• Quantum Encoding of Structured Data with Matrix Product States
• Disentangling quantum autoencoder