Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
复制标题
基于采样的次线性低秩矩阵算术框架用于反量化量子机器学习
DOI：
10.1145/3549524
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Wang, Chunhao
中科院分区：
文献类型：
--
作者：
Chia, Nai-Hui;Gilyén, András Pal;Li, Tongyang;Lin, Han-Hsuan;Tang, Ewin;Wang, Chunhao
我们提出了一个算法框架量子启发经典算法接近低秩矩阵，推广了一系列结果开始唐的突破量子启发算法推荐系统[STOC'19]。受量子线性代数算法和Gilyén等人的量子奇异值变换（SVT）框架的启发。[STOC'19]，我们开发了SVT的经典算法，这些算法在适当的量子采样假设下，与输入维度无关。我们的研究结果给出了令人信服的证据，在相应的QRAM数据结构输入模型，量子SVT不产生指数量子加速。由于量子SVT框架基本上概括了量子线性代数的所有已知技术，因此我们的结果与以前工作中的采样引理相结合，足以概括所有关于去量化量子机器学习算法的先前结果。特别是，我们的经典SVT框架恢复，并经常提高推荐系统，主成分分析，监督聚类，支持向量机，低秩回归和半定程序求解的去量化结果。我们还给出了额外的反量子化结果的低秩哈密顿模拟和判别分析。我们的改进来自于识别量子启发输入模型的关键特征，这是所有先前量子启发结果的核心：2-范数采样可以在时间上近似矩阵乘积，而与其维度无关。我们把所有的主要结果都归结为这个事实，使我们的论述简洁、自足和直观。
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC’19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all prior results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ2-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.
登录
查看更多内容
影响因子：
6.4
作者：
Preskill, John
通讯作者：
Preskill, John
运算符 H"older--Zygmund 函数
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
A. Aleksandrov;V. Peller
通讯作者：
V. Peller
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
A. Aleksandrov;V. Peller
通讯作者：
V. Peller
基于特征脸的人脸建模与识别
DOI：
--
发表时间：
2003
期刊：
IPSJ SIG Technical Reports Vol. CVIM-139
影响因子：
--
作者：
T.;Shakunaga;F.;Sakaue;Y.;Matsubara
通讯作者：
Matsubara