Information-theoretic bounds on quantum advantage in machine learning

Abstract

We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter $x$ and involve execution of a (possibly unknown) quantum process $\mathcal{E}$. Our figure of merit is the number of runs of $\mathcal{E}$ required to achieve a desired prediction performance. We consider classical ML models that perform a measurement and record the classical outcome after each run of $\mathcal{E}$, and quantum ML models that can access $\mathcal{E}$ coherently to acquire quantum data; the classical or quantum data is then used to predict outcomes of future experiments. We prove that for any input distribution $\mathcal{D}(x)$, a classical ML model can provide accurate predictions on average by accessing $\mathcal{E}$ a number of times comparable to the optimal quantum ML model. In contrast, for achieving accurate prediction on all inputs, we prove that exponential quantum advantage is possible. For example, to predict expectations of all Pauli observables in an $n$-qubit system $\rho$, classical ML models require $2^{\Omega (n)}$ copies of $\rho$, but we present a quantum ML model using only $\mathcal{O}(n)$ copies. Our results clarify where quantum advantage is possible and highlight the potential for classical ML models to address challenging quantum problems in physics and chemistry.

arXiv comment6 pages, 2 figures + 28-page appendix

References in corpus (45)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• A variational eigenvalue solver on a quantum processor
• Neural Message Passing for Quantum Chemistry
• Quantum algorithm for solving linear systems of equations
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Probing many-body dynamics on a 51-atom quantum simulator
• Supervised learning with quantum enhanced feature spaces
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Quantum support vector machine for big data classification
• Quantum machine learning in feature Hilbert spaces
• Quantum Convolutional Neural Networks
• Machine learning phases of matter
• Quantum principal component analysis
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Learning phase transitions by confusion
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Quantum Data Fitting
• Quantum algorithms for supervised and unsupervised machine learning
• High-fidelity control and entanglement of Rydberg atom qubits
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Mixed-state entanglement from local randomized measurements
• Active learning machine learns to create new quantum experiments
• Measurement Optimization in the Variational Quantum Eigensolver Using a Minimum Clique Cover
• Deep autoregressive models for the efficient variational simulation of many-body quantum systems
• Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers
• Virtual Distillation for Quantum Error Mitigation
• Efficient quantum measurement of Pauli operators in the presence of finite sampling error
• Quantum-inspired algorithms in practice
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Quantum Algorithmic Measurement
• Experimental Estimation of Quantum State Properties from Classical Shadows
• On the Quantum versus Classical Learnability of Discrete Distributions
• Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets
• Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning
• Near-term quantum algorithms for linear systems of equations
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions
• A Survey of Quantum Property Testing
• An approximate description of quantum states
• Optimal Quantum Sample Complexity of Learning Algorithms
• Quantum statistical query learning
• Fast graph operations in quantum computation
• Binary Classification with Classical Instances and Quantum Labels
• Learnability and Complexity of Quantum Samples

Cited by in corpus (130)

• Power of data in quantum machine learning
• Challenges and Opportunities in Quantum Machine Learning
• Quantum advantage in learning from experiments
• Generalization in quantum machine learning from few training data
• Provably efficient machine learning for quantum many-body problems
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Quantum machine learning beyond kernel methods
• Efficient estimation of Pauli observables by derandomization
• Generalization in Quantum Machine Learning: a Quantum Information Perspective
• Efficient measure for the expressivity of variational quantum algorithms
• Quantum computing models for artificial neural networks
• Exact emergent quantum state designs from quantum chaotic dynamics
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Quantum Algorithmic Measurement
• Recent advances for quantum classifiers
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Dynamical purification and the emergence of quantum state designs from the projected ensemble
• Does provable absence of barren plateaus imply classical simulability?
• Representation Learning via Quantum Neural Tangent Kernels
• Out-of-distribution generalization for learning quantum dynamics
• NISQ Computers: A Path to Quantum Supremacy
• Experimental quantum state measurement with classical shadows
• Subtleties in the trainability of quantum machine learning models
• Quantum advantages for Pauli channel estimation
• Analytic theory for the dynamics of wide quantum neural networks
• Generalization despite overfitting in quantum machine learning models
• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ansätze
• Variational inference with a quantum computer
• Deep quantum neural networks equipped with backpropagation on a superconducting processor
• Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
• Generative Quantum Learning of Joint Probability Distribution Functions
• Robustness Verification of Quantum Classifiers
• Improved machine learning algorithm for predicting ground state properties
• Quantum Phase Recognition via Quantum Kernel Methods
• Quantum-Noise-Driven Generative Diffusion Models
• Structural risk minimization for quantum linear classifiers
• Exponential data encoding for quantum supervised learning
• Learning quantum states and unitaries of bounded gate complexity
• Entanglement entropy production in Quantum Neural Networks
• Entangled Datasets for Quantum Machine Learning
• Energy-Consumption Advantage of Quantum Computation
• Quantum kernels to learn the phases of quantum matter
• Bell sampling from quantum circuits
• On the Sample Complexity of Quantum Boltzmann Machine Learning
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Usefulness of adaptive strategies in asymptotic quantum channel discrimination
• Improved Stabilizer Estimation via Bell Difference Sampling
• Dequantizing quantum machine learning models using tensor networks
• Transition Role of Entangled Data in Quantum Machine Learning
• Accelerated variational quantum eigensolver with joint Bell measurement
• Entanglement-enabled advantage for learning a bosonic random displacement channel
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Triply efficient shadow tomography
• What the foundations of quantum computer science teach us about chemistry
• Playing Atari with Hybrid Quantum-Classical Reinforcement Learning
• Statistical Complexity of Quantum Learning
• What can we learn from quantum convolutional neural networks?
• Filtering crosstalk from bath non-Markovianity via spacetime classical shadows
• Quantum Continual Learning Overcoming Catastrophic Forgetting
• Tight bounds on Pauli channel learning without entanglement
• Quantum advantage for noisy channel discrimination
• Optimizing Quantum Convolutional Neural Network Architectures for Arbitrary Data Dimension
• Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
• Implementation of quantum stochastic walks for function approximation, two-dimensional data classification, and sequence classification
• Optimising quantum tomography via shadow inversion
• Qudit Machine Learning
• Generalizing measurement-induced phase transitions to information exchange symmetry breaking
• Operational Quantum Average-Case Distances
• On Classical and Hybrid Shadows of Quantum States
• Quantum Cross Entropy and Maximum Likelihood Principle
• Entanglement transitions induced by quantum-data collection
• The dilemma of quantum neural networks
• Efficient distributed inner product estimation via Pauli sampling
• Protect Measurement-Induced Phase Transition from Noise
• The power and limitations of learning quantum dynamics incoherently
• Quantum learning advantage on a scalable photonic platform
• Digital-analog quantum learning on Rydberg atom arrays
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Efficient Learning of Continuous-Variable Quantum States
• Entanglement engineering of optomechanical systems by reinforcement learning
• Secure Quantum Pattern Communication
• Rademacher complexity of noisy quantum circuits
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Efficient and quantum-adaptive machine learning with fermion neural networks
• Operational interpretation of the Stabilizer Entropy
• Exponential learning advantages with conjugate states and minimal quantum memory
• Optimisation-free Classification and Density Estimation with Quantum Circuits
• Quantum Communication Networks Enhanced by Distributed Quantum Memories
• A Hierarchy for Replica Quantum Advantage
• The Inductive Bias of Quantum Kernels
• Toward Instance-Optimal State Certification With Incoherent Measurements
• A survey of universal quantum von Neumann architecture
• Observing Schrödinger's Cat with Artificial Intelligence: Emergent Classicality from Information Bottleneck
• Lower Bounds for Learning Quantum States with Single-Copy Measurements
• Classical shadows meet quantum optimal mass transport
• The Quantum Density Matrix and its many uses: From quantum structure to quantum chaos and noisy simulators
• Quantum Neural Networks in Practice: A Comparative Study with Classical Models from Standard Data Sets to Industrial Images
• Resource-Efficient Cross-Platform Verification with Modular Superconducting Devices
• Coherent Information Phase Transition in a Noisy Quantum Circuit
• Learning Quantum Processes with Quantum Statistical Queries
• Noise tailoring for Robust Amplitude Estimation
• Nearly query-optimal classical shadow estimation of unitary channels
• Monte Carlo Simulation of Operator Dynamics and Entanglement in Dual-Unitary Circuits
• Quantum circuit-like learning: A fast and scalable classical machine-learning algorithm with similar performance to quantum circuit learning
• Accelerating variational quantum algorithms with multiple quantum processors
• A family of quantum von Neumann architecture
• Experimental simulation of quantum superchannels
• Block Lanczos method for excited states on a quantum computer
• Quantum neural network autoencoder and classifier applied to an industrial case study
• Quantum fidelity kernel with a trapped-ion simulation platform
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Experimental measurement and a physical interpretation of quantum shadow enumerators
• Double descent in quantum kernel methods
• Harnessing Quantum Dynamics for Robust and Scalable Quantum Extreme Learning Machines
• Single-Qudit Quantum Neural Networks for Multiclass Classification
• Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
• Quantum Advantage in Storage and Retrieval of Isometry Channels
• Unsupervised Learning of Symmetry Protected Topological Phase Transitions
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond
• Faster Quantum Algorithm for Multiple Observables Estimation in Fermionic Problems
• Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation
• On the Fundamental Resource for Exponential Advantage in Quantum Channel Learning
• Optimal estimation of three parallel spins with genuine and restricted collective measurements
• Learning complexity gradually in quantum machine learning models
• Quantum Machine Learning with SQUID
• On the query complexity of unitary channel certification
• One, Two, Three: One empirical evaluation of a two-copy shadow tomography scheme with triple efficiency
• Measuring Incompatible Observables with Quantum Neural Networks
• Quantum phase classification via partial tomography-based quantum hypothesis testing
• Bell sampling in Quantum Monte Carlo simulations