Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians

arXiv:2607.03278v1 Announce Type: cross Abstract: Topological data analysis (TDA) is a machine learning technique that uses topology to extract patterns from data and has shown the potential to exhibit quantum advantage. A key concept in TDA is persistent homology, which measures the robustness of topological information at different lengthscales. In this paper, we introduce and study the problem of normalized persistence, a practically motivated and easily interpretable version of persistent homology that counts the fraction of holes that persist at different lengthscales. We prove that a variant of normalized persistence is mathsf{DQC}_1-hard and contained in mathsf{BQP}, giving evidence of an exponential quantum speedup for TDA under the standard assumption that mathsf{DQC}_1 notsubseteq mathsf{BPP}. These are the first mathsf{DQC}_1-hardness results that are directly applicable to TDA instances. We also find a close connection between normalized persistence and the complexity of estimating spectral quantities in the low-energy subspace of local Hamiltonians. We study a family of such problems, including a low-energy normalized subtrace and spectral density. We show that these are mathsf{DQC}_1-hard for O(1)-local Hamiltonians, strengthening previous results that required log-local interactions. We also introduce a variant of mathsf{DQC}_1 with perfect completeness (mathsf{SDQC}_1) to characterize the hardness of problems normalized by an exact kernel. This includes normalized persistence for O(1)-local Hamiltonians, which we show is mathsf{SDQC}_1-hard.

Source: arXiv cs.LG | 2026-07-07