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:2106.07302 · Physical Review A

Quantum diffusion map for nonlinear dimensionality reduction

Apimuk Sornsaeng, Ninnat Dangniam, Pantita Palittapongarnpim, Thiparat Chotibut

Published Nov 10, 2021• 14 citations
arXivHTMLPDF

Abstract

Inspired by random walks on graphs, the diffusion map (DM) is a class of unsupervised machine learning that offers automatic identification of low-dimensional data structure hidden in a high-dimensional data set. In recent years, among its many applications, the DM has been successfully applied to discover relevant order parameters in many-body systems, enabling automatic classification of quantum phases of matter. However, a classical DM algorithm is computationally prohibitive for a large data set, and any reduction of the time complexity would be desirable. With a quantum computational speedup in mind, we propose a quantum algorithm for the DM, termed the quantum diffusion map (qDM). Our qDM takes as an input $N$ classical data vectors, performs an eigendecomposition of the Markov transition matrix in time $O({log}^{3}N)$, and classically constructs the diffusion map via the readout (tomography) of the eigenvectors, giving a total expected runtime proportional to ${N}^{2}\text{polylog}\phantom{\rule{0.16em}{0ex}}N$. Finally, quantum subroutines in the qDM for constructing a Markov transition matrix and for analyzing its spectral properties can also be useful for other random-walk-based algorithms.

DOI
10.1103/physreva.104.052410

Related papers

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

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

Unsupervised Machine Learning of Quantum Phase Transitions Using Diffusion Maps

Alexander Lidiak, Zhexuan Gong

Experimental quantum simulators have become large and complex enough that discovering new physics from the huge amount of measurement data can be quite challenging, especially when little theoretical understanding of the simulated model is available. Unsupervised machine learning methods are particularly promising in overcoming this challenge. For the specific task of learning quantum phase transitions, unsupervised machine learning methods have primarily been developed for phase transitions characterized by simple order parameters, typically linear in the measured observables. However, such methods often fail for more complicated phase transitions, such as those involving incommensurate phases, valence-bond solids, topological order, and many-body localization. We show that the diffusion map method, which performs nonlinear dimensionality reduction and spectral clustering of the measurement data, has significant potential for learning such complex phase transitions unsupervised. This method may work for measurements of local observables in a single basis and is thus readily applicable to many experimental quantum simulators as a versatile tool for learning various quantum phases and phase transitions.

arXiv:2003.07399•Physical Review Letters•Nov 24, 2020•55 citations

Quantum spectral clustering

Iordanis Kerenidis, Jonas Landman

Spectral clustering is a powerful unsupervised machine learning algorithm for clustering data with nonconvex or nested structures [A. Y. Ng, M. I. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm, in Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference (MIT Press, Cambridge, MA, 2002), pp. 849--856]. With roots in graph theory, it uses the spectral properties of the Laplacian matrix to project the data in a low-dimensional space where clustering is more efficient. Despite its success in clustering tasks, spectral clustering suffers in practice from a fast-growing running time of $O({n}^{3})$, where $n$ is the number of points in the data set. In this work we propose an end-to-end quantum algorithm performing spectral clustering, extending a number of works in quantum machine learning. The quantum algorithm is composed of two parts: the first is the efficient creation of the quantum state corresponding to the projected Laplacian matrix, and the second consists of applying the existing quantum analog of the $k$-means algorithm [I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, $q$-means: A quantum algorithm for unsupervised machine learning, in Advances in Neural Information Processing Systems 32: Proceedings of the 2019 Conference (Curran Associates, Red Hook, NY, 2020), pp. 4136--4146]. Both steps depend polynomially on the number of clusters, as well as precision and data parameters arising from quantum procedures, and polylogarithmically on the dimension of the input vectors. Our numerical simulations show an asymptotic linear growth with $n$ when all terms are taken into account, significantly better than the classical cubic growth. This work opens the path to other graph-based quantum machine learning algorithms, as it provides routines for efficient computation and quantum access to the incidence, adjacency, and projected Laplacian matrices of a graph.

