Provable quantum speedups for computing persistence in topological data analysis
read the original abstract
Topological data analysis (TDA) aims to extract noise-robust features from a data set by examining the number and persistence of holes in its topology. We provide an efficient quantum algorithm for a computational problem closely related to a core task in TDA -- determining whether a given hole persists across different length scales. Further, we prove the problem itself is $\mathsf{BQP}_1$-hard, implying that a classical solution is extremely unlikely; this stands in contrast to all previous quantum approaches to TDA, where the problems were also intractable for quantum computers, or where a rigorous proof of classical hardness still remains open. This result implies an {exponential} quantum speedup for this problem under standard complexity-theoretic assumptions. Our approach relies on encoding the persistence of a hole in a variant of the guided sparse Hamiltonian problem, where the guiding state is constructed from a harmonic representative of the hole.
This paper has not been read by Pith yet.
Forward citations
Cited by 4 Pith papers
-
New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes
Quantum algorithms achieve polylogarithmic complexity for Betti number estimation and homology testing via block-encoded Laplacians and cohomological projections, claiming exponential speedups under sparsity assumptions.
-
Fragmentation is Efficiently Learnable by Quantum Neural Networks
Fragment classification is efficiently learnable by quantum neural networks under suitable conditions but resists known classical dequantization techniques.
-
Hodge Spectral Surrogates for Topology-Constrained Optimization
Introduces Hodge spectral relaxations and filters as differentiable surrogates for Betti numbers and persistent homology in optimization on graphs and point clouds.
-
Gauge Geometry of Hodge Zero-Mode Transport in Parameter-Dependent Topological Data Analysis
Introduces a gauge-geometry framework that computes curvature and holonomy of Hodge zero-mode transport to detect structural changes in parameter-dependent topological data.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.