Quantum-Inspired Classical Algorithms for Singular Value Transformation
arXiv:1910.05699 · doi:10.4230/LIPIcs.MFCS.2020.53
Abstract
A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC19).
arXiv comment19 pages
References in corpus (10)
- Quantum algorithm for solving linear systems of equations
- Quantum support vector machine for big data classification
- Quantum principal component analysis
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Preconditioned quantum linear system algorithm
- A quantum linear system algorithm for dense matrices
- Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
- Quantum-inspired algorithms in practice
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension