Quantum computing and persistence in topological data analysis

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 show that a computational problem closely related to a core task in TDA — determining whether a given hole persists across different length scales — is BQP1
-hard and contained in BQP
. 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.

https://ui.adsabs.harvard.edu/#abs/2024arXiv241021258G/abstract