Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians
2026-07-03 • Computational Complexity
Computational ComplexityMachine Learning
AI summaryⓘ
The authors study a version of a topological data analysis method called persistent homology, which counts how many topological features (holes) last across different scales, calling it normalized persistence. They show that computing this normalized persistence is very hard for classical computers but can be done efficiently on certain quantum computers, suggesting a quantum advantage for these problems. They connect this difficulty to estimating properties of quantum systems described by local Hamiltonians and introduce a new complexity class variant to better understand these problems. Their results improve previous findings by dealing with simpler types of quantum interactions.
Topological Data AnalysisPersistent HomologyNormalized PersistenceQuantum ComputingDQC1 (Deterministic Quantum Computation with One Clean Qubit)BQP (Bounded-Error Quantum Polynomial Time)Local HamiltoniansSpectral DensityQuantum Complexity TheoryPerfect Completeness
Authors
Dominic Lowe, M. S. Kim, Roberto Bondesan, Ryu Hayakawa
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.