Nhat A. Nghiem, Junseo Lee (Jun 03 2025).

Abstract: Recently, the application of quantum computation to topological data analysis (TDA) has received increasing attention. In particular, several quantum algorithms have been proposed for estimating (normalized) Betti numbers, a central challenge in TDA. However, it was recently proven that estimating Betti numbers is an NP-hard problem, revealing a complexity-theoretic limitation to achieving a generic quantum advantage for this task. Motivated by this limitation and inspired by previous progress, we explore broader quantum approaches to TDA. First, we consider scenarios in which a simplicial complex is specified in a more informative form, enabling alternative quantum algorithms to estimate Betti numbers and persistent Betti numbers. We then move beyond Betti numbers and study the problem of testing the homology class of a given cycle, as well as distinguishing between homology classes. We also introduce cohomological techniques for these problems, along with a quantum algorithm. We then discuss their potential use in the testing and tracking of homology classes, which can be useful for TDA applications. Our results show that, despite the hardness of general Betti number estimation, quantum algorithms can still offer speed-ups in structured settings.

Arxiv: https://arxiv.org/abs/2506.01432