Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2110.11541 · Chinese Physics B

Quantum algorithm for neighborhood preserving embedding

Shi‐Jie Pan, Lin‐Chun Wan, Hailing Liu, Yusen Wu, Su‐Juan Qin, Qiaoyan Wen, Fei Gao

Published Feb 7, 2022• 25 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/1674-1056/ac523a

Related papers

Variational quantum algorithms for dimensionality reduction and classification

Jin‐Min Liang, Shu‐Qian Shen, Ming Li +1 more

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 $(\mathcal{G},\mathcal{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.

arXiv:1910.12164•Physical Review A•Mar 16, 2020•43 citations

Variational Quantum Isometric Feature Mapping

Guoqing Gong

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.

International Symposium on Computer Technology and Information Science (ISCTIS)•Jul 12, 2024•2 citations

Quantum Nearest-Neighbor Algorithms for Machine Learning

Nathan Wiebe, Ashish Kapoor, Krysta M. Svore

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.

Quantum Information and Computation•Jan 9, 2014•75 citations

Quantum-enhanced t-stochastic neighbor embedding for high-dimensional data visualization

Xin Zhang, Chao‐Hua Yu, Gongde Guo +1 more

t-distributed stochastic neighbor embedding (t-SNE) is a nonlinear dimensionality reduction algorithm that preserves local similarity by matching probability distributions between high- and low-dimensional spaces. Owing to its ability to capture complex manifold structures, t-SNE has become a widely used technique for high-dimensional data visualization. However, it still faces significant computational challenges when dealing with large-scale datasets. In this paper, we present a quantum-enhanced t-SNE algorithm that achieves a quadratic speedup with respect to the number of data samples. Specifically, three unitary operators are constructed using quantum arithmetic and comparators to compute the probability distributions. By integrating them with the Hadamard transform, the gradients of the Kullback-Leibler divergence can be efficiently computed. Moreover, since a complete quantum procedure is provided, our method surpasses the performance of existing quantum variants.

Physical Review Research•Apr 6, 2026•0 citations

Fast variational quantum algorithms for training neural networks and solving convex optimizations

Changpeng Shao

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.

Physical Review A•Apr 17, 2019•13 citations

Robustness of Quantum Algorithms Against Approximate Data Representations

Vladyslav Los, Mykola Maksymenko, Maciej Koch-Janusz +2 more

Quantum algorithms face practical difficulties and overheads in execution on realistic devices, potentially thwarting their theoretical advantages. A key practical challenge is efficiently encoding classical data, since data embedding layers, often exponential in the number of qubits, can consume a significant portion of the circuit depth. One possible strategy to address this is to compress the standard data embeddings using variational circuits. The approximate amplitude encoding (AAE) algorithm successfully applies this approach to financial calculations and image pattern matching, achieving only polynomially deep embedding layers. While prior works focus on optimizing the approximate embedding in isolation, the ultimate goal is the compound algorithm's performance. This study systematically examines the impact of embedding compression on the fidelity of the subsequent quantum algorithm in a noiseless setting, specifically investigating amplitude encoding and its dependence on input data set size and complexity. Trainability of the different variational ansaetze, their output state fidelity, and the degree of the embedding layer depth compression are investigated. Performance benchmarks of standard quantum algorithms, e.g. Grover search, amplitude estimation, and quantum Fourier transform (QFT), are conducted based on the degree of compression and quality of the compressed input state. Results show that the amplitude encoding circuit can be compressed substantially in depth, for generic data and a small number of qubits, with only marginal loss in state fidelity. Certain algorithms, like QFT, demonstrate robustness to such approximations.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•0 citations
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.
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)(\mathcal{G},\mathcal{S})(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.
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.
t-distributed stochastic neighbor embedding (t-SNE) is a nonlinear dimensionality reduction algorithm that preserves local similarity by matching probability distributions between high- and low-dimensional spaces. Owing to its ability to capture complex manifold structures, t-SNE has become a widely used technique for high-dimensional data visualization. However, it still faces significant computational challenges when dealing with large-scale datasets. In this paper, we present a quantum-enhanced t-SNE algorithm that achieves a quadratic speedup with respect to the number of data samples. Specifically, three unitary operators are constructed using quantum arithmetic and comparators to compute the probability distributions. By integrating them with the Hadamard transform, the gradients of the Kullback-Leibler divergence can be efficiently computed. Moreover, since a complete quantum procedure is provided, our method surpasses the performance of existing quantum variants.
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.
Quantum algorithms face practical difficulties and overheads in execution on realistic devices, potentially thwarting their theoretical advantages. A key practical challenge is efficiently encoding classical data, since data embedding layers, often exponential in the number of qubits, can consume a significant portion of the circuit depth. One possible strategy to address this is to compress the standard data embeddings using variational circuits. The approximate amplitude encoding (AAE) algorithm successfully applies this approach to financial calculations and image pattern matching, achieving only polynomially deep embedding layers. While prior works focus on optimizing the approximate embedding in isolation, the ultimate goal is the compound algorithm's performance. This study systematically examines the impact of embedding compression on the fidelity of the subsequent quantum algorithm in a noiseless setting, specifically investigating amplitude encoding and its dependence on input data set size and complexity. Trainability of the different variational ansaetze, their output state fidelity, and the degree of the embedding layer depth compression are investigated. Performance benchmarks of standard quantum algorithms, e.g. Grover search, amplitude estimation, and quantum Fourier transform (QFT), are conducted based on the degree of compression and quality of the compressed input state. Results show that the amplitude encoding circuit can be compressed substantially in depth, for generic data and a small number of qubits, with only marginal loss in state fidelity. Certain algorithms, like QFT, demonstrate robustness to such approximations.