Quantum Communication Complexity of Linear Regression
Quantum Communication Complexity of Linear Regression
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 …