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

@misc{lowe2026complexity,
  title = {{Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians}},
  author = {Dominic Lowe and M. S. Kim and Roberto Bondesan and Ryu Hayakawa},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2607.03278},
  eprint = {2607.03278},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.03278},
}

TY  - UNPB
TI  - Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians
AU  - Dominic Lowe
AU  - M. S. Kim
AU  - Roberto Bondesan
AU  - Ryu Hayakawa
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2607.03278
UR  - https://arxiv.org/abs/2607.03278
AB  - 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 DQC_1-hard and contained in BQP, giving evidence of an exponential quantum speedup for TDA under the standard assumption that DQC_1 not⊆ BPP. These are the first DQC_1-hardness results for clique complexes, making them 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 DQC_1-hard for O(1)-local Hamiltonians, strengthening previous results that required log-local interactions. We also introduce a variant of DQC_1 with perfect completeness (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 SDQC_1-hard.
ER  -