# Quantum diffusion map for nonlinear dimensionality reduction

arXiv: https://arxiv.org/abs/2106.07302 · HTML: https://mlsanity.com/paper/2106.07302/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 46 references that are in the map.
- First posted on arXiv 14 Jun 2021.

## Builds on (most cited first, 7 of 7)

- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [A Quantum Interior Point Method for LPs and SDPs](https://mlsanity.com/paper/1808.09266/) (2018)
- [Quantum linear systems algorithms: a primer](https://mlsanity.com/paper/1802.08227/) (2018)
- [Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions](https://mlsanity.com/paper/2004.10756/) (2020)
- [Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving](https://mlsanity.com/paper/1911.07306/) (2019)
- [Unsupervised machine learning of quantum phase transitions using diffusion maps](https://mlsanity.com/paper/2003.07399/) (2020)

## Built on by (most cited first, 1 of 1)

- [Snake net and balloon force with a neural network for detecting multiple phases](https://mlsanity.com/paper/2205.09699/) (2022)

## Abstract (arXiv)

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