Assessing Quantum Advantage for Gaussian Process Regression
This work addresses the quantum computing community by demonstrating that quantum advantages for Gaussian Process Regression are limited, making it an incremental contribution that clarifies theoretical bounds.
The paper tackles the problem of assessing quantum advantage for Gaussian Process Regression by showing that proposed quantum algorithms do not achieve exponential speedup in many scenarios, as proven through rigorous analysis of kernel matrix properties like condition number scaling linearly with matrix size.
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.