Click here to flash read.
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.
