# Topological data analysis on noisy quantum computers

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 99 references that are in the map.
- First posted on arXiv 19 Sep 2022.

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

- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Topology of deep neural networks](https://mlsanity.com/paper/2004.06093/) (2020)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [On Characterizing the Capacity of Neural Networks using Algebraic Topology](https://mlsanity.com/paper/1802.04443/) (2018)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions](https://mlsanity.com/paper/1811.00414/) (2018)
- [Clique topology reveals intrinsic geometric structure in neural correlations](https://mlsanity.com/paper/1502.06172/) (2015)
- [(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)
- [Quantum Topological Data Analysis with Linear Depth and Exponential Speedup](https://mlsanity.com/paper/2108.02811/) (2021)
- [Review of a Quantum Algorithm for Betti Numbers](https://mlsanity.com/paper/1906.07673/) (2019)

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

- [Advantage of Quantum Machine Learning from General Computational Advantages](https://mlsanity.com/paper/2312.03057/) (2023)
- [Provable quantum speedups for computing persistence in topological data analysis](https://mlsanity.com/paper/2410.21258/) (2024)
- [Higher-order topological kernels via quantum computation](https://mlsanity.com/paper/2307.07383/) (2023)
- [Quantum Topological Data Encoding](https://mlsanity.com/paper/2607.13847/) (2026)

## Abstract (arXiv)

Topological data analysis (TDA) is a powerful technique for extracting complex and valuable shape-related summaries of high-dimensional data. However, the computational demands of classical algorithms for computing TDA are exorbitant, and quickly become impractical for high-order characteristics. Quantum computers offer the potential of achieving significant speedup for certain computational problems. Indeed, TDA has been purported to be one such problem, yet, quantum computing algorithms proposed for the problem, such as the original Quantum TDA (QTDA) formulation by Lloyd, Garnerone and Zanardi, require fault-tolerance qualifications that are currently unavailable. In this study, we present NISQ-TDA, a fully implemented end-to-end quantum machine learning algorithm needing only a short circuit-depth, that is applicable to high-dimensional classical data, and with provable asymptotic speedup for certain classes of problems. The algorithm neither suffers from the data-loading problem nor does it need to store the input data on the quantum computer explicitly. The algorithm was successfully executed on quantum computing devices, as well as on noisy quantum simulators, applied to small datasets. Preliminary empirical results suggest that the algorithm is robust to noise.