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.
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.
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.
With the significant advancement in quantum computation during the past couple of decades, the exploration of machine-learning subroutines using quantum strategies has become increasingly popular. Gaussian process regression is a widely used technique in supervised classical machine learning. Here we introduce an algorithm for Gaussian process regression using continuous-variable quantum systems that can be realized with technology based on photonic quantum computers under certain assumptions regarding distribution of data and availability of efficient quantum access. Our algorithm shows that by using a continuous-variable quantum computer a dramatic speedup in computing Gaussian process regression can be achieved, i.e., the possibility of exponentially reducing the time to compute. Furthermore, our results also include a continuous-variable quantum-assisted singular value decomposition method of nonsparse low rank matrices and forms an important subroutine in our Gaussian process regression algorithm.
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.
The Gaussian kernel is a very popular kernel function used in many machine learning algorithms, especially in support vector machines (SVMs). It is more often used than polynomial kernels when learning from nonlinear datasets and is usually employed in formulating the classical SVM for nonlinear problems. Rebentrost et al. discussed an elegant quantum version of a least square support vector machine using quantum polynomial kernels, which is exponentially faster than the classical counterpart. This paper demonstrates a quantum version of the Gaussian kernel and analyzes its runtime complexity using the quantum random access memory (QRAM) in the context of quantum SVM. Our analysis shows that the runtime computational complexity of the quantum Gaussian kernel is approximated to [Formula: see text] and even [Formula: see text] when [Formula: see text] and the error [Formula: see text] are small enough to be ignored, where [Formula: see text] is the dimension of the training instances, [Formula: see text] is the accuracy, [Formula: see text] is the dot product of the two quantum states, and [Formula: see text] is the Taylor remainder error term. Therefore, the run time complexity of the quantum version of the Gaussian kernel seems to be significantly faster when compared with its classical version.
The Gaussian kernel is a very popular kernel function used in many machine-learning algorithms, especially in support vector machines (SVM). For nonlinear training instances in machine learning, it often outperforms polynomial kernels in model accuracy. We use Gaussian kernel profoundly in formulating nonlinear classical SVM. In the recent research, P. Rebentrost et.al. discuss a very elegant quantum version of least square support vector machine using the quantum version of polynomial kernel, which is exponentially faster than the classical counterparts. In this paper, we have demonstrated a quantum version of the Gaussian kernel and analyzed its complexity in the context of quantum SVM. Our analysis shows that the computational complexity of the quantum Gaussian kernel is O(\epsilon^(-1)logN) with N-dimensional instances and \epsilon with a Taylor remainder error term |R_m (\epsilon^(-1) logN)|.
This chapter covers a number of disparate applications of quantum computing in the area of machine learning. We only consider situations where the dataset is classical (rather than quantum). We cover quantum algorithms for big-data problems relying upon high-dimensional linear algebra, such as Gaussian process regression and support vector machines. We discuss the prospect of achieving a quantum speedup with these algorithms, which face certain input/output caveats and must compete against quantum-inspired classical algorithms. We also cover heuristic quantum algorithms for energy-based models, which are generative machine learning models that learn to produce outputs similar to those in a training dataset. Next, we cover a quantum algorithm for the tensor principal component analysis problem, where a quartic speedup may be available, as well as quantum algorithms for topological data analysis, which aim to compute topologically invariant properties of a dataset. We conclude by covering quantum neural networks and quantum kernel methods, where the machine learning model itself is quantum in nature.