Assessing Quantum Advantage for Gaussian Process Regression

2025/05/28 by Dominic Lowe, M. S. Kim, Lowe, Dominic +3 · 1 citation
Computer Science · #FOS: Computer and information sciences #FOS: Physical sciences #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2505.22502

openalex publication_date 2025/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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.

Citations

• Quantum-Assisted Hilbert-Space Gaussian Process Regression
• QRAM: A Survey and Critique
• Optimal scaling quantum linear systems solver via discrete adiabatic theorem
• Preconditioning for Scalable Gaussian Process Hyperparameter Optimization
• Faster quantum-inspired algorithms for solving linear systems
• Wide neural networks of any depth evolve as linear models under gradient descent *
• Quantum Principal Component Analysis Only Achieves an Exponential Speedup Because of Its State Preparation Assumptions
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• A quantum-inspired classical algorithm for recommendation systems
• When Gaussian Process Meets Big Data: A Review of Scalable GPs
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Quantum Recommendation Systems
• Hilbert space methods for reduced-rank Gaussian process regression
• Quantum algorithms for supervised and unsupervised machine learning
• The condition number of a randomly perturbed matrix
• A very short proof of Cauchy's interlace theorem for eigenvalues of Hermitian matrices

Cited by

• Spectral Estimation with Free Decompression

Related

• Quantum Machine Learning using Gaussian Processes with Performant Quantum Kernels
• A quantum gradient descent algorithm for optimizing Gaussian Process models
• Quantum-assisted Gaussian process regression using random Fourier features
• Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters
• Accelerating Regression Tasks with Quantum Algorithms