arXiv:2007.00280•Physical Review A•Apr 15, 2021•68 citations

Physics-inspired Generative AI models via real hardware-based noisy quantum diffusion

Marco Parigi, Stefano Martina, Francesco Aldo Venturelli +1 more

Abstract Quantum Diffusion Models (QDMs) are an emerging paradigm in Generative AI that aims to use quantum properties to improve the performances of their classical counterparts. However, existing algorithms are not easily scalable due to the limitations of near-term quantum devices. Following our previous work on QDMs, here we propose and implement two physics-inspired protocols. In the first, we use the formalism of quantum stochastic walks, showing that a specific interplay of quantum and classical dynamics in the forward process produces statistically more robust models generating sets of MNIST images with lower Fréchet Inception Distance (FID) than using totally classical dynamics. In the second approach, we realize an algorithm to generate images by exploiting the intrinsic noise of real IBM quantum hardware with only four qubits. Our work could be a starting point to pave the way for new scenarios for large-scale algorithms in quantum Generative AI, where quantum noise is neither mitigated nor corrected, but instead exploited as a useful resource.

arXiv:2505.22193•Quantum Machine Intelligence•Oct 9, 2026•3 citations

Topological quantum phase transitions retrieved through unsupervised machine learning

Yanming Che, Clemens Gneiting, Tao Liu +1 more

The discovery of topological features of quantum states plays an important role in modern condensed matter physics and various artificial systems. Due to the absence of local order parameters, the detection of topological quantum phase transitions remains a challenge. Machine learning may provide effective methods for identifying topological features. In this work we show that the unsupervised manifold learning can successfully retrieve topological quantum phase transitions in momentum and real space. Our results show that the Chebyshev distance between two data points sharpens the characteristic features of topological quantum phase transitions in momentum space, while the widely used Euclidean distance is in general suboptimal. Then a diffusion map or isometric map can be applied to implement the dimensionality reduction, and to learn about topological quantum phase transitions in an unsupervised manner. We demonstrate this method on the prototypical Su-Schrieffer-Heeger (SSH) model, the Qi-Wu-Zhang (QWZ) model, and the quenched SSH model in momentum space, and further provide implications and demonstrations for learning in real space, where the topological invariants could be unknown or hard to compute. The interpretable good performance of our approach shows the capability of manifold learning, when equipped with a suitable distance metric, in exploring topological quantum phase transitions.

arXiv:2002.02363•Physical review. B./Physical review. B•Oct 29, 2020•94 citations
Inspired by random walks on graphs, the diffusion map (DM) is a class of unsupervised machine learning that offers automatic identification of low-dimensional data structure hidden in a high-dimensional data set. In recent years, among its many applications, the DM has been successfully applied to discover relevant order parameters in many-body systems, enabling automatic classification of quantum phases of matter. However, a classical DM algorithm is computationally prohibitive for a large data set, and any reduction of the time complexity would be desirable. With a quantum computational speedup in mind, we propose a quantum algorithm for the DM, termed the quantum diffusion map (qDM). Our qDM takes as an input NNN classical data vectors, performs an eigendecomposition of the Markov transition matrix in time O(log3N)O({log}^{3}N)O(log3N), and classically constructs the diffusion map via the readout (tomography) of the eigenvectors, giving a total expected runtime proportional to N2polylogN{N}^{2}\text{polylog}\phantom{\rule{0.16em}{0ex}}NN2polylogN. Finally, quantum subroutines in the qDM for constructing a Markov transition matrix and for analyzing its spectral properties can also be useful for other random-walk-based 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.
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.
Experimental quantum simulators have become large and complex enough that discovering new physics from the huge amount of measurement data can be quite challenging, especially when little theoretical understanding of the simulated model is available. Unsupervised machine learning methods are particularly promising in overcoming this challenge. For the specific task of learning quantum phase transitions, unsupervised machine learning methods have primarily been developed for phase transitions characterized by simple order parameters, typically linear in the measured observables. However, such methods often fail for more complicated phase transitions, such as those involving incommensurate phases, valence-bond solids, topological order, and many-body localization. We show that the diffusion map method, which performs nonlinear dimensionality reduction and spectral clustering of the measurement data, has significant potential for learning such complex phase transitions unsupervised. This method may work for measurements of local observables in a single basis and is thus readily applicable to many experimental quantum simulators as a versatile tool for learning various quantum phases and phase transitions.
Spectral clustering is a powerful unsupervised machine learning algorithm for clustering data with nonconvex or nested structures [A. Y. Ng, M. I. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm, in Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference (MIT Press, Cambridge, MA, 2002), pp. 849--856]. With roots in graph theory, it uses the spectral properties of the Laplacian matrix to project the data in a low-dimensional space where clustering is more efficient. Despite its success in clustering tasks, spectral clustering suffers in practice from a fast-growing running time of O(n3)O({n}^{3})O(n3), where nnn is the number of points in the data set. In this work we propose an end-to-end quantum algorithm performing spectral clustering, extending a number of works in quantum machine learning. The quantum algorithm is composed of two parts: the first is the efficient creation of the quantum state corresponding to the projected Laplacian matrix, and the second consists of applying the existing quantum analog of the kkk-means algorithm [I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, qqq-means: A quantum algorithm for unsupervised machine learning, in Advances in Neural Information Processing Systems 32: Proceedings of the 2019 Conference (Curran Associates, Red Hook, NY, 2020), pp. 4136--4146]. Both steps depend polynomially on the number of clusters, as well as precision and data parameters arising from quantum procedures, and polylogarithmically on the dimension of the input vectors. Our numerical simulations show an asymptotic linear growth with nnn when all terms are taken into account, significantly better than the classical cubic growth. This work opens the path to other graph-based quantum machine learning algorithms, as it provides routines for efficient computation and quantum access to the incidence, adjacency, and projected Laplacian matrices of a graph.
Abstract Quantum Diffusion Models (QDMs) are an emerging paradigm in Generative AI that aims to use quantum properties to improve the performances of their classical counterparts. However, existing algorithms are not easily scalable due to the limitations of near-term quantum devices. Following our previous work on QDMs, here we propose and implement two physics-inspired protocols. In the first, we use the formalism of quantum stochastic walks, showing that a specific interplay of quantum and classical dynamics in the forward process produces statistically more robust models generating sets of MNIST images with lower Fréchet Inception Distance (FID) than using totally classical dynamics. In the second approach, we realize an algorithm to generate images by exploiting the intrinsic noise of real IBM quantum hardware with only four qubits. Our work could be a starting point to pave the way for new scenarios for large-scale algorithms in quantum Generative AI, where quantum noise is neither mitigated nor corrected, but instead exploited as a useful resource.
The discovery of topological features of quantum states plays an important role in modern condensed matter physics and various artificial systems. Due to the absence of local order parameters, the detection of topological quantum phase transitions remains a challenge. Machine learning may provide effective methods for identifying topological features. In this work we show that the unsupervised manifold learning can successfully retrieve topological quantum phase transitions in momentum and real space. Our results show that the Chebyshev distance between two data points sharpens the characteristic features of topological quantum phase transitions in momentum space, while the widely used Euclidean distance is in general suboptimal. Then a diffusion map or isometric map can be applied to implement the dimensionality reduction, and to learn about topological quantum phase transitions in an unsupervised manner. We demonstrate this method on the prototypical Su-Schrieffer-Heeger (SSH) model, the Qi-Wu-Zhang (QWZ) model, and the quenched SSH model in momentum space, and further provide implications and demonstrations for learning in real space, where the topological invariants could be unknown or hard to compute. The interpretable good performance of our approach shows the capability of manifold learning, when equipped with a suitable distance metric, in exploring topological quantum phase transitions.