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

Zhongguo kexue. Wulixue Lixue Tianwenxue

基于最大方差展开的量子非线性降维

ZHANG Xin, Gongde Guo, YU ChaoHua, Song Lin

Published Mar 1, 2024• 1 citation
Publisher

Abstract

Maximum variance unfolding is a nonlinear dimensionality reduction algorithm based on the local equidistance of manifolds. However, it is quite computationally expensive, especially when dealing with large-scale datasets. Therefore, an efficient quantum maximum variance unfolding algorithm is proposed herein. First, we propose a quantum matrix square root algorithm with exponential speedup, which can be used to obtain the square root of the involved matrix. As a result, we can efficiently obtain the density operator of the Laplacian matrix. Then, a complete quantum dimensionality reduction algorithm is proposed to map the original high-dimensional data onto a low-dimensional data space using Hamiltonian simulation and phase estimation. Finally, our research reveals that compared with its classical counterpart, the proposed quantum dimensionality reduction algorithm achieves an exponential speedup in terms of dimension and a polynomial speedup in terms of number of samples.

DOI
10.1360/sspma-2024-0098

Related papers

Quantum algorithm for the nonlinear dimensionality reduction with arbitrary kernel

Yaochong Li, Ri‐Gui Zhou, Ruiqing Xu +2 more

Abstract Dimensionality reduction (DR) techniques play an extremely critical role in the data mining and pattern recognition field. However, most DR approaches involve large-scale matrix computations, which cause too high running complexity to implement in the big data scenario efficiently. The recent developments in quantum information processing provide a novel path to alleviate this problem, where a potential quantum acceleration can be obtained comparing with the classical counterpart. Nevertheless, existing proposals for quantum DR methods faced the common dilemma of the nonlinear generalization owing to the intrinsic linear limitation of quantum computation. In this paper, an architecture to simulate the arbitrary nonlinear kernels on a universal quantum computer is illustrated and further propose the quantum kernel principal component analysis (QKPCA) algorithm. The key idea is employing the truncated Taylor expansion to approximate the arbitrary nonlinear kernel within the fixed error and then constructing the corresponding Hamiltonian simulation for the quantum phase estimation algorithm. It is demonstrated theoretically that the QKPCA is qualified for the nonlinear DR task while the exponential speedup is also maintained. In addition, this research has the potential ability to develop other quantum DR approaches and existing linear quantum machine learning models.

Quantum Science and Technology•Oct 5, 2020•35 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 Laplacian Eigenmap

Yiming Huang, Xiaoyu Li

Laplacian eigenmap algorithm is a typical nonlinear model for dimensionality reduction in classical machine learning. We propose an efficient quantum Laplacian eigenmap algorithm to exponentially speed up the original counterparts. In our work, we demonstrate that the Hermitian chain product proposed in quantum linear discriminant analysis (arXiv:1510.00113,2015) can be applied to implement quantum Laplacian eigenmap algorithm. While classical Laplacian eigenmap algorithm requires polynomial time to solve the eigenvector problem, our algorithm is able to exponentially speed up nonlinear dimensionality reduction.

arXiv:1611.00760•Nov 2, 2016•3 citations

Quantum discriminant analysis for dimensionality reduction and classification

Iris Cong, Luming Duan

We present quantum algorithms to efficiently perform discriminant analysis for dimensionality reduction and classification over an exponentially large input data set. Compared with the best-known classical algorithms, the quantum algorithms show an exponential speedup in both the number of training vectors M and the feature space dimension N . We generalize the previous quantum algorithm for solving systems of linear equations (2009 Phys. Rev. Lett. 103 150502 ) to efficiently implement a Hermitian chain product of k trace-normalized N × N Hermitian positive-semidefinite matrices with time complexity of . Using this result, we perform linear as well as nonlinear Fisher discriminant analysis for dimensionality reduction over M vectors, each in an N -dimensional feature space, in time , where denotes the tolerance error, and p is the number of principal projection directions desired. We also present a quantum discriminant analysis algorithm for data classification with time complexity .

