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• 2 citations
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•8 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

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
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.
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.
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.