Quantum computing and persistence in topological data analysis
This provides a theoretical foundation for quantum speedups in topological data analysis, which is incremental as it builds on existing complexity theory.
The paper tackles the computational problem of determining hole persistence in topological data analysis, showing it is BQP-hard and in BQP, implying an exponential quantum speedup under standard assumptions.
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 $\mathsf{BQP}_1$-hard and contained in $\mathsf{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.