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•36 citations

A general quantum matrix exponential dimensionality reduction framework based on block-encoding

Li, Yong-Mei, Hai-Ling Liu, Shijie 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 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 new efficient quantum algorithms can be derived from this framework. Specifically, by constructing the block-encodings of the data matrix exponentials, we solve the eigenproblem and then obtain the digital-encoded quantum state corresponding to the compressed low-dimensional dataset, which can be directly utilized as 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•Jun 16, 2023•0 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•0 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.

Physical Review A•Oct 19, 2023•7 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•133 citations

Quantum locally linear embedding

Xi He, Sun Li, Chufan Lyu +1 more

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(\mathrm{poly}(\log N))$. 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.

•Oct 17, 2019•2 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.
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 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 new efficient quantum algorithms can be derived from this framework. Specifically, by constructing the block-encodings of the data matrix exponentials, we solve the eigenproblem and then obtain the digital-encoded quantum state corresponding to the compressed low-dimensional dataset, which can be directly utilized as 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.
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.
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.
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 .
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 NNN, where NNN is the global number of the original high-dimensional data. In data preprocessing, we invoke the quantum kkk-nearest neighbors algorithm (kkk-NN) to find out the kkk 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(log⁡N))O(\mathrm{poly}(\log N))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.