Scattered data fitting is a frequently encountered problem for reconstructing an unknown function from given scattered data. Radial basis function (RBF) methods have proven to be highly useful to deal with this problem. We describe two quantum algorithms to efficiently fit scattered data based on globally and compactly supported RBFs respectively. For the globally supported RBF method, the core of the quantum algorithm relies on using coherent states to calculate the radial functions and a nonsparse matrix exponentiation technique for efficiently performing a matrix inversion. A quadratic speedup is achieved in the number of data over the classical algorithms. For the compactly supported RBF method, we mainly use the HHL algorithm as a subroutine to design an efficient quantum procedure that runs in time logarithmic in the number of data, achieving an exponential improvement over the classical methods.
Scattered data fitting is a frequently encountered problem for reconstructing an unknown function from given scattered data. Radial basis function (RBF) methods have proven to be highly useful to deal with this problem. We describe two quantum algorithms to efficiently fit scattered data based on globally and compactly supported RBFs respectively. For the globally supported RBF method, the core of the quantum algorithm relies on using coherent states to calculate the radial functions and a nonsparse matrix exponentiation technique for efficiently performing a matrix inversion. A quadratic speedup is achieved in the number of data over the classical algorithms. For the compactly supported RBF method, we mainly use the HHL algorithm as a subroutine to design an efficient quantum procedure that runs in time logarithmic in the number of data, achieving an exponential improvement over the classical methods.
Radial basis function (RBF) network is a simple but useful neural network model that contains wide applications in machine learning. The training of an RBF network reduces to solve a linear system, which is time consuming classically. Based on HHL algorithm, we propose two quantum algorithms to train RBF networks. To apply the HHL algorithm, we choose using the Hamiltonian simulation algorithm proposed in [P. Rebentrost, A. Steffens, I. Marvian and S. Lloyd, Phys. Rev. A 97, 012327, 2018]. However, to use this result, an oracle to query the entries of the matrix of the network should be constructed. We apply the amplitude estimation technique to build this oracle. The final results indicate that if the centers of the RBF network are the training samples, then the quantum computer achieves exponential speedup at the number and the dimension of training samples over the classical computer; if the centers are determined by the K-means algorithm, then the quantum computer achieves quadratic speedup at the number of samples and exponential speedup at the dimension of samples.
Abstract The radial basis function (RBF) method is widely used for the numerical solution of the Poisson problem in high dimension, where the approximate solution can be found by solving a large system of linear equations. We demonstrate that the RBF method can be accelerated on a quantum computer by using an efficient quantum algorithm for linear equations. We compare the theoretical performance of our quantum algorithm with that of a standard classical algorithm, and find that the quantum algorithm can achieve a polynomial speedup.
Radial-basis-function (RBF) networks are third-layered neural networks that are widely used in function approximation and data classification. Here we propose a quantum model for RBF networks. As in the classical case, we use radial basis functions as activation functions; quantum linear algebraic techniques and coherent states can be applied to implement these functions. We define the state of the weight as a tensor product of single-qubit states. This gives a simple approach to implement the quantum RBF network in quantum circuits. In this model we prove that training is almost quadratically faster than in the classical case. We demonstrate numerically that the quantum RBF network can solve binary classification problems as effectively as the classical RBF network, while the time and number of iterations used for training are much smaller.
Along with the development of quantum technology, finding useful applications of quantum computers has been a central pursuit. Despite various quantum algorithms have been developed, many of them often require strong input assumptions, which is hardware demanding. In particular, recent advances on dequantization have revealed that the quantum advantage is more of a mere artifact of strong input assumptions. In this work, we propose a variant of these algorithms, leveraging both classical and quantum resources. Provided the classical knowledge (the entries) of the matrix/vector of interest, a classical procedure is used to pre-process this information. Then they are fed into a quantum circuit which is shown to be a block encoding of the matrix of interest. From this block-encoding, we show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, preparing ground state, and data fitting. We also analyze our protocol, showing that both the classical and quantum procedure can achieve logarithmic complexity in the input dimension, thus implying its potential for near term realization. We then discuss several implications and corollaries of our result. First,, our results suggest there are certain matrices/Hamiltonians where our method can provide exponential improvement compared to the existing ones with respect to the sparsity. Regarding dense linear systems, our method achieves exponential speed-up with respect to the inverse of error tolerance, compared to the best previously known quantum algorithm for dense systems. Last, and most importantly, regarding quantum data fitting, we show how the output of our quantum algorithms can be leveraged to predict unseen data. Thus, it provides an end-to-end application, which has been an open aspect of the previous quantum data fitting algorithm.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
Kernel-based one-class classification (OCC) methods leverage kernel functions and are widely used for anomaly detection due to their ability to map data into high-dimensional feature spaces. One such model is Least Squares Support Vector Data Description (LS-SVDD), which aims to construct a minimum volume hypersphere that encompasses the target class observations. A pivotal component in the construction of the hypersphere is the choice of kernel. In this study, the Radial Basis Function (RBF) kernel is compared to a quantum kernel constructed through quantum feature maps. The two kernel methods are compared across four distributional shift scenarios—mean shift, rotating covariance, correlation drift, and Gaussian mixture—at three dimensionalities through simulations. Additionally, the two kernel methods are also evaluated using real-world data through an illustrative example. Furthermore, the Harrow-Hassidim-Lloyd (HHL) quantum algorithm was examined as a potential speedup for solving linear systems of equations within the LS-SVDD framework in quantum space.