Provable quantum speedups for computing persistence in topological data analysis
arXiv:2410.21258 · doi:10.1103/gvys-hl8h
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 -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.
17 pages
References in corpus (16)
- Quantum algorithm for solving linear systems of equations
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- A quantum-inspired classical algorithm for recommendation systems
- Weighted simplicial complexes and their representation power of higher-order network data and topology
- Persistent Laplacians: properties, algorithms and implications
- Towards quantum advantage via topological data analysis
- Analyzing Prospects for Quantum Advantage in Topological Data Analysis
- Hardness of approximation for quantum problems
- Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
- A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits
- Global topological synchronization of weighted simplicial complexes
- Complexity of Supersymmetric Systems and the Cohomology Problem
- A (simple) classical algorithm for estimating Betti numbers
- Clique Homology is QMA1-hard
- Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
- Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis