A rigorous and robust quantum speed-up in supervised machine learning

Abstract

Over the past few years several quantum machine learning algorithms were proposed that promise quantum speed-ups over their classical counterparts. Most of these learning algorithms either assume quantum access to data -- making it unclear if quantum speed-ups still exist without making these strong assumptions, or are heuristic in nature with no provable advantage over classical algorithms. In this paper, we establish a rigorous quantum speed-up for supervised classification using a general-purpose quantum learning algorithm that only requires classical access to data. Our quantum classifier is a conventional support vector machine that uses a fault-tolerant quantum computer to estimate a kernel function. Data samples are mapped to a quantum feature space and the kernel entries can be estimated as the transition amplitude of a quantum circuit. We construct a family of datasets and show that no classical learner can classify the data inverse-polynomially better than random guessing, assuming the widely-believed hardness of the discrete logarithm problem. Meanwhile, the quantum classifier achieves high accuracy and is robust against additive errors in the kernel entries that arise from finite sampling statistics.

arXiv comment27 pages, 2 figures

References in corpus (25)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Supervised learning with quantum enhanced feature spaces
• Machine learning and the physical sciences
• Quantum support vector machine for big data classification
• Quantum machine learning in feature Hilbert spaces
• Quantum Circuit Learning
• Quantum principal component analysis
• Error mitigation for short-depth quantum circuits
• Circuit-centric quantum classifiers
• Extending the computational reach of a noisy superconducting quantum processor
• Quantum generative adversarial learning
• Quantum Data Fitting
• Quantum machine learning: a classical perspective
• Quantum generative adversarial networks
• Differentiable Learning of Quantum Circuit Born Machine
• A quantum-inspired classical algorithm for recommendation systems
• Quantum-Inspired Support Vector Machine
• Quantum singular value decomposition of non-sparse low-rank matrices
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Quantum assisted Gaussian process regression
• On the Quantum versus Classical Learnability of Discrete Distributions
• Experimental quantum kernel machine learning with nuclear spins in a solid

Cited by in corpus (218)

• Challenges and Opportunities in Quantum Machine Learning
• Generalization in quantum machine learning from few training data
• The Future of Quantum Computing with Superconducting Qubits
• Is quantum advantage the right goal for quantum machine learning?
• Quantum machine learning beyond kernel methods
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Quantum agents in the Gym: a variational quantum algorithm for deep Q-learning
• Quantum Machine Learning for Chemistry and Physics
• Training Quantum Embedding Kernels on Near-Term Quantum Computers
• Experimental quantum adversarial learning with programmable superconducting qubits
• Mixed Quantum-Classical Method For Fraud Detection with Quantum Feature Selection
• Advances of Machine Learning in Materials Science: Ideas and Techniques
• Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines
• Quantum Machine Learning: from physics to software engineering
• Theory for Equivariant Quantum Neural Networks
• Recent advances for quantum classifiers
• Time Series Quantum Reservoir Computing with Weak and Projective Measurements
• Quantum Computing for Molecular Biology
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Biology and medicine in the landscape of quantum advantages
• Universal Approximation Property of Quantum Machine Learning Models in Quantum-Enhanced Feature Spaces
• Application of Quantum Machine Learning using the Quantum Kernel Algorithm on High Energy Physics Analysis at the LHC
• Towards provably efficient quantum algorithms for large-scale machine-learning models
• Towards quantum enhanced adversarial robustness in machine learning
• Representation Learning via Quantum Neural Tangent Kernels
• Understanding quantum machine learning also requires rethinking generalization
• Out-of-distribution generalization for learning quantum dynamics
• NISQ Computers: A Path to Quantum Supremacy
• Quantum Machine Learning Framework for Virtual Screening in Drug Discovery: a Prospective Quantum Advantage
• Hamiltonian variational ansatz without barren plateaus
• Subtleties in the trainability of quantum machine learning models
• Shadows of quantum machine learning
• Machine Learning for Anomaly Detection in Particle Physics
• Importance of Kernel Bandwidth in Quantum Machine Learning
• Covariant quantum kernels for data with group structure
• Enhancing Quantum Support Vector Machines through Variational Kernel Training
• Quantum kernels for real-world predictions based on electronic health records
• The complexity of quantum support vector machines
• Quantum machine learning of large datasets using randomized measurements
• Analytic theory for the dynamics of wide quantum neural networks
• Data compression for quantum machine learning
• Quantum Neural Network Classifiers: A Tutorial
• 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
• Reflection Equivariant Quantum Neural Networks for Enhanced Image Classification
• Deep quantum neural networks equipped with backpropagation on a superconducting processor
• Variational inference with a quantum computer
• Application of quantum machine learning using quantum kernel algorithms on multiclass neuron M type classification
• Generative Quantum Learning of Joint Probability Distribution Functions
• Hybrid quantum ResNet for car classification and its hyperparameter optimization
• Breaking Rate-Distance Limitation of Measurement-Device-Independent Quantum Secret Sharing
• Quantum Kernel Methods under Scrutiny: A Benchmarking Study
• Quantum anomaly detection in the latent space of proton collision events at the LHC
• Imaginary components of out-of-time correlators and information scrambling for navigating the learning landscape of a quantum machine learning model
• Unravelling physics beyond the standard model with classical and quantum anomaly detection
• ResQNets: A Residual Approach for Mitigating Barren Plateaus in Quantum Neural Networks
• Efficient quantum amplitude encoding of polynomial functions
• Quantum Phase Recognition via Quantum Kernel Methods
• Provably Trainable Rotationally Equivariant Quantum Machine Learning
• Quantum Neuronal Sensing of Quantum Many-Body States on a 61-Qubit Programmable Superconducting Processor
• Trainability Enhancement of Parameterized Quantum Circuits via Reduced-Domain Parameter Initialization
• Structural risk minimization for quantum linear classifiers
• Quantum Deep Hedging
• Certified randomness using a trapped-ion quantum processor
• Variational Quantum Approximate Support Vector Machine with Inference Transfer
• Interpretable Quantum Advantage in Neural Sequence Learning
• Quantum Deep Reinforcement Learning for Robot Navigation Tasks
• Fock State-enhanced Expressivity of Quantum Machine Learning Models
• Efficient classical algorithms for simulating symmetric quantum systems
• A single $T$-gate makes distribution learning hard
• Quantum Gaussian Process Regression for Bayesian Optimization
• Scalable Networking of Neutral-Atom Qubits: Nanofiber-Based Approach for Multiprocessor Fault-Tolerant Quantum Computer
• Quantum reservoir computing in finite dimensions
• On fundamental aspects of quantum extreme learning machines
• Single-qubit universal classifier implemented on an ion-trap quantum device
• Parallel Hybrid Networks: an interplay between quantum and classical neural networks
• Variational quantum one-class classifier
• Drastic Circuit Depth Reductions with Preserved Adversarial Robustness by Approximate Encoding for Quantum Machine Learning
• Breaking universal limitations on quantum conference key agreement without quantum memory
• Noisy Quantum Kernel Machines
• The Quantum Path Kernel: a Generalized Quantum Neural Tangent Kernel for Deep Quantum Machine Learning
• Let Quantum Neural Networks Choose Their Own Frequencies
• Provable bounds for noise-free expectation values computed from noisy samples
• Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric
• Resource Saving via Ensemble Techniques for Quantum Neural Networks
• Numerical evidence against advantage with quantum fidelity kernels on classical data
• A Practical Introduction to Benchmarking and Characterization of Quantum Computers
• Quantum AI simulator using a hybrid CPU-FPGA approach
• Explaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning
• Permutation Invariant Encodings for Quantum Machine Learning with Point Cloud Data
• Rapid training of quantum recurrent neural networks
• Data re-uploading with a single qudit
• Optimal quantum dataset for learning a unitary transformation
• Transition Role of Entangled Data in Quantum Machine Learning
• On the expressivity of embedding quantum kernels
• Neural Quantum Embedding: Pushing the Limits of Quantum Supervised Learning
• A super-polynomial quantum-classical separation for density modelling
• Quantum Kernel Alignment with Stochastic Gradient Descent
• Quantivine: A Visualization Approach for Large-scale Quantum Circuit Representation and Analysis
• Quantum Advantage Seeker with Kernels (QuASK): a software framework to speed up the research in quantum machine learning
• Approximately Equivariant Quantum Neural Network for $p4m$ Group Symmetries in Images
• Quantum Continual Learning Overcoming Catastrophic Forgetting
• What can we learn from quantum convolutional neural networks?
• Quantum Vision Transformers for Quark-Gluon Classification
• Loop-Free Tensor Networks for High-Energy Physics
• Neural quantum kernels: training quantum kernels with quantum neural networks
• Boosted Ensembles of Qubit and Continuous Variable Quantum Support Vector Machines for B Meson Flavour Tagging
• Efficient Parameter Optimisation for Quantum Kernel Alignment: A Sub-sampling Approach in Variational Training
• Quantum Gaussian process model of potential energy surface for a polyatomic molecule
• Hyperparameter Importance of Quantum Neural Networks Across Small Datasets
• Automatic and effective discovery of quantum kernels
• Efficient MPS representations and quantum circuits from the Fourier modes of classical image data
• Hybrid quantum learning with data re-uploading on a small-scale superconducting quantum simulator
• The role of data embedding in equivariant quantum convolutional neural networks
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Expressivity of Variational Quantum Machine Learning on the Boolean Cube
• Quantum Fourier Iterative Amplitude Estimation
• Entanglement-induced provable and robust quantum learning advantages
• Quantum Computing for Software Engineering: Prospects
• Direct implementation of a perceptron in superconducting circuit quantum hardware
• Adiabatic quantum algorithm for artificial graphene
• Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey
• Quantum-machine-assisted Drug Discovery
• Laziness, Barren Plateau, and Noise in Machine Learning
• Hybrid Genetic Optimisation for Quantum Feature Map Design
• Guided-SPSA: Simultaneous Perturbation Stochastic Approximation assisted by the Parameter Shift Rule
• Splitting and Parallelizing of Quantum Convolutional Neural Networks for Learning Translationally Symmetric Data
• Faster variational quantum algorithms with quantum kernel-based surrogate models
• Satellite image classification with neural quantum kernels
• Guided Quantum Compression for High Dimensional Data Classification
• Application of quantum computing to a linear non-Gaussian acyclic model for novel medical knowledge discovery
• Representation of the Fermionic Boundary Operator
• Variational Quantum Support Vector Machine based on $\Gamma$ matrix expansion and Variational Universal-Quantum-State Generator
• Digital-analog quantum learning on Rydberg atom arrays
• Parametrized constant-depth quantum neuron
• Adversarial Robustness Guarantees for Quantum Classifiers
• Quantum Natural Policy Gradients: Towards Sample-Efficient Reinforcement Learning
• A quantum computing concept for 1-D elastic wave simulation with exponential speedup
• EP-PQM: Efficient Parametric Probabilistic Quantum Memory with Fewer Qubits and Gates
• Quantum-enhanced neural networks in the neural tangent kernel framework
• Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation
• Quantum Supervised Learning
• Continuous-variable quantum kernel method on a programmable photonic quantum processor
• SnCQA: A hardware-efficient equivariant quantum convolutional circuit architecture
• Quantum continual learning on a programmable superconducting processor
• Detect anomalous quartic gauge couplings at muon colliders with quantum kernel k-means
• Quantum kernel learning Model constructed with small data
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method
• Quantum Kernel Machine Learning With Continuous Variables
• Optimize the event selection strategy to study the anomalous quartic gauge couplings at muon colliders using the support vector machine and quantum support vector machine
• Quantum neural compressive sensing for ghost imaging
• Framework for Learning and Control in the Classical and Quantum Domains
• Efficient and quantum-adaptive machine learning with fermion neural networks
• A Study on Quantum Graph Neural Networks Applied to Molecular Physics
• Quantum density estimation with density matrices: Application to quantum anomaly detection
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Non-Classical Kernels in Continuous Variable Systems
• Robust Quantum Reservoir Computing for Molecular Property Prediction
• Hybrid Quantum Neural Networks with Variational Quantum Regressor for Enhancing QSPR Modeling of CO2-Capturing Amine
• Quantum delegated and federated learning via quantum homomorphic encryption
• Improved resource-tunable near-term quantum algorithms for transition probabilities, with applications in physics and variational quantum linear algebra
• Generative Invertible Quantum Neural Networks
• All you need is spin: SU(2) equivariant variational quantum circuits based on spin networks
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Quantum Kerr Learning
• The Quantum Density Matrix and its many uses: From quantum structure to quantum chaos and noisy simulators
• Experimental benchmarking of quantum state overlap estimation strategies with photonic systems
• QuForge: A Library for Qudits Simulation
• Permutation-equivariant quantum convolutional neural networks
• Supervised Learning Guarantee for Quantum AdaBoost
• The role of coherence theory in attractor quantum neural networks
• Quantum machine learning for multiclass classification beyond kernel methods
• On the similarity of bandwidth-tuned quantum kernels and classical kernels
• Single-shot quantum machine learning
• Encoding-dependent generalization bounds for parametrized quantum circuits
• Joint Wire Cutting with Non-Maximally Entangled States
• Data-Dependent Generalization Bounds for Parameterized Quantum Models Under Noise
• Trained quantum neural networks are Gaussian processes
• Quantum Neural Networks in Practice: A Comparative Study with Classical Models from Standard Data Sets to Industrial Images
• Constructing Local Bases for a Deep Variational Quantum Eigensolver for Molecular Systems
• Quantum enhanced stratification of Breast Cancer: exploring quantum expressivity for real omics data
• Heisenberg-limited adaptive gradient estimation for multiple observables
• VQE-generated quantum circuit dataset for machine learning
• Learning Fourier series with parametrized quantum circuits
• Measurement-based quantum machine learning
• QUACK: Quantum Aligned Centroid Kernel
• Expressivity of deterministic quantum computation with one qubit
• Quantitative convergence of trained quantum neural networks to a Gaussian process
• Typical Machine Learning Datasets as Low-Depth Quantum Circuits
• Quantum State Preparation for Probability Distributions with Reflection Symmetry Using Matrix Product States
• Quantum Curriculum Learning
• High-Accuracy Temporal Prediction via Experimental Quantum Reservoir Computing in Correlated Spins
• Quantum Kernel Methods: Convergence Theory, Separation Bounds and Applications to Marketing Analytics
• Unbounded quantum-classical separation in sample complexity for sphere center finding
• Mitigating exponential concentration in covariant quantum kernels for subspace and real-world data
• Quadratic speed-ups in quantum kernelized binary classification
• Atom Cavity Encoding for NP-Complete Problems
• Guided Graph Compression for Quantum Graph Neural Networks
• Benchmarking of quantum fidelity kernels for Gaussian process regression
• Learning out-of-time-ordered correlators with classical kernel methods
• Learning Reduced Representations for Quantum Classifiers
• Double descent in quantum kernel methods
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Quantum fidelity kernel with a trapped-ion simulation platform
• Harnessing Quantum Dynamics for Robust and Scalable Quantum Extreme Learning Machines
• Empirical Power of Quantum Encoding Methods for Binary Classification
• When Quantum and Classical Models Disagree: Learning Beyond Minimum Norm Least Square
• Quantum feature-map learning with reduced resource overhead
• Noise-Resilient Quantum Reinforcement Learning
• Quantum Algorithms for Causal Estimands
• New perspectives on quantum kernels through the lens of entangled tensor kernels
• Mean-field limit from general mixtures of experts to quantum neural networks
• Quantum Phase Recognition via Quantum Attention Mechanism
• Quantum-Inspired Weight-Constrained Neural Network: Reducing Variable Numbers by 100x Compared to Standard Neural Networks
• Quantum Machine Learning with SQUID
• Learning complexity gradually in quantum machine learning models
• Efficient classical computation of the neural tangent kernel of quantum neural networks