Probabilistic machine learning models are distinguished by their ability to integrate prior knowledge of noise statistics, smoothness parameters, and training data uncertainty. A common approach involves modeling data with Gaussian processes; however, their computational complexity quickly becomes intractable as the training dataset grows. To address this limitation, we introduce a quantum-assisted algorithm for sparse Gaussian process regression based on the random Fourier feature kernel approximation. We start by encoding the data matrix into a quantum state using a multi-controlled unitary operation, which encodes the classical representation of the random Fourier features matrix used for kernel approximation. We then employ a quantum principal component analysis along with a quantum phase estimation technique to extract the spectral decomposition of the kernel matrix. We apply a conditional rotation operator to the ancillary qubit based on the eigenvalue. We then use Hadamard and swap tests to compute the mean and variance of the posterior Gaussian distribution. We achieve a polynomialorder computational speedup relative to the classical method.
Probabilistic machine learning models are distinguished by their ability to integrate prior knowledge of noise statistics, smoothness parameters, and training data uncertainty. A common approach involves modeling data with Gaussian processes; however, their computational complexity quickly becomes intractable as the training dataset grows. To address this limitation, we introduce a quantum-assisted algorithm for sparse Gaussian process regression based on the random Fourier feature kernel approximation. We start by encoding the data matrix into a quantum state using a multi-controlled unitary operation, which encodes the classical representation of the random Fourier features matrix used for kernel approximation. We then employ a quantum principal component analysis along with a quantum phase estimation technique to extract the spectral decomposition of the kernel matrix. We apply a conditional rotation operator to the ancillary qubit based on the eigenvalue. We then use Hadamard and swap tests to compute the mean and variance of the posterior Gaussian distribution. We achieve a polynomialorder computational speedup relative to the classical method.
Gaussian processes are probabilistic models that are commonly used as functional priors in machine learning. Due to their probabilistic nature, they can be used to capture prior information on the statistics of noise, smoothness of the functions, and training data uncertainty. However, their computational complexity quickly becomes intractable as the size of the data set grows. We propose a Hilbert-space approximation-based quantum algorithm for Gaussian process regression to overcome this limitation. Our method consists of a combination of classical basis function expansion with quantum computing techniques of quantum principal component analysis, conditional rotations, and Hadamard and tests. The quantum principal component analysis is used to estimate the eigenvalues, while the conditional rotations and the Hadamard and tests are employed to evaluate the posterior mean and variance of the Gaussian process. Our method provides polynomial computational complexity reduction over the classical method. Published by the American Physical Society 2024
Abstract Gaussian processes are widely used probabilistic models for regression and classification tasks. Their flexibility and ability to quantify uncertainties make them well-suited for many applications. However, their applicability to large datasets is limited by the cubic computational time complexity. While reduced-rank methods such as Hilbert space approximations reduce this complexity, scaling to very large datasets remains challenging. Quantum algorithms are promising candidates to further accelerate such computations. Quantum principal component analysis has previously been applied to Hilbert space Gaussian process regression to address this scaling limitation. However, its applicability is limited by the requirement for fault-tolerant quantum hardware. In this work, we present a hybrid quantum-classical model for reduced-rank Gaussian process regression, where we apply a quantum principal component analysis algorithm based on parameterized quantum circuits to Hilbert space Gaussian process regression. In noiseless simulations on a one-dimensional test function, the resulting model reaches a regression accuracy comparable to that of the exact Gaussian process and the classical Hilbert space Gaussian process. The framework uses shallow parameterized circuits and does not require fault-tolerant quantum hardware, which makes it a candidate for noisy intermediate-scale quantum devices.
The aim of this paper is to develop novel quantum algorithms for Gaussian process quadrature methods. Gaussian process quadratures are numerical integration methods where Gaussian processes are used as functional priors for the integrands to capture the uncertainty arising from the sparse function evaluations. Quantum computers have emerged as potential replacements for classical computers, offering exponential reductions in the computational complexity of machine learning tasks. In this paper, we combine Gaussian process quadratures and quantum computing by proposing a quantum low-rank Gaussian process quadrature method based on a Hilbert space approximation of the Gaussian process kernel and enhancing the quadrature using a quantum circuit. The method combines the quantum phase estimation algorithm with the quantum principal component analysis technique to extract information up to a desired rank. Then, Hadamard and SWAP tests are implemented to find the expected value and variance that determines the quadrature. We use numerical simulations of a quantum computer to demonstrate the effectiveness of the method. Furthermore, we provide a theoretical complexity analysis that shows a polynomial advantage over classical Gaussian process quadrature methods. The code is available at https://github.com/cagalvisf/Quantum_HSGPQ.
Gaussian processes are widely known for their ability to provide probabilistic predictions in supervised machine learning models. Their non-parametric nature and flexibility make them particularly effective for regression tasks. However, training a Gaussian process model using standard methods requires matrix inversions with a cubic time complexity, which poses significant computational challenges for inference on larger datasets. Quantum algorithms, such as the HHL algorithm, have been proposed as solutions that overcome the need for classical matrix inversions by efficiently solving linear systems of equations using quantum computers. However, to gain a computational advantage over classical algorithms, these algorithms require fault-tolerant quantum computers with a large number of qubits, which are not yet available. The Variational Quantum Linear Solver is a hybrid quantum-classical algorithm that solves linear systems of equations by optimizing the parameters of a variational quantum circuit using a classical computer. This method is especially suitable for noisy intermediate-scale quantum computers, as it does not require many qubits. It can be used to compute the posterior distribution of a Gaussian process by reformulating the matrix inversion into a set of linear systems of equations. We empirically demonstrate that using the Variational Quantum Linear Solver to perform inference for Gaussian process regression delivers regression quality comparable to that of classical methods.
While quantum annealing (QA) has been developed for combinatorial optimization, practical QA devices operate at finite temperature and under noise, and their outputs can be regarded as stochastic samples close to a Gibbs--Boltzmann distribution. In this study, we propose a QA-in-the-loop kernel learning framework that integrates QA not merely as a substitute for Markov-chain Monte Carlo sampling but as a component that directly determines the learned kernel for regression. Based on Bochner's theorem, a shift-invariant kernel is represented as an expectation over a spectral distribution, and random Fourier features (RFF) approximate the kernel by sampling frequencies. We model the spectral distribution with a (multi-layer) restricted Boltzmann machine (RBM), generate discrete RBM samples using QA, and map them to continuous frequencies via a Gaussian--Bernoulli transformation. Using the resulting RFF, we construct a data-adaptive kernel and perform Nadaraya--Watson (NW) regression. Because the RFF approximation based on cos(ω⊤Δx) can yield small negative values and cancellation across neighbors, the Nadaraya--Watson denominator ∑jkij may become close to zero. We therefore employ nonnegative squared-kernel weights wij=k(xi,xj)2, which also enhances the contrast of kernel weights. The kernel parameters are trained by minimizing the leave-one-out NW mean squared error, and we additionally evaluate local linear regression with the same squared-kernel weights at inference. Experiments on multiple benchmark regression datasets demonstrate a decrease in training loss, accompanied by structural changes in the kernel matrix, and show that the learned kernel tends to improve R2 and RMSE over the baseline Gaussian-kernel NW. Increasing the number of random features at inference further enhances accuracy.
Gaussian process regression (GPR) is a nonparametric supervised learning method, widely valued for its ability to quantify uncertainty. Despite its advantages and broad applications, classical GPR implementations face significant scalability challenges, as they involve matrix operations with a cubic complexity in relation to the dataset size. This computational challenge is further compounded by the demand of optimizing the Gaussian Process (GP) model over its hyperparameters, rendering the total computational cost prohibitive for data intensive problems. To address this issue, we propose a quantum gradient descent algorithm to optimize the GP model. Taking advantage of recent advances in quantum algorithms for linear algebra, our algorithm achieves exponential speedup in computing the gradients of the log marginal likelihood. The entire gradient descent process is integrated into the quantum circuit. Through runtime analysis and error bounds, we demonstrate that our approach significantly improves the scalability of GPR model optimization, making it computationally feasible for large-scale applications.