文章基本信息

标题：Quantum-Inspired Classical Algorithms for Singular Value Transformation
本地全文：下载
作者：Dhawal Jethwani ; Fran{\c{c}}ois Le Gall ; Sanjay K. Singh 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：53:1-53:14
DOI：10.4230/LIPIcs.MFCS.2020.53
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 (STOC 2019).
关键词：Sampling algorithms; quantum-inspired algorithms; linear algebra