Pith. sign in

REVIEW 5 cited by

Provable quantum speedups for computing persistence in topological data analysis

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2410.21258 v2 pith:C5XXGO3G submitted 2024-10-28 quant-ph cs.CCcs.LG

Casper Gyurik , Alexander Schmidhuber , Robbie King , Vedran Dunjko , Ryu Hayakawa This is my paper · ORCID
classification quant-phcs.CCcs.LG
keywords quantumproblemdataholepersistenceanalysisclassicaltopological
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A quantum algorithm for Khovanov homology

    math.GT 2025-01 conditional novelty 8.0 of 10

    A conditional quantum algorithm for estimating the Betti numbers of Khovanov homology, together with DQC1, BQP, and #P hardness results for harder approximation regimes.

  2. Hodge Spectral Surrogates for Topology-Constrained Optimization

    math.AT 2026-06 unverdicted novelty 6.0 of 10

    Introduces Hodge spectral relaxations and filters as differentiable surrogates for Betti numbers and persistent homology in optimization on graphs and point clouds.

  3. Gauge Geometry of Hodge Zero-Mode Transport in Parameter-Dependent Topological Data Analysis

    math.AT 2026-05 unverdicted novelty 6.0 of 10

    Introduces a gauge-geometry framework that computes curvature and holonomy of Hodge zero-mode transport to detect structural changes in parameter-dependent topological data.

  4. Topological network analysis using a programmable photonic quantum processor

    quant-ph 2025-07 conditional novelty 6.0 of 10

    A programmable Gaussian boson sampling photonic processor extracts k-cliques and topological features from complex-weighted networks.

  5. Testing the presence of balanced and bipartite components in a sparse graph is QMA1-hard

    quant-ph 2024-12 reject novelty 4.0 of 10

    The claimed QMA1-hardness of sparse balancedness and sparse bipartitedness is not established, because the main spectral equivalence is false.

Pith tools