Quantum algorithm for the spectral analysis of a random walk operator with the application in manifold learning

Inspired by random walks on graphs, the diffusion map (DM) is a ubiquitous unsupervised machine learning algorithm 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 polylog N . Importantly, quantum subroutines in the qDM for constructing a Markov transition matrix and for analyzing its spectral properties provide an exponential speedup, which can also be useful for other random-walk-based algorithms.