Assessing Quantum Advantage for Gaussian Process Regression

Over the last decade, the question of whether quantum computers can speed up machine learning workloads has been under intense investigation [1, 2, 3]. With quantum computers excelling at performing matrix operations in high-dimensional spaces, a natural question is whether machine learning algorithms can be implemented using quantum linear algebra more efficiently [4, 5, 6]. The workhorse of these proposals is the HHL algorithm that approximates the solution of a linear system [7]. An important caveat of these quantum machine learning algorithms is that for exponential speedup over the best classical methods, we need to load the classical data into a quantum superposition in logarithmic time, an assumption whose practicality has been heavily debated [8]. In fact, classical algorithms supplied with a similar input data structure exhibit only a polynomial slowdown compared to their quantum analogues [9, 10].