arXiv:1510.00113•New Journal of Physics•Jul 6, 2016•139 citations

General quantum matrix exponential dimensionality-reduction framework based on block encoding

Yongmei Li, Hai-Ling Liu, Shi‐Jie Pan +3 more

As a general framework, matrix exponential dimensionality reduction (MEDR) deals with the small-sample-size problem that appears in linear dimensionality-reduction (DR) algorithms. High complexity is the bottleneck in this type of DR algorithm because one has to solve a large-scale matrix exponential generalized eigenproblem. To address it, here we design a general quantum algorithm framework for MEDR based on the block-encoding technique. This framework is configurable, that is, by selecting suitable methods to design the block encodings of the data matrices, a series of efficient quantum algorithms can be derived from this framework. Specifically, by constructing the block encodings of the data matrix exponentials, we solve the generalized eigenproblem and then obtain the digital-encoded quantum state corresponding to the compressed low-dimensional data set, which can be directly utilized as the input state for other quantum machine learning tasks to overcome the curse of dimensionality. As applications, we apply this framework to four linear DR algorithms and design their quantum algorithms, which all achieve a polynomial speedup in the dimension of the sample over their classical counterparts.

arXiv:2306.09606•Physical Review A•Oct 19, 2023•7 citations

Quantum algorithm for random-walk-assisted nonlinear dimensionality reduction

Apimuk Sornsaeng, Thiparat Chotibut, Ninnat Dangniam

Dimensionality reduction is an unsupervised learning technique that uncovers the underlying low-dimensional structure in highdimensional data sets. Random walks on graphs for dimensionality reduction, such as diffusion maps (DM) and the Potential of Heat-diffusion for Affinity-based Trajectory Embedding (PHATE), have emerged as powerful tools for automatically identifying low-dimensional data. These methods have applications in various fields, including many-body physics and bioinformatics. However, the classical implementations of DM and PHATE suffer from a computational bottleneck caused by the eigendecomposition step, which has a cubic time complexity to the size of the data set, rendering them impractical for large data sets. Leveraging the quantum computational speedup, we propose a quantum analog of nonlinear dimensionality reduction, named the quantum diffusion map (qDM), which can significantly reduce the computational cost of constructing the Markov transition matrix. Specifically, our algorithm can construct the Markov transition matrix for N classical data vectors in O(log3 N) time and extract the eigenpairs of the transition matrix classically to construct the DM with an expected runtime of N2polylogN. Moreover, the quantum subroutines utilized in our algorithm have potential applications beyond dimensionality reduction, for example, in any random-walk-based problems requiring Markov transition matrix construction and spectral analysis.

