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