Assessing quantum advantage for Gaussian process regression
Author(s)
Lowe, Dominic
Kim, MS
Bondesan, Roberto
Type
Journal Article
Abstract
Gaussian Process Regression is a machine learning technique with established applications 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. Our results give similar conclusions for kernel ridge regression and quantum support vector machines under the same 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.
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. Our results give similar conclusions for kernel ridge regression and quantum support vector machines under the same 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.
Date Acceptance
2026-07-31
Citation
npj Quantum Information
ISSN
2056-6387
Publisher
Nature Portfolio
Journal / Book Title
npj Quantum Information
Copyright Statement
© The Author(s) 2026. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Identifier
10.1038/s41534-026-01350-8
Subjects
Lowe
D.
Kim
M.S.
Bondesan
R. Assessing quantum advantage for Gaussian process regression. npj Quantum Inf (2026)
Publication Status
Published online
Date Publish Online
2026-08-14