Quantum algorithms for training Gaussian Processes

Abstract

Gaussian processes (GPs) are important models in supervised machine learning. Training in Gaussian processes refers to selecting the covariance functions and the associated parameters in order to improve the outcome of predictions, the core of which amounts to evaluating the logarithm of the marginal likelihood (LML) of a given model. LML gives a concrete measure of the quality of prediction that a GP model is expected to achieve. The classical computation of LML typically carries a polynomial time overhead with respect to the input size. We propose a quantum algorithm that computes the logarithm of the determinant of a Hermitian matrix, which runs in logarithmic time for sparse matrices. This is applied in conjunction with a variant of the quantum linear system algorithm that allows for logarithmic time computation of the form ${\mathbf{y}}^T{A}^{-1}\mathbf{y}$, where $\mathbf{y}$ is a dense vector and $A$ is the covariance matrix. We hence show that quantum computing can be used to estimate the LML of a GP with exponentially improved efficiency under certain conditions.

arXiv comment5 pages. Comments welcome

References in corpus (16)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• An introduction to quantum machine learning
• Quantum Algorithms Revisited
• Quantum Boltzmann Machine
• Prediction by linear regression on a quantum computer
• A quantum linear system algorithm for dense matrices
• Optimal Quantum Clocks
• Quantum adiabatic machine learning
• Quantum assisted Gaussian process regression
• Quantum Recommendation Systems
• Bayesian Deep Learning on a Quantum Computer
• The power of one qumode for quantum computation
• Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
• Improved stochastic trace estimation using mutually unbiased bases

Cited by in corpus (7)

• The prospects of quantum computing in computational molecular biology
• Biology and medicine in the landscape of quantum advantages
• Fault tolerant resource estimation of quantum random-access memories
• Protocol for implementing quantum nonparametric learning with trapped ions
• Quantum algorithms for spectral sums
• Dual-VQE: A quantum algorithm to lower bound the ground-state energy
• Enhanced Quantum Key Distribution using Hybrid Channels and Natural Random Numbers