# Assessing Quantum Advantage for Gaussian Process Regression

arXiv: https://arxiv.org/abs/2505.22502 · HTML: https://mlsanity.com/paper/2505.22502/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 45 references that are in the map.
- First posted on arXiv 28 May 2025.

## Builds on (most cited first, 18 of 18)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [When Gaussian Process Meets Big Data: A Review of Scalable GPs](https://mlsanity.com/paper/1807.01065/) (2018)
- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Hilbert Space Methods for Reduced-Rank Gaussian Process Regression](https://mlsanity.com/paper/1401.5508/) (2014)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions](https://mlsanity.com/paper/1811.00414/) (2018)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Quantum assisted Gaussian process regression](https://mlsanity.com/paper/1512.03929/) (2015)
- [Quantum-Assisted Hilbert-Space Gaussian Process Regression](https://mlsanity.com/paper/2402.00544/) (2024)
- [Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra](https://mlsanity.com/paper/2302.01873/) (2023)

## Built on by (most cited first, 2 of 2)

- [Spectral Estimation with Free Decompression](https://mlsanity.com/paper/2506.11994/) (2025)
- [Spectral Anatomy of Quantum Gaussian Process Kernels](https://mlsanity.com/paper/2605.30952/) (2026)

## Abstract (arXiv)

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.