Does provable absence of barren plateaus imply classical simulability?

Abstract

A large amount of effort has recently been put into understanding the barren plateau phenomenon. In this perspective article, we face the increasingly loud elephant in the room and ask a question that has been hinted at by many but not explicitly addressed: Can the structure that allows one to avoid barren plateaus also be leveraged to efficiently simulate the loss classically? We collect evidence-on a case-by-case basis-that many commonly used models whose loss landscapes avoid barren plateaus can also admit classical simulation, provided that one can collect some classical data from quantum devices during an initial data acquisition phase. This follows from the observation that barren plateaus result from a curse of dimensionality, and that current approaches for solving them end up encoding the problem into some small, classically simulable, subspaces. Thus, while stressing that quantum computers can be essential for collecting data, our analysis sheds doubt on the information processing capabilities of many parametrized quantum circuits with provably barren plateau-free landscapes. We end by discussing the (many) caveats in our arguments including the limitations of average case arguments, the role of smart initializations, models that fall outside our assumptions, the potential for provably superpolynomial advantages and the possibility that, once larger devices become available, parametrized quantum circuits could heuristically outperform our analytic expectations.

15+22 pages, 5+2 figures, 2 tables, updated to published version

References in corpus (91)

• Variational Quantum Algorithms
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Noisy intermediate-scale quantum (NISQ) algorithms
• An introduction to quantum machine learning
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Matrix product states represent ground states faithfully
• Challenges and Opportunities in Quantum Machine Learning
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Hybrid quantum-classical algorithms and quantum error mitigation
• Generalization in quantum machine learning from few training data
• Training variational quantum algorithms is NP-hard
• Quantum convolutional neural network for classical data classification
• The randomized measurement toolbox
• Minimally Entangled Typical Thermal State Algorithms
• Quantum Computation of Electronic Transitions using a Variational Quantum Eigensolver
• Information-theoretic bounds on quantum advantage in machine learning
• Permutationally invariant quantum tomography
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Matchgates and classical simulation of quantum circuits
• Exploiting symmetry in variational quantum machine learning
• Trainability of Dissipative Perceptron-Based Quantum Neural Networks
• Group-Invariant Quantum Machine Learning
• Equivalence of quantum barren plateaus to cost concentration and narrow gorges
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• Entanglement Devised Barren Plateau Mitigation
• Barren plateaus preclude learning scramblers
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Higher Order Derivatives of Quantum Neural Networks with Barren Plateaus
• On barren plateaus and cost function locality in variational quantum algorithms
• Theory for Equivariant Quantum Neural Networks
• Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• ADAPT-VQE is insensitive to rough parameter landscapes and barren plateaus
• Variational Quantum Algorithm for Estimating the Quantum Fisher Information
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Matchgate Shadows for Fermionic Quantum Simulation
• Barren plateaus in quantum tensor network optimization
• A polynomial-time classical algorithm for noisy random circuit sampling
• Analyzing the barren plateau phenomenon in training quantum neural networks with the ZX-calculus
• Understanding quantum machine learning also requires rethinking generalization
• On the practical usefulness of the Hardware Efficient Ansatz
• Hamiltonian variational ansatz without barren plateaus
• Shadows of quantum machine learning
• Variational Quantum Eigensolver for Frustrated Quantum Systems
• 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
• Classical surrogates for quantum learning models
• The Presence and Absence of Barren Plateaus in Tensor-network Based Machine Learning
• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ansätze
• Progress toward favorable landscapes in quantum combinatorial optimization
• Trainability barriers and opportunities in quantum generative modeling
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Provably Trainable Rotationally Equivariant Quantum Machine Learning
• Model-Independent Learning of Quantum Phases of Matter with Quantum Convolutional Neural Networks
• Trainability Enhancement of Parameterized Quantum Circuits via Reduced-Domain Parameter Initialization
• Interpretable Quantum Advantage in Neural Sequence Learning
• Non-trivial symmetries in quantum landscapes and their resilience to quantum noise
• Quantum Deep Hedging
• Efficient classical algorithms for simulating symmetric quantum systems
• Solvable non-Hermitian skin effect in many-body unitary dynamics
• Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Classification of dynamical Lie algebras for translation-invariant 2-local spin systems in one dimension
• 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
• Engineered dissipation to mitigate barren plateaus
• Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits
• Inference-Based Quantum Sensing
• Dequantizing quantum machine learning models using tensor networks
• Classical simulation of non-Gaussian fermionic circuits
• Isometric tensor network optimization for extensive Hamiltonians is free of barren plateaus
• Potential and limitations of random Fourier features for dequantizing quantum machine learning
• Quantum neural networks form Gaussian processes
• Computing exact moments of local random quantum circuits via tensor networks
• The quantum cost function concentration dependency on the parametrization expressivity
• The Unified Effect of Data Encoding, Ansatz Expressibility and Entanglement on the Trainability of HQNNs
• What can we learn from quantum convolutional neural networks?
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• Trainability and Expressivity of Hamming-Weight Preserving Quantum Circuits for Machine Learning
• F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits
• Convergence and Quantum Advantage of Trotterized MERA for Strongly-Correlated Systems
• Classically Approximating Variational Quantum Machine Learning with Random Fourier Features
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Arbitrary Polynomial Separations in Trainable Quantum Machine Learning
• Dynamic parameterized quantum circuits: expressive and barren-plateau free
• Simulation of Fermionic circuits using Majorana Propagation

