# Quantum Topological Data Analysis with Linear Depth and Exponential Speedup

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 59 references that are in the map.
- First posted on arXiv 5 Aug 2021.

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

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Efficient Learning for Deep Quantum Neural Networks](https://mlsanity.com/paper/1902.10445/) (2019)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era](https://mlsanity.com/paper/2102.05321/) (2021)
- [(Pseudo) Random Quantum States with Binary Phase](https://mlsanity.com/paper/1906.10611/) (2019)
- [Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2011.04125/) (2020)
- [Fast estimation of approximate matrix ranks using spectral densities](https://mlsanity.com/paper/1608.05754/) (2016)
- [Review of a Quantum Algorithm for Betti Numbers](https://mlsanity.com/paper/1906.07673/) (2019)

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

- [Topological data analysis on noisy quantum computers](https://mlsanity.com/paper/2209.09371/) (2022)
- [Quantum Distance Approximation for Persistence Diagrams](https://mlsanity.com/paper/2402.17295/) (2024)
- [Depth-Efficient Quantum Topological Data Analysis for Regime-Specific Detection of Financial Stress](https://mlsanity.com/paper/2607.09906/) (2026)
- [Quantum Topological Data Encoding](https://mlsanity.com/paper/2607.13847/) (2026)

## Abstract (arXiv)

Quantum computing offers the potential of exponential speedups for certain classical computations. Over the last decade, many quantum machine learning (QML) algorithms have been proposed as candidates for such exponential improvements. However, two issues unravel the hope of exponential speedup for some of these QML algorithms: the data-loading problem and, more recently, the stunning dequantization results of Tang et al. A third issue, namely the fault-tolerance requirements of most QML algorithms, has further hindered their practical realization. The quantum topological data analysis (QTDA) algorithm of Lloyd, Garnerone and Zanardi was one of the first QML algorithms that convincingly offered an expected exponential speedup. From the outset, it did not suffer from the data-loading problem. A recent result has also shown that the generalized problem solved by this algorithm is likely classically intractable, and would therefore be immune to any dequantization efforts. However, the QTDA algorithm of Lloyd et~al. has a time complexity of O(n4/(ε2 δ)) (where n is the number of data points, ε is the error tolerance, and δ is the smallest nonzero eigenvalue of the restricted Laplacian) and requires fault-tolerant quantum computing, which has not yet been achieved. In this paper, we completely overhaul the QTDA algorithm to achieve an improved exponential speedup and depth complexity of O(nlog(1/(δε))). Our approach includes three key innovations: (a) an efficient realization of the combinatorial Laplacian as a sum of Pauli operators; (b) a quantum rejection sampling approach to restrict the superposition to the simplices in the complex; and (c) a stochastic rank estimation method to estimate the Betti numbers. We present a theoretical error analysis, and the circuit and computational time and depth complexities for Betti number estimation.