论文标题
线性回归的量子通信复杂性
Quantum communication complexity of linear regression
论文作者
论文摘要
量子计算机可能会在其经典同行方面达到求解线性代数问题的加速。但是，在某些情况下，例如对于低级矩阵 - 取消算法表明不可能有指数量子加速。在这项工作中，我们表明量子计算机在通信复杂性方面具有可证明的多项式和指数加速，对于某些基本线性代数问题\ Update {如果对等级没有限制}。我们主要专注于解决线性回归和哈密顿模拟。在量子情况下，任务是准备结果的量子状态。为了进行公平的比较，在经典情况下，任务是从结果中进行采样。我们在两方和多方模型中研究了这两个问题，提出了近乎最佳的量子协议，并证明了量子/经典下限。在此过程中，我们为量子奇异值转换提出了有效的量子协议，这是设计量子算法的强大技术。这将有助于为许多其他问题开发有效的量子协议。
Quantum computers may achieve speedups over their classical counterparts for solving linear algebra problems. However, in some cases -- such as for low-rank matrices -- dequantized algorithms demonstrate that there cannot be an exponential quantum speedup. In this work, we show that quantum computers have provable polynomial and exponential speedups in terms of communication complexity for some fundamental linear algebra problems \update{if there is no restriction on the rank}. We mainly focus on solving linear regression and Hamiltonian simulation. In the quantum case, the task is to prepare the quantum state of the result. To allow for a fair comparison, in the classical case, the task is to sample from the result. We investigate these two problems in two-party and multiparty models, propose near-optimal quantum protocols and prove quantum/classical lower bounds. In this process, we propose an efficient quantum protocol for quantum singular value transformation, which is a powerful technique for designing quantum algorithms. This will be helpful in developing efficient quantum protocols for many other problems.