Cited by in corpus (49)

• Classically estimating observables of noiseless quantum circuits
• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• Lie-algebraic classical simulations for quantum computing
• A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits
• Constrained and Vanishing Expressivity of Quantum Fourier Models
• Noise-induced shallow circuits and absence of barren plateaus
• Variational quantum computing for quantum simulation: principles, implementations, and challenges
• Adversarial Robustness Guarantees for Quantum Classifiers
• The power and limitations of learning quantum dynamics incoherently
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Parallel-in-time quantum simulation via Page and Wootters quantum time
• Ground state-based quantum feature maps
• Architectures and random properties of symplectic quantum circuits
• Dual-VQE: A quantum algorithm to lower bound the ground-state energy
• Double-bracket algorithm for quantum signal processing without post-selection
• Regularizing quantum loss landscapes by noise injection
• Quantum Curriculum Learning
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Towards Improved Quantum Machine Learning for Molecular Force Fields
• Preparation Circuits for Matrix Product States by Classical Variational Disentanglement
• Engineering the uncontrollable: Steering noisy spin-correlated radical-pairs with coherent and incoherent control
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Optimal quantum reservoir learning in proximity to universality
• When Quantum and Classical Models Disagree: Learning Beyond Minimum Norm Least Square
• Integrated Encoding and Quantization to Enhance Quanvolutional Neural Networks
• Estimates of loss function concentration in noisy parametrized quantum circuits
• Generative flow-based warm start of the variational quantum eigensolver
• Accelerating Quantum Eigensolver Algorithms With Machine Learning
• Exploiting many-body localization for scalable variational quantum simulation
• On the Hardness of Measuring Magic
• Equivalence between exponential concentration in quantum machine learning kernels and barren plateaus in variational algorithms
• Dynamic LOCC Circuits for Automated Entanglement Manipulation
• Towards Compact Wavefunctions from Quantum-Selected Configuration Interaction
• Decoded Quantum Interferometry Under Noise
• Efficient classical computation of the neural tangent kernel of quantum neural networks
• Gradient Scalability and Taylor Surrogation of Quantum Cost Landscapes
• Vortex Detection from Quantum Data
• Direct Gradient Computation for Barren Plateaus in Parameterized Quantum Circuits
• Quantum phase classification via partial tomography-based quantum hypothesis testing
• LArTPC hit-based topology classification with quantum machine learning and symmetry
• Quantum Encoding of Structured Data with Matrix Product States
• A graph-theoretic approach to chaos and complexity in quantum systems
• Performance Guarantees for Quantum Neural Estimation of Entropies
• Double-bracket quantum algorithms for high-fidelity ground state preparation