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:2112.11161

Manifold learning via quantum dynamics

Kumar, Akshat, Mohan Sarovar

Published Dec 20, 2021• 3 citations
arXivHTMLPDF

Abstract

We introduce an algorithm for computing geodesics on sampled manifolds that relies on simulation of quantum dynamics on a graph embedding of the sampled data. Our approach exploits classic results in semiclassical analysis and the quantum-classical correspondence, and forms a basis for techniques to learn the manifold from which a dataset is sampled, and subsequently for nonlinear dimensionality reduction of high-dimensional datasets. We illustrate the new algorithm with data sampled from model manifolds and also by a clustering demonstration based on COVID-19 mobility data. Finally, our method reveals interesting connections between the discretization provided by data sampling and quantization.

DOI
10.48550/arxiv.2112.11161

Related papers

Shining light on data: Geometric data analysis through quantum dynamics

Kumar, Akshat, Mohan Sarovar

Experimental sciences have come to depend heavily on our ability to organize and interpret high-dimensional datasets. Natural laws, conservation principles, and inter-dependencies among observed variables yield geometric structure, with fewer degrees of freedom, on the dataset. We introduce the frameworks of semiclassical and microlocal analysis to data analysis and develop a novel, yet natural uncertainty principle for extracting fine-scale features of this geometric structure in data, crucially dependent on data-driven approximations to quantum mechanical processes underlying geometric optics. This leads to the first tractable algorithm for approximation of wave dynamics and geodesics on data manifolds with rigorous probabilistic convergence rates under the manifold hypothesis. We demonstrate our algorithm on real-world datasets, including an analysis of population mobility information during the COVID-19 pandemic to achieve four-fold improvement in dimensionality reduction over existing state-of-the-art and reveal anomalous behavior exhibited by less than 1.2% of the entire dataset. Our work initiates the study of data-driven quantum dynamics for analyzing datasets, and we outline several future directions for research.

arXiv:2212.00682•Dec 1, 2022•2 citations

Manifold Learning and its Applications in Science

Apimuk Sornsaeng, Thiparat Chotibut

In the age of big data, unsupervised machine learning plays crucial roles in detecting statistical patterns hidden in gigantic dataset. Taking root in statistical physics of random walks and heat diffusion on networks, Diffusion Maps are one of the most efficient modern classical unsupervised algorithms for clustering high-dimensional dataset. Not only it can automatically discover hidden statistical structure in a high-dimensional dataset, but it can also projects the data into a lower dimensional embedding where the majority of the data structure reside. Such projections are termed nonlinear dimensionality reduction or manifold learning in machine leaning literature. In the first part of this thesis, we begin by reviewing the physics of classical random walks on a graph which motivates the construction of Diffusion Maps. We will discuss how Diffusion Maps can perform clustering as well as nonlinear dimensionality reduction based on the properties of Markov transition matrix defined on a dataset-associated graph. We then showcase the usefulness of Diffusion Maps to learn low dimensional embedding in some real data samples. In the second part of this thesis, we bring diffusion maps into the realm of quantum algorithms. Motivated by advances in modern near-term quantum devices, we explore a construction of Quantum Diffusion Maps. By exploiting coherent state encoding scheme into Quantum RAM, we outline how to achieve both quantum computational speedup as well as quantum storage capacity reduction for quantum computations of Diffusion Maps on a quantum device. Lastly, it’s known that quantum walks can spread faster than its classical counterparts; we construct quantum walk protocols that perhaps can provide an alternative way to perform unsupervised data clustering, given that one can create quantum walks on quantum devices or quantum simulators.

•Jan 1, 2019•0 citations

Quantum Simulation on Riemannian Manifolds

Dylan Herman, Jacob Watkins, Guneykan Ozgul +4 more

We investigate algorithms for the quantum simulation of the Schrödinger equation on a Riemannian manifold, where the kinetic operator is defined by the Laplace--Beltrami operator corresponding to the metric. Our first algorithms are based on a global spectral method based on the identification of an efficient transform to the eigenbasis of the Laplace--Beltrami operator. We use this method to provide explicit, efficient, quantum simulation algorithms for the Riemannian Schrödinger equation on tori and spheres with their standard metrics, simplices with the Wright--Fisher metric, truncated positive orthants and their invertible affine images with the log-barrier Hessian metric, and $\ell_p$ balls with a metric induced by the Duffy map. Our second algorithm is based on a coherent simulation of local spectral methods on multiple charts, and is in principle applicable to any compact manifold. We first analyze this algorithm in the continuum and derive conditions under which a polynomial spectral cutoff suffices. We also provide a discretization analysis of a polynomial spectral cutoff for tensor-products of constant-dimensional manifolds. Finally, we consider applications of these methods to optimization and physical simulation. For optimization, we provide results including a generalization and convergence analysis of Quantum Hamiltonian Descent for geodesically convex functions that leads to explicit algorithms on the sphere and simplex, and a Riemannian generalization of the Real-Space Adiabatic Algorithm. For physical simulation, we show that our algorithms can simulate certain spatially discretized field theories, including a variant of the nonlinear sigma model.

quant-pharXiv:2610.03673•Oct 5, 2026•0 citations

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

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

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
We introduce an algorithm for computing geodesics on sampled manifolds that relies on simulation of quantum dynamics on a graph embedding of the sampled data. Our approach exploits classic results in semiclassical analysis and the quantum-classical correspondence, and forms a basis for techniques to learn the manifold from which a dataset is sampled, and subsequently for nonlinear dimensionality reduction of high-dimensional datasets. We illustrate the new algorithm with data sampled from model manifolds and also by a clustering demonstration based on COVID-19 mobility data. Finally, our method reveals interesting connections between the discretization provided by data sampling and quantization.
Experimental sciences have come to depend heavily on our ability to organize and interpret high-dimensional datasets. Natural laws, conservation principles, and inter-dependencies among observed variables yield geometric structure, with fewer degrees of freedom, on the dataset. We introduce the frameworks of semiclassical and microlocal analysis to data analysis and develop a novel, yet natural uncertainty principle for extracting fine-scale features of this geometric structure in data, crucially dependent on data-driven approximations to quantum mechanical processes underlying geometric optics. This leads to the first tractable algorithm for approximation of wave dynamics and geodesics on data manifolds with rigorous probabilistic convergence rates under the manifold hypothesis. We demonstrate our algorithm on real-world datasets, including an analysis of population mobility information during the COVID-19 pandemic to achieve four-fold improvement in dimensionality reduction over existing state-of-the-art and reveal anomalous behavior exhibited by less than 1.2% of the entire dataset. Our work initiates the study of data-driven quantum dynamics for analyzing datasets, and we outline several future directions for research.
In the age of big data, unsupervised machine learning plays crucial roles in detecting statistical patterns hidden in gigantic dataset. Taking root in statistical physics of random walks and heat diffusion on networks, Diffusion Maps are one of the most efficient modern classical unsupervised algorithms for clustering high-dimensional dataset. Not only it can automatically discover hidden statistical structure in a high-dimensional dataset, but it can also projects the data into a lower dimensional embedding where the majority of the data structure reside. Such projections are termed nonlinear dimensionality reduction or manifold learning in machine leaning literature. In the first part of this thesis, we begin by reviewing the physics of classical random walks on a graph which motivates the construction of Diffusion Maps. We will discuss how Diffusion Maps can perform clustering as well as nonlinear dimensionality reduction based on the properties of Markov transition matrix defined on a dataset-associated graph. We then showcase the usefulness of Diffusion Maps to learn low dimensional embedding in some real data samples. In the second part of this thesis, we bring diffusion maps into the realm of quantum algorithms. Motivated by advances in modern near-term quantum devices, we explore a construction of Quantum Diffusion Maps. By exploiting coherent state encoding scheme into Quantum RAM, we outline how to achieve both quantum computational speedup as well as quantum storage capacity reduction for quantum computations of Diffusion Maps on a quantum device. Lastly, it’s known that quantum walks can spread faster than its classical counterparts; we construct quantum walk protocols that perhaps can provide an alternative way to perform unsupervised data clustering, given that one can create quantum walks on quantum devices or quantum simulators.
We investigate algorithms for the quantum simulation of the Schrödinger equation on a Riemannian manifold, where the kinetic operator is defined by the Laplace--Beltrami operator corresponding to the metric. Our first algorithms are based on a global spectral method based on the identification of an efficient transform to the eigenbasis of the Laplace--Beltrami operator. We use this method to provide explicit, efficient, quantum simulation algorithms for the Riemannian Schrödinger equation on tori and spheres with their standard metrics, simplices with the Wright--Fisher metric, truncated positive orthants and their invertible affine images with the log-barrier Hessian metric, and ℓp\ell_pℓp​ balls with a metric induced by the Duffy map. Our second algorithm is based on a coherent simulation of local spectral methods on multiple charts, and is in principle applicable to any compact manifold. We first analyze this algorithm in the continuum and derive conditions under which a polynomial spectral cutoff suffices. We also provide a discretization analysis of a polynomial spectral cutoff for tensor-products of constant-dimensional manifolds. Finally, we consider applications of these methods to optimization and physical simulation. For optimization, we provide results including a generalization and convergence analysis of Quantum Hamiltonian Descent for geodesically convex functions that leads to explicit algorithms on the sphere and simplex, and a Riemannian generalization of the Real-Space Adiabatic Algorithm. For physical simulation, we show that our algorithms can simulate certain spatially discretized field theories, including a variant of the nonlinear sigma model.
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.
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.
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.