Source-linked AI summary
Quantum assisted Gaussian process regression
Zhikuan Zhao, Jack K. Fitzsimons, Joseph F. Fitzsimons
TL;DR
Gaussian process regression is widely used but typically requires O(n^3) computation, motivating a more scalable approach. The paper applies the quantum linear systems algorithm to estimate GPR’s predictor and variance, finding exponential speed-ups in favorable sparse, well-conditioned cases and polynomial improvements in less ideal cases.
Problem
Gaussian process regression is widely used, but practical implementations typically require O(n^3) operations, limiting exact inference for large training sets.
Source: pp. 1–2Method
The paper applies the quantum linear systems algorithm to GPR and estimates the linear predictor and regression variance through repeated measurements of quantum output states.
Source: pp. 1, 3, 4Results
Exponential speed-up is achievable when the kernel and input vector are sparse and the system is well-conditioned; less favorable cases can still scale as ˜O(n).
Source: p. 4Takeaways & Limitations
QLA is most advantageous for GPR problems with sparse kernels and, ideally, sparse input vectors, while sparsity and conditioning determine whether exponential improvement is obtained.
Source: p. 4Applying QLA requires care because state preparation, matrix conditioning, sparsity, and extracting information from the output state can limit the claimed speed-up.
Source: pp. 2–3
Abstract
from arXiv · showhide
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.