Quantum assisted Gaussian process regression
This addresses a bottleneck in supervised machine learning for researchers and practitioners by potentially speeding up regression tasks, though it appears incremental as it adapts an existing quantum method to a known problem.
The paper tackles the computational inefficiency of Gaussian process regression, which typically requires O(n^3) logic gates, by applying a quantum linear systems algorithm to achieve exponential or polynomial reductions in computation time in various instances.
Gaussian processes (GP) are a widely used model for regression problems in supervised machine learning. Implementation of GP regression typically requires $O(n^3)$ logic gates. We show that the quantum linear systems algorithm [Harrow et al., Phys. Rev. Lett. 103, 150502 (2009)] can be applied to Gaussian process regression (GPR), leading to an exponential reduction in computation time in some instances. We show that even in some cases not ideally suited to the quantum linear systems algorithm, a polynomial increase in efficiency still occurs.