证明量子算法在高斯过程回归中无指数加速优势
Assessing Quantum Advantage for Gaussian Process Regression
- 理论证明核矩阵条件数随规模线性增长
- 多种主流核函数数值验证结果一致
- 适用于量子与去量子化算法，适合量子机器学习研究者
高斯过程回归是机器学习中的经典方法，已有多个量子算法被提出。本文证明，在广泛场景下这些算法均不存在指数加速。通过严格推导，在一般数据和核函数假设下，核矩阵的条件数至少随矩阵规模线性增长；同时证明其稀疏性和Frobenius范数也呈线性增长。该结果对量子算法运行时间的影响不依赖于经典数据加载复杂度，同样适用于去量子化算法。我们还针对机器学习中常用的几种核函数进行了数值验证。
原文摘要 · Abstract (English)
Gaussian Process Regression is a well-known machine learning technique for which several quantum algorithms have been proposed. We show here that in a wide range of scenarios these algorithms show no exponential speedup. We achieve this by rigorously proving that the condition number of a kernel matrix scales at least linearly with the matrix size under general assumptions on the data and kernel. We additionally prove that the sparsity and Frobenius norm of a kernel matrix scale linearly under similar assumptions. The implications for the quantum algorithms runtime are independent of the complexity of loading classical data on a quantum computer and also apply to dequantised algorithms. We supplement our theoretical analysis with numerical verification for popular kernels in machine learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。