Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
arXiv:1910.06151 · doi:10.1145/3357713.3384314
Abstract
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quantum-inspired algorithm for recommendation systems [STOC'19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén, Su, Low, and Wiebe [STOC'19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all recent results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: -norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.
77 pages, 2 figures. v2: revised to add more connection to QSVT, improve existing results. v3: revised structure, introduction rewritten for clarity. v4: minor correction to regression result
References in corpus (12)
- Quantum algorithm for solving linear systems of equations
- Quantum random access memory
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Sketching as a Tool for Numerical Linear Algebra
- A Grand Unification of Quantum Algorithms
- Information-theoretic bounds on quantum advantage in machine learning
- Creating superpositions that correspond to efficiently integrable probability distributions
- Quantum Algorithmic Measurement
- Towards quantum advantage via topological data analysis
- Approximate Quantum Circuit Synthesis using Block-Encodings
- Quantum-Inspired Classical Algorithms for Singular Value Transformation
- Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions
Cited by in corpus (47)
- Challenges and Opportunities in Quantum Machine Learning
- Quantum advantage in learning from experiments
- A rigorous and robust quantum speed-up in supervised machine learning
- Quantum computing for finance
- Noisy intermediate-scale quantum computers
- A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
- Biology and medicine in the landscape of quantum advantages
- Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
- The complexity of quantum support vector machines
- An improved quantum-inspired algorithm for linear regression
- Towards quantum advantage via topological data analysis
- Variational learning for quantum artificial neural networks
- Quantum algorithm for persistent Betti numbers and topological data analysis
- Grammar-aware sentence classification on quantum computers
- Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle
- A brief introduction to quantum algorithms
- Quantum Gaussian Process Regression for Bayesian Optimization
- Quantum algorithm for Neighborhood Preserving Embedding
- Fast Quantum Algorithms for Trace Distance Estimation
- Quantum Regularized Least Squares
- Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
- Quantum statistical query learning
- Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
- Quantum-Inspired Classical Algorithms for Singular Value Transformation
- Quantum algorithms for SVD-based data representation and analysis
- Quantum algorithms for escaping from saddle points
- Quantum-accessible reinforcement learning beyond strictly epochal environments
- Quantum and Quantum-Inspired Stereographic K Nearest-Neighbour Clustering
- Quantum Semi-Supervised Kernel Learning
- Tight Bound for Estimating Expectation Values from a System of Linear Equations
- Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
- Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
- The topology of data hides in quantum thermal states
- The 7 faces of quantum NP
- Modular quantum signal processing in many variables
- Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
- Quantum-Inspired Classical Algorithm for Principal Component Regression
- A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices
- A quantum-inspired algorithm for approximating statistical leverage scores
- Quantum-Inspired Classical Algorithm for Slow Feature Analysis
- Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
- Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning
- Quantum Machine Learning For Classical Data
- Revisiting dequantization and quantum advantage in learning tasks
- Block Lanczos method for excited states on a quantum computer
- StoqMA meets distribution testing
- Quantum Inspired Adaptive Boosting