Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning

doi:10.1145/3549524

Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning

2022-10-27

0

OA

AI

DOI：10.1145/3549524

原文链接

原文求助

摘要

En 中文

我们提出了一种适用于接近低秩矩阵的量子启发式经典算法框架，该框架推广了由Tang突破性的量子启发式推荐系统算法[STOC’19]开启的一系列结果。受量子线性代数算法以及Gilyén等人提出的量子奇异值变换（SVT）框架[STOC’19]的启发，我们在合适的量子启发式采样假设下，开发了运行时间与输入维度无关的SVT经典算法。我们的结果表明，在对应的QRAM数据结构输入模型中，量子SVT并未带来指数级的量子加速。由于量子SVT框架本质上概括了所有已知的量子线性代数技术，我们的结果结合先前工作中的采样引理，足以推广所有关于量子机器学习算法去量子化的先前结果。具体而言，我们的经典SVT框架恢复了并常常改进了关于推荐系统、主成分分析、监督聚类、支持向量机、低秩回归和半定规划求解的去量子化结果。我们还给出了关于低秩哈密顿量模拟和判别分析的额外去量子化结果。我们的改进来自于识别出量子启发式输入模型的关键特征，该特征是所有先前量子启发式结果的核心：ℓ2-范数采样可以在与矩阵维度无关的时间内近似矩阵乘积。我们将所有主要结果都归结为这一事实，从而使我们的表述简洁、自洽且直观。

Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning

摘要

期刊

机构

引用论文