Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been "dequantized" in the past few years. These dequantization results typically hold when classical algorithms can access the data via length-squared sampling. In this work we investigate how robust these dequantization results are. We introduce the notion of approximate length-squared sampling, where classical algorithms are only able to sample from a distribution close to the ideal distribution in total variation distance. While quantum algorithms are natively robust against small perturbations, current techniques in dequantization are not. Our main technical contribution is showing how many techniques from randomized linear algebra can be adapted to work under this weaker assumption as well. We then use these techniques to show that the recent low-rank dequantization framework by Chia, Gily\'en, Li, Lin, Tang and Wang (JACM 2022) and the dequantization framework for sparse matrices by Gharibian and Le Gall (STOC 2022), which are both based on the Quantum Singular Value Transformation, can be generalized to the case of approximate length-squared sampling access to the input. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms, including quantum algorithms for recommendation systems, supervised clustering and low-rank matrix inversion.
翻译:量子奇异值变换与量子机器学习算法的鲁棒去量子化
翻译后的摘要:
过去几年中,已经对几种线性代数问题,特别是量子机器学习问题进行了“去量子化”的研究。这些去量子化结果通常只在经典算法能够通过长度平方采样来访问数据时成立。本文研究了这些去量子化结果的鲁棒性。我们引入了近似长度平方采样的概念,其中经典算法只能从接近理想分布的分布中进行采样。虽然量子算法天然具有对小扰动的鲁棒性,但是当前的去量子化技术没有这种性质。我们的主要技术贡献是展示如何将许多随机化线性代数的技术适应于这个更弱的假设。然后我们使用这些技术来展示,最近 Chia、Gilyén、Li、Lin、Tang 和 Wang(JACM 2022)提出的低秩去量子化框架和Gharibian 和 Le Gall (STOC 2022) 的用于稀疏矩阵的去量子化框架都可以推广到输入仅具有近似长度平方采样访问的情况下。我们还将这些结果应用于量子机器学习算法,包括推荐系统、监督聚类和低秩矩阵求逆的量子算法的鲁棒性去量子化。