Quantum diffusion map for nonlinear dimensionality reduction

This is the authors' abstract. We don't add key points for this paper.

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³N), and classically constructs the diffusion map via the readout (tomography) of the eigenvectors, giving a total expected runtime proportional to N²polylog0.16em0exN. 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.