Quantum algorithms for training Gaussian Processes

Zhikuan Zhao, Jack K. Fitzsimons, Michael A. Osborne, Stephen J. Roberts, Joseph F. FitzsimonsarXiv 2018 · DOI · OpenReview

Abstract

Gaussian processes (GPs) are fundamental models in supervised machine learning, particularly valued for their ability to provide uncertainty estimates alongside predictions. Training a GP involves selecting covariance functions and hyperparameters to maximize the Log Marginal Likelihood (LML). However, the classical computation of LML typically carries a polynomial time overhead ($O(n^3)$) with respect to the input size $n$, limiting its scalability. We propose a quantum algorithmic framework that computes the logarithm of the determinant of a Hermitian matrix in logarithmic time for sparse matrices. Combined with a variant of the quantum linear system algorithm (QLSA) to evaluate the quadratic form $\mathbf{y}^TA^{-1}\mathbf{y}$, we demonstrate that quantum computing can estimate the LML of a GP with an exponential improvement in efficiency under certain conditions.

Introduction

Gaussian processes (GPs) represent a cornerstone of Bayesian machine learning. Unlike many "black-box" models, GPs offer a probabilistic framework for regression and classification, providing a measure of confidence in every prediction. Despite their utility, GPs face a significant "Achilles' heel": scalability.

To train a GP, one must optimize the Log Marginal Likelihood (LML), a metric that quantifies the quality of the model's predictions. Classically, this requires calculating the determinant of a covariance matrix and performing a matrix inversion. For a dataset of size $n$, these operations scale as $O(n^3)$. As modern datasets grow into the millions, standard GPs become computationally intractable. This paper introduces a quantum framework designed to bypass these classical bottlenecks.

The Log Marginal Likelihood Challenge

The LML is defined by the following expression: $$LML = -\frac{1}{2} \log \det[K + \sigma_n^2 I] - \frac{1}{2} \mathbf{y}^T (K + \sigma_n^2 I)^{-1} \mathbf{y} - \frac{n}{2} \log 2\pi$$

Where:

  • $K$ is the covariance matrix.
  • $\sigma_n^2$ is the noise variance.
  • $\mathbf{y}$ is the vector of training targets.

The computational difficulty lies in the first two terms: the log-determinant (the "penalty" term) and the quadratic form (the "data fit" term).

Proposed Quantum Methodology

The proposed algorithm addresses the LML components using two distinct quantum techniques:

1. Estimating the Log-Determinant via Spectral Sampling

Rather than computing the entire determinant—a difficult task even for quantum computers—the algorithm treats the log-determinant as a sampling problem. By utilizing Quantum Phase Estimation (QPE), the algorithm samples the eigenvalues $\lambda_i$ of the covariance matrix. Since the log-determinant is the sum of the logs of the eigenvalues ($\sum \log \lambda_i$), the authors show that by repeatedly sampling $\lambda_i$ and calculating the average $n \langle \log \lambda_i \rangle$, they can estimate the log-det term with high efficiency. This "sampling shortcut" is a key insight of the paper.

2. Evaluating the Quadratic Form via Modified QLSA

To compute the data fit term $\mathbf{y}^T A^{-1} \mathbf{y}$, the authors adapt the Quantum Linear System Algorithm (QLSA), commonly known as HHL. Instead of a direct $1/x$ inversion, they employ a $1/\sqrt{x}$ transformation. This allows the quantum computer to prepare a state proportional to $A^{-1/2} |\mathbf{y}\rangle$. Measuring the success probability of this state preparation yields the desired quadratic form. This modification improves the conditioning of the problem, making the measurement step more efficient than standard inversion.

Complexity and Performance

The algorithm's primary advantage is its scaling. For $s$-sparse matrices (where each row has at most $s$ non-zero entries), the runtime is: $$\tilde{O}\left(\frac{s \log n}{\sigma_n^2 \epsilon}\right)$$

This represents an exponential speedup over the $O(n^3)$ classical bottleneck. The paper also highlights several key performance characteristics:

  • Low-Rank Matrices: If the matrix is not sparse but is low-rank, the algorithm can still achieve logarithmic time using density matrix exponentiation.
  • Error Resilience: The relative variance of the LML estimate does not scale with the number of data points $n$, ensuring the quantum advantage holds for massive datasets.
  • Polynomial Backup: In the worst-case scenario of full-rank, non-sparse matrices, the authors note that singular value estimation still provides a polynomial speedup ($O(\sqrt{n} \log n)$).

Limitations and Future Directions

While the theoretical speedup is transformative, the authors identify several practical requirements:

  • QRAM Requirements: The algorithm assumes the existence of Quantum Random Access Memory (QRAM) to load the training data vector $\mathbf{y}$ into a quantum state. Reliable, large-scale QRAM remains a significant hardware challenge.
  • The Noise Floor: The runtime is sensitive to the minimum eigenvalue, represented by the noise floor $\sigma_n^2$. If the data is extremely clean (very low noise), the condition number of the matrix worsens, which can slow the algorithm.
  • Sparsity Constraints: The most dramatic speedups are contingent on the covariance matrix being sparse or low-rank. While many GP approximations utilize these structures, they are not universal to all kernels.

Conclusion

This work demonstrates that quantum computing can fundamentally change the scalability of Gaussian Processes. By leveraging spectral sampling and modified linear system algorithms, the proposed framework reduces the $O(n^3)$ training bottleneck to logarithmic time. This opens the door for Bayesian machine learning to be applied to datasets of a scale previously considered impossible.

Summary updated

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}^TA^{-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.
BibTeX
@misc{zhao2018quantum,
  author = {Zhikuan Zhao and Jack K. Fitzsimons and Michael A. Osborne and Stephen J. Roberts and Joseph F. Fitzsimons},
  title = {{Quantum algorithms for training Gaussian Processes}},
  year = {2018},
  eprint = {1803.10520},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.10520},
}
Figure