•Jan 1, 2022•0 citations
Maximum variance unfolding is a nonlinear dimensionality reduction algorithm based on the local equidistance of manifolds. However, it is quite computationally expensive, especially when dealing with large-scale datasets. Therefore, an efficient quantum maximum variance unfolding algorithm is proposed herein. First, we propose a quantum matrix square root algorithm with exponential speedup, which can be used to obtain the square root of the involved matrix. As a result, we can efficiently obtain the density operator of the Laplacian matrix. Then, a complete quantum dimensionality reduction algorithm is proposed to map the original high-dimensional data onto a low-dimensional data space using Hamiltonian simulation and phase estimation. Finally, our research reveals that compared with its classical counterpart, the proposed quantum dimensionality reduction algorithm achieves an exponential speedup in terms of dimension and a polynomial speedup in terms of number of samples.
Abstract Dimensionality reduction (DR) techniques play an extremely critical role in the data mining and pattern recognition field. However, most DR approaches involve large-scale matrix computations, which cause too high running complexity to implement in the big data scenario efficiently. The recent developments in quantum information processing provide a novel path to alleviate this problem, where a potential quantum acceleration can be obtained comparing with the classical counterpart. Nevertheless, existing proposals for quantum DR methods faced the common dilemma of the nonlinear generalization owing to the intrinsic linear limitation of quantum computation. In this paper, an architecture to simulate the arbitrary nonlinear kernels on a universal quantum computer is illustrated and further propose the quantum kernel principal component analysis (QKPCA) algorithm. The key idea is employing the truncated Taylor expansion to approximate the arbitrary nonlinear kernel within the fixed error and then constructing the corresponding Hamiltonian simulation for the quantum phase estimation algorithm. It is demonstrated theoretically that the QKPCA is qualified for the nonlinear DR task while the exponential speedup is also maintained. In addition, this research has the potential ability to develop other quantum DR approaches and existing linear quantum machine learning models.
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.
Laplacian eigenmap algorithm is a typical nonlinear model for dimensionality reduction in classical machine learning. We propose an efficient quantum Laplacian eigenmap algorithm to exponentially speed up the original counterparts. In our work, we demonstrate that the Hermitian chain product proposed in quantum linear discriminant analysis (arXiv:1510.00113,2015) can be applied to implement quantum Laplacian eigenmap algorithm. While classical Laplacian eigenmap algorithm requires polynomial time to solve the eigenvector problem, our algorithm is able to exponentially speed up nonlinear dimensionality reduction.
We present quantum algorithms to efficiently perform discriminant analysis for dimensionality reduction and classification over an exponentially large input data set. Compared with the best-known classical algorithms, the quantum algorithms show an exponential speedup in both the number of training vectors M and the feature space dimension N . We generalize the previous quantum algorithm for solving systems of linear equations (2009 Phys. Rev. Lett. 103 150502 ) to efficiently implement a Hermitian chain product of k trace-normalized N × N Hermitian positive-semidefinite matrices with time complexity of . Using this result, we perform linear as well as nonlinear Fisher discriminant analysis for dimensionality reduction over M vectors, each in an N -dimensional feature space, in time , where denotes the tolerance error, and p is the number of principal projection directions desired. We also present a quantum discriminant analysis algorithm for data classification with time complexity .
As a general framework, matrix exponential dimensionality reduction (MEDR) deals with the small-sample-size problem that appears in linear dimensionality-reduction (DR) algorithms. High complexity is the bottleneck in this type of DR algorithm because one has to solve a large-scale matrix exponential generalized eigenproblem. To address it, here we design a general quantum algorithm framework for MEDR based on the block-encoding technique. This framework is configurable, that is, by selecting suitable methods to design the block encodings of the data matrices, a series of efficient quantum algorithms can be derived from this framework. Specifically, by constructing the block encodings of the data matrix exponentials, we solve the generalized eigenproblem and then obtain the digital-encoded quantum state corresponding to the compressed low-dimensional data set, which can be directly utilized as the input state for other quantum machine learning tasks to overcome the curse of dimensionality. As applications, we apply this framework to four linear DR algorithms and design their quantum algorithms, which all achieve a polynomial speedup in the dimension of the sample over their classical counterparts.
Dimensionality reduction is an unsupervised learning technique that uncovers the underlying low-dimensional structure in highdimensional data sets. Random walks on graphs for dimensionality reduction, such as diffusion maps (DM) and the Potential of Heat-diffusion for Affinity-based Trajectory Embedding (PHATE), have emerged as powerful tools for automatically identifying low-dimensional data. These methods have applications in various fields, including many-body physics and bioinformatics. However, the classical implementations of DM and PHATE suffer from a computational bottleneck caused by the eigendecomposition step, which has a cubic time complexity to the size of the data set, rendering them impractical for large data sets. Leveraging the quantum computational speedup, we propose a quantum analog of nonlinear dimensionality reduction, named the quantum diffusion map (qDM), which can significantly reduce the computational cost of constructing the Markov transition matrix. Specifically, our algorithm can construct the Markov transition matrix for N classical data vectors in O(log3 N) time and extract the eigenpairs of the transition matrix classically to construct the DM with an expected runtime of N2polylogN. Moreover, the quantum subroutines utilized in our algorithm have potential applications beyond dimensionality reduction, for example, in any random-walk-based problems requiring Markov transition matrix construction and spectral analysis.