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

International Symposium on Computer Technology and Information Science (ISCTIS)

Variational Quantum Isometric Feature Mapping

Guoqing Gong

Published Jul 12, 2024• 1 citation
Publisher

Abstract

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.

DOI
10.1109/isctis63324.2024.10699116

Related papers

Quantum Isomap algorithm for manifold learning

Weijun Feng, Gongde Guo, Song Lin +1 more

Isometric feature mapping (Isomap) is a nonlinear dimensionality reduction algorithm based on the concept of manifold learning. The algorithm is widely used in neuroimaging, spectral analysis, and other fields. While Isomap performs well in certain scenarios, it still faces the challenge of time complexity when dealing with large-scale data sets. In this paper, we proposed a quantum Isomap algorithm that runs with quadratic dependence on the number of data points. Technically, our algorithm is based on two subroutines, quantum Floyd's algorithm and quantum multidimensional scaling. They are of independent interest and may serve as potential tools for addressing other problems.

Physical Review Applied•Jul 19, 2024•7 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

Quantum Locality Sensitive Discriminant Analysis for Data Dimensionality Reduction

Yongmei Li, Chengkang Pan, Xian Ping Lu +3 more

The era of big data has made traditional machine learning algorithms struggle with high-dimensional, nonlinear datasets due to high computational resource consumption, long training times, and limited generalization. Quantum computing, with its exponential parallelism from qubit superposition and entanglement, offers new hope for machine learning. Local Sensitive Discriminant Analysis (LSDA) algorithm is a widely used dimensionality reduction technique in machine learning. However, it is time-consuming when handling large-scale high-dimensional data. This paper proposed a quantum version of LSDA algorithm, which transforms the generalized eigenvalue problem in LSDA into a Hermitian eigenvalue problem, solved using quantum phase estimation and block-encoding techniques. Two post-processing strategies are provided to obtain low-dimensional data for quantum or classical machine learning tasks. The quantum LSDA algorithm obtains polynomial speedups compared to the classical LSDA in terms of the number of data points and dimensionality, showing the potential of quantum technique to boost machine learning efficiency.

International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT)•Oct 24, 2025•0 citations

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

ZHANG Xin, Gongde Guo, YU ChaoHua +1 more

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.

Zhongguo kexue. Wulixue Lixue Tianwenxue•Mar 1, 2024•1 citation

Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm

Weijun Feng, Gongde Guo, Kai Yu +2 more

Isomap algorithm is a representative manifold learning algorithm. The algorithm simplifies the data analysis process and is widely used in neuroimaging, spectral analysis and other fields. However, the classic Isomap algorithm becomes unwieldy when dealing with large data sets. Our object is to accelerate the classical algorithm with quantum computing, and propose the quantum Isomap algorithm. The algorithm consists of two sub-algorithms. The first one is the quantum Floyd algorithm, which calculates the shortest distance for any two nodes. The other is quantum Isomap algorithm based on quantum Floyd algorithm, which finds a low-dimensional representation for the original high-dimensional data. Finally, we analyze that the quantum Floyd algorithm achieves exponential speedup without sampling. In addition, the time complexity of quantum Isomap algorithm is $O(dNpolylogN)$. Both algorithms reduce the time complexity of classical algorithms.

arXiv:2212.03599•Dec 7, 2022•0 citations

Variational quantum support vector machine based on Hadamard test

Xu Li, Xiaoyu Zhang, Jin‐Min Liang +4 more

Abstract Classical machine learning algorithms seem to be totally incapable of processing tremendous amounts of data, while quantum machine learning algorithms could deal with big data with ease and provide exponential acceleration over classical counterparts. Meanwhile, variational quantum algorithms are widely proposed to solve relevant computational problems on noisy, intermediate-scale quantum devices. In this paper, we apply variational quantum algorithms to quantum support vector machines and demonstrate a proof-of-principle numerical experiment of this algorithm. In addition, in the classification stage, fewer qubits, shorter circuit depth, and simpler measurement requirements show its superiority over the former algorithms.

Communications in Theoretical Physics•Apr 2, 2022•9 citations
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.
Isometric feature mapping (Isomap) is a nonlinear dimensionality reduction algorithm based on the concept of manifold learning. The algorithm is widely used in neuroimaging, spectral analysis, and other fields. While Isomap performs well in certain scenarios, it still faces the challenge of time complexity when dealing with large-scale data sets. In this paper, we proposed a quantum Isomap algorithm that runs with quadratic dependence on the number of data points. Technically, our algorithm is based on two subroutines, quantum Floyd's algorithm and quantum multidimensional scaling. They are of independent interest and may serve as potential tools for addressing other problems.
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.
The era of big data has made traditional machine learning algorithms struggle with high-dimensional, nonlinear datasets due to high computational resource consumption, long training times, and limited generalization. Quantum computing, with its exponential parallelism from qubit superposition and entanglement, offers new hope for machine learning. Local Sensitive Discriminant Analysis (LSDA) algorithm is a widely used dimensionality reduction technique in machine learning. However, it is time-consuming when handling large-scale high-dimensional data. This paper proposed a quantum version of LSDA algorithm, which transforms the generalized eigenvalue problem in LSDA into a Hermitian eigenvalue problem, solved using quantum phase estimation and block-encoding techniques. Two post-processing strategies are provided to obtain low-dimensional data for quantum or classical machine learning tasks. The quantum LSDA algorithm obtains polynomial speedups compared to the classical LSDA in terms of the number of data points and dimensionality, showing the potential of quantum technique to boost machine learning efficiency.
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.
Isomap algorithm is a representative manifold learning algorithm. The algorithm simplifies the data analysis process and is widely used in neuroimaging, spectral analysis and other fields. However, the classic Isomap algorithm becomes unwieldy when dealing with large data sets. Our object is to accelerate the classical algorithm with quantum computing, and propose the quantum Isomap algorithm. The algorithm consists of two sub-algorithms. The first one is the quantum Floyd algorithm, which calculates the shortest distance for any two nodes. The other is quantum Isomap algorithm based on quantum Floyd algorithm, which finds a low-dimensional representation for the original high-dimensional data. Finally, we analyze that the quantum Floyd algorithm achieves exponential speedup without sampling. In addition, the time complexity of quantum Isomap algorithm is O(dNpolylogN)O(dNpolylogN)O(dNpolylogN). Both algorithms reduce the time complexity of classical algorithms.
Abstract Classical machine learning algorithms seem to be totally incapable of processing tremendous amounts of data, while quantum machine learning algorithms could deal with big data with ease and provide exponential acceleration over classical counterparts. Meanwhile, variational quantum algorithms are widely proposed to solve relevant computational problems on noisy, intermediate-scale quantum devices. In this paper, we apply variational quantum algorithms to quantum support vector machines and demonstrate a proof-of-principle numerical experiment of this algorithm. In addition, in the classification stage, fewer qubits, shorter circuit depth, and simpler measurement requirements show its superiority over the former algorithms.