Fetching the paper…
Reading the bibliography…
Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been "dequantized" in the past few years.
The variation of the spectrum of a normal matrix
Alan J. Hoffman and Helmut W. Wielandt · 1953
Earlier work this paper cites.
Non-Uniform Random Variate Generation
Luc Devroye · 1986
Earlier work this paper cites.
Random generation of combinatorial structures from a uniform distribution
Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani · 1986
Earlier work this paper cites.
On the method of bounded differences
Colin McDiarmid · 1989
Earlier work this paper cites.
Fast Monte-Carlo algorithms for approximate matrix multiplication
Petros Drineas and Ravi Kannan · 2001
Earlier work this paper cites.
Clustering large graphs via the singular value decomposition
Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, and V. Vinay · 2004
Earlier work this paper cites.
Fast Monte-Carlo algorithms for finding low-rank approximations
Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala · 2004
Earlier work this paper cites.
Fast Monte Carlo algorithms for matrices I: approximating matrix multiplication
Petros Drineas, Ravi Kannan, and Michael W. Mahoney · 2006
Earlier work this paper cites.
Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix
Petros Drineas, Ravi Kannan, and Michael W. Mahoney · 2006
Earlier work this paper cites.
Fast Monte Carlo algorithms for matrices III: computing a compressed approximate matrix decomposition
Petros Drineas, Ravi Kannan, and Michael W. Mahoney · 2006
Earlier work this paper cites.
Quantum algorithm for linear systems of equations
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd · 2009
Earlier work this paper cites.
Spectral algorithms
Ravi Kannan and Santosh S. Vempala · 2009
Earlier work this paper cites.
Perturbations of functions of diagonalizable matrices
Michael I. Gil · 2010
Earlier work this paper cites.
Quantum algorithm for data fitting
Nathan Wiebe, Daniel Braun, and Seth Lloyd · 2012
Earlier work this paper cites.
Quantum algorithms for supervised and unsupervised machine learning
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost · 2013
Cited alongside, same era.
Quantum principal component analysis
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost · 2014
Cited alongside, same era.
Quantum support vector machine for big data classification
Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd · 2014
Cited alongside, same era.
Read the fine print
Scott Aaronson · 2015
Cited alongside, same era.
Quantum discriminant analysis for dimensionality reduction and classification
Iris Cong and Luming Duan · 2016
Cited alongside, same era.
Randomized algorithms in numerical linear algebra
Ravindran Kannan and Santosh S. Vempala · 2017
Cited alongside, same era.
Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension
Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang · 2020
Later among the works it cites.
Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming
Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang · 2020
Later among the works it cites.
Quantum-inspired algorithm for general minimum conical hull problems
Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao · 2020
Later among the works it cites.
Quantum-inspired classical algorithms for singular value transformation
Dhawal Jethwani, François Le Gall, and Sanjay K. Singh · 2020
Later among the works it cites.
Revisiting dequantization and quantum advantage in learning tasks
Jordan Cotler, Hsin-Yuan Huang, and Jarrod R. McClean · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quantum recommendation systems
Iordanis Kerenidis and Anupam Prakash · 2017
Cited alongside, same era.
Fast quantum algorithms for least squares regression and statistic leverage scores
Yang Liu and Shengyu Zhang · 2017
Cited alongside, same era.
Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
András Gilyén, Seth Lloyd, and Ewin Tang · 2018
Cited alongside, same era.
Quantum Hopfield neural network
Patrick Rebentrost, Thomas R. Bromley, Christian Weedbrook, and Seth Lloyd · 2018
Cited alongside, same era.
Quantum singular-value decomposition of nonsparse low-rank matrices
Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd · 2018
Cited alongside, same era.
A quantum-inspired classical algorithm for separable non-negative matrix factorization
Zhihuai Chen, Yinan Li, Xiaoming Sun, Pei Yuan, and Jialin Zhang · 2019
Cited alongside, same era.
Grand unification of quantum algorithms
John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang · 2021
Later among the works it cites.
Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
Ewin Tang · 2021
Later among the works it cites.
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang · 2022
Later among the works it cites.
Quantum-inspired support vector machine
Chen Ding, Tian-Yi Bao, and He-Liang Huang · 2022
Later among the works it cites.
Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum PCP conjecture
Sevag Gharibian and François Le Gall · 2022
Later among the works it cites.
An improved quantum-inspired algorithm for linear regression
András Gilyén, Zhao Song, and Ewin Tang · 2022
Later among the works it cites.
Faster quantum-inspired algorithms for solving linear systems
Changpeng Shao and Ashley Montanaro · 2022
Later among the works it cites.
An improved classical singular value transformation for quantum machine learning
Ainesh Bakshi and Ewin Tang · 2024
Closest in time.