# Provable quantum speedups for computing persistence in topological data analysis

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 28 Oct 2024.

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

- [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)
- [Persistent Laplacians: properties, algorithms and implications](https://mlsanity.com/paper/2012.02808/) (2020)
- [Towards quantum advantage via topological data analysis](https://mlsanity.com/paper/2005.02607/) (2020)
- [Weighted simplicial complexes and their representation power of higher-order network data and topology](https://mlsanity.com/paper/2207.04710/) (2022)
- [Topological data analysis on noisy quantum computers](https://mlsanity.com/paper/2209.09371/) (2022)
- [A (simple) classical algorithm for estimating Betti numbers](https://mlsanity.com/paper/2211.09618/) (2022)

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

- [Limits of quantum generative models with classical sampling hardness](https://mlsanity.com/paper/2512.24801/) (2025)
- [Quantum Topological Data Encoding](https://mlsanity.com/paper/2607.13847/) (2026)

## Abstract (arXiv)

Topological data analysis (TDA) aims to extract noise-robust features from a data set by examining the number and persistence of holes in its topology. We provide an efficient quantum algorithm for a computational problem closely related to a core task in TDA -- determining whether a given hole persists across different length scales. Further, we prove the problem itself is mathsfBQP1-hard, implying that a classical solution is extremely unlikely; this stands in contrast to all previous quantum approaches to TDA, where the problems were also intractable for quantum computers, or where a rigorous proof of classical hardness still remains open. This result implies an exponential quantum speedup for this problem under standard complexity-theoretic assumptions. Our approach relies on encoding the persistence of a hole in a variant of the guided sparse Hamiltonian problem, where the guiding state is constructed from a harmonic representative of the hole.