Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension

Abstract

We construct an efficient classical analogue of the quantum matrix inversion algorithm (HHL) for low-rank matrices. Inspired by recent work of Tang, assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix and sample from the solution to the problem $Ax=b$ using fast sampling techniques. We implement the pseudo-inverse by finding an approximate singular value decomposition of $A$ via subsampling, then inverting the singular values. In principle, the approach can also be used to apply any desired "smooth" function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem, our result suggests that more low-rank quantum algorithms can be effectively "dequantised" into classical length-square sampling algorithms.

arXiv comment10 pages

Cited by in corpus (34)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Information-theoretic bounds on quantum advantage in machine learning
• Quantum-Inspired Support Vector Machine
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Quantum-inspired algorithms in practice
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• q-means: A quantum algorithm for unsupervised machine learning
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Prospects and challenges of quantum finance
• Quantum Algorithm for Fidelity Estimation
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Quantum Differentially Private Sparse Regression Learning
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• Fast Quantum Algorithms for Trace Distance Estimation
• Quantum Language Processing
• Quantum-enhanced least-square support vector machine: simplified quantum algorithm and sparse solutions
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test
• Quantum-Inspired Classical Algorithms for Singular Value Transformation
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Quantum algorithms for hedging and the learning of Ising models
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• Quantum Semi-Supervised Kernel Learning
• Quantum-inspired canonical correlation analysis for exponentially large dimensional data
• An HHL-Based Algorithm for Computing Hitting Probabilities of Quantum Random Walks
• The topology of data hides in quantum thermal states
• Supercomputer simulations of transmon quantum computers
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• A quantum-inspired algorithm for approximating statistical leverage scores
• Quantum-Inspired Classical Algorithm for Slow Feature Analysis
• Revisiting dequantization and quantum advantage in learning tasks
• Quantum Machine Learning For Classical Data
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks