{"ID":5935760,"CreatedAt":"2026-07-07T01:22:02.77346169Z","UpdatedAt":"2026-07-07T02:10:06.972658124Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.03278","arxiv_id":"2607.03278","title":"Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians","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 \\not\\subseteq \\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.","short_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 in...","url_abs":"https://arxiv.org/abs/2607.03278","url_pdf":"https://arxiv.org/pdf/2607.03278v1","authors":"[\"Dominic Lowe\",\"M. S. Kim\",\"Roberto Bondesan\",\"Ryu Hayakawa\"]","published":"2026-07-03T12:46:53Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CC\",\"cs.LG\"]","methods":"[]","has_code":false}