Quantum algorithm for persistent Betti numbers and topological data analysis
arXiv:2111.00433 · doi:10.22331/q-2022-12-07-873
Abstract
Topological data analysis (TDA) is an emergent field of data analysis. The critical step of TDA is computing the persistent Betti numbers. Existing classical algorithms for TDA are limited if we want to learn from high-dimensional topological features because the number of high-dimensional simplices grows exponentially in the size of the data. In the context of quantum computation, it has been previously shown that there exists an efficient quantum algorithm for estimating the Betti numbers even in high dimensions. However, the Betti numbers are less general than the persistent Betti numbers, and there have been no quantum algorithms that can estimate the persistent Betti numbers of arbitrary dimensions. This paper shows the first quantum algorithm that can estimate the (normalized) persistent Betti numbers of arbitrary dimensions. Our algorithm is efficient for simplicial complexes such as the Vietoris-Rips complex and demonstrates exponential speedup over the known classical algorithms.
arXiv comment27 pages; Accepted in Quantum
References in corpus (23)
- Quantum algorithm for solving linear systems of equations
- Quantum Amplitude Amplification and Estimation
- Quantum random access memory
- A roadmap for the computation of persistent homology
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Statistical topological data analysis using persistence landscapes
- A Grand Unification of Quantum Algorithms
- A new quantum ripple-carry addition circuit
- Persistent homology analysis of protein structure, flexibility and folding
- The Topology of the Cosmic Web in Terms of Persistent Betti Numbers
- Deterministic Preparation of Dicke States
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Persistent Laplacians: properties, algorithms and implications
- Demonstration of Topological Data Analysis on a Quantum Processor
- Hodge Laplacians on graphs
- Finding self-similar behavior in quantum many-body dynamics via persistent homology
- Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
- Complexity of Supersymmetric Systems and the Cohomology Problem
- Review of a Quantum Algorithm for Betti Numbers
- Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
- Limitations of Clustering Using Quantum Persistent Homology
- Proof of bijection for combinatorial number system