In terms of quantum algorithms, the first quantum algorithm to solve an \(n \times n\)  sparse linear system was proposed by Harrow, Hassidim, and Lloyd in 2009 (referred to as the HHL algorithm) [1]}. It outputs a quantum state \(|x\rangle \)  proportional to the answer \(x\) , and the running time complexity is \(O\left(({\rm log}\,n)s^2\kappa ^2/\epsilon \right)\) , where \(\kappa \)  is the condition number, \(s\)  is the most non-zero entries in each row of matrix \(A\)  and \(\epsilon \)  is the precision parameter. Compared with any classical version method, the HHL algorithm achieves an exponential speed up by computing the quantum state of the solution. Inspired by the HHL algorithm, a series of logarithmic time quantum algorithms have been proposed to solve various machine learning related problems, such as least square approximation [2]}, [3]}, [4]}, [5]}, [6]}, linear system equations [7]}, [8]}, [9]}, [9]}, [11]}, principal component analysis [12]}, support vector machine [13]}, recommendation systems [14]}, etc [15]}, [16]}, [17]}. Just as the HHL algorithm, the above logarithmic time algorithms do not provide a complete description of the solution, but give quantum states that can be sampled. In [18]}, Liu and Zhang give a fast quantum algorithm based on amplitude amplification and amplitude estimation to approximate the statistical leverage scores of \(A\)  in \(O({\rm log}\,(m + n)s^2 \kappa / \epsilon )\)  time. It achieves an exponential speedup over the best known classical algorithms. Note that the classical algorithm might also complete sampling from the solution in logarithmic time. Recently, Tang [19]} proposed a classical algorithm for recommendation systems within logarithmic time by using the efficient low rank approximation techniques of Frieze, Kannan and Vempala [20]}. Motivated by the dequantizing techniques, other papers are also proposed to deal with some low-rank matrix operations, such as matrix inversion [21]}, [22]}, [23]}, singular value transformation [24]}, non-negative matrix factorization [25]}, support vector machine [26]}, general minimum conical hull problems [27]}. Dequantizing techniques in those algorithms involve two technologies, the Monte-Carlo singular value decomposition and sampling techniques, which could efficiently simulate some special operations on low rank matrices.
