Neighborhood preserving embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality n. However, the algorithm has two disadvantages: (i) It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one. (ii) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm, and achieve a significant speedup compared to Liang et al.’s algorithm even without considering the complexity of the VQA.
Reducing the dimension of nonlinear data is crucial in data processing and visualization. The locally linear embedding algorithm (LLE) is specifically a representative nonlinear dimensionality reduction method with well maintaining the original manifold structure. In this paper, we present two implementations of the quantum locally linear embedding algorithm (qLLE) to perform the nonlinear dimensionality reduction on quantum devices. One implementation, the linear-algebra-based qLLE algorithm utilizes quantum linear algebra subroutines to reduce the dimension of the given data. The other implementation, the variational qLLE algorithm utilizes a variational quantum-classical hybrid procedure to acquire the low-dimensional data. The classical LLE algorithm requires polynomial time complexity of
N, where
N is the global number of the original high-dimensional data. In data preprocessing, we invoke the quantum
k-nearest neighbors algorithm (
k-NN) to find out the
k nearest neighbors of the given data with quadratic speedup. For the main part of the qLLE algorithm, compared with the corresponding classical algorithm, the linear-algebra-based qLLE algorithm proposed in this paper achieves an exponential speedup in
O(poly(logN)). The variational qLLE algorithm can be implemented on the near term quantum devices. In addition, the corresponding quantum circuits of the qLLE algorithm are also presented.
In this work, we present a quantum neighborhood preserving embedding and a quantum local discriminant embedding for dimensionality reduction and classification. We demonstrate that these two algorithms have an exponential speedup over their respectively classical counterparts. Along the way, we propose a variational quantum generalized eigenvalue solver that finds the generalized eigenvalues and eigenstates of a matrix pencil
(G,S). As a proof of principle, we implement our algorithm to solve ${2}^{5}\ifmmode\times\else\texttimes\fi{}{2}^{5}$ generalized eigenvalue problems. Finally, our results offer two optional outputs with quantum or classical form, which can be directly applied in another quantum or classical machine learning process.
Currently, big data often encounters "curse of dimensionality" problems. Using classic nonlinear dimensionality reduction algorithm, the complexity increases sharply with the increase of data dimension and quantity. While, quantum dimensionality reduction algorithm can achieve exponential acceleration for large-scale data processing, it requires a large number of n -qubit operations. To solve the problems above, this paper proposed a variational quantum isometric feature mapping algorithm based on classical nonlinear dimensionality reduction algorithm, quantum machine learning algorithm and variational quantum algorithm. In the data processing stage, the quantum k-nearest neighbor algorithm is used to obtain the K nearest neighbors of the original data, construct the adjacency graph, and calculate the geodesic distance between each point to get the distance matrix. The inner product matrix is obtained by redesigning the quantum circuit. Then the characteristic problem of the inner product matrix is solved by using the variational quantum eigensolver. Finally, the representation of low-dimensional data after dimensionality reduction is obtained, and the nonlinear dimensionality reduction of large-scale high-dimensional data is realized.
Dimensionality reduction algorithms, which reduce the dimensionality of a given data set whereas preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan et al. proposed a quantum version of the A-optimal projection algorithm (AOP) for dimensionality reduction [Phys. Rev. A 99, 032311 (2019)] and claimed that the algorithm has exponential speedups on the dimensionality of the original feature space
n and the dimensionality of the reduced feature space
k over the classical algorithm. In this paper, we correct the time complexity of the algorithm of Duan et al. to $O\left[\frac{{\ensuremath{\kappa}}^{4s}\sqrt{{k}^{s}}}{{\ensuremath{\epsilon}}^{s}}{\mathrm{polylog}}^{s}\left(\frac{mn}{\ensuremath{\epsilon}}\right)\right]$, where $\ensuremath{\kappa}$ is the condition number of a matrix that related to the original data set,
s is the number of iterations,
m is the number of data points, and $\ensuremath{\epsilon}$ is the desired precision of the output state. Since the time complexity has an exponential dependence on
s, the quantum algorithm can only be beneficial for high-dimensional problems with a small number of iterations
s. To get a further speedup, we propose an improved quantum AOP algorithm with time complexity $O\left[\frac{s{\ensuremath{\kappa}}^{6}\sqrt{k}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{nm}{\ensuremath{\epsilon}}\right)+\frac{{s}^{2}{\ensuremath{\kappa}}^{4}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{\ensuremath{\kappa}k}{\ensuremath{\epsilon}}\right)\right]$ and space complexity $O[{log}_{2}(nk/\ensuremath{\epsilon})+s]$. With space complexity slightly worse, our algorithm achieves, at least, a polynomial speedup compared to the algorithm of Duan et al.. Also, our algorithm shows exponential speedups in
n and
m compared with the classical algorithm when $\ensuremath{\kappa},\phantom{\rule{0.28em}{0ex}}k$, and $1/\ensuremath{\epsilon}$ are
O[polylog(nm)].
We present several quantum algorithms for performing nearest-neighbor learning. At the core of our algorithms are fast and coherent quantum methods for computing distance metrics such as the inner product and Euclidean distance. We prove upper bounds on the number of queries to the input data required to compute these metrics. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to the corresponding classical algorithm. In certain cases, we show exponential or even super-exponential reductions over the classical analog. We study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.
Variational hybrid quantum classical algorithms to optimizations are important applications for near-term quantum computing. This paper proposes two quantum algorithms (the second one is variational) for training neural networks. Both of them obtain exponential speedup at the number of samples and polynomial speedup at the dimension of the samples over classical training algorithms. Moreover, the proposed quantum algorithms return the classical information of the training weight so that the outputs can be used directly to solve other problems. For practicality, we draw the quantum circuits to implement the two algorithms. Finally, as an inspiration, we show how to apply the variational algorithm to achieve speedup at the number of constraints in solving convex optimization problems.