Quantum diffusion map for nonlinear dimensionality reduction

Abstract

Inspired by random walk on graphs, diffusion map (DM) is a class of unsupervised machine learning that offers automatic identification of low-dimensional data structure hidden in a high-dimensional dataset. In recent years, among its many applications, DM has been successfully applied to discover relevant order parameters in many-body systems, enabling automatic classification of quantum phases of matter. However, classical DM algorithm is computationally prohibitive for a large dataset, and any reduction of the time complexity would be desirable. With a quantum computational speedup in mind, we propose a quantum algorithm for DM, termed quantum diffusion map (qDM). Our qDM takes as an input $N$ classical data vectors, performs an eigen-decomposition 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}N$. Lastly, quantum subroutines in qDM for constructing a Markov transition matrix, and for analyzing its spectral properties can also be useful for other random walk-based algorithms.

13 pages, 4 figures

References in corpus (6)

• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• A Grand Unification of Quantum Algorithms
• Resilience of quantum random access memory to generic noise
• Experimental realization of 105-qubit random access quantum memory
• Automatic Learning of Topological Phase Boundaries

Cited by in corpus (4)

• Experimental implementation of quantum algorithm for association rules mining
• High robustness quantum walk search algorithm with qudit Householder traversing coin, machine learning study
• Classifying topological neural network quantum states via diffusion maps
• Snake net and balloon force with a neural network for detecting multiple phases