Quantum algorithm for persistent Betti numbers and topological data analysis

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.

27 pages; Accepted in Quantum

References in corpus (10)

• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• A Grand Unification of Quantum Algorithms
• A new quantum ripple-carry addition circuit
• Persistent homology analysis of protein structure, flexibility and folding
• Persistent Laplacians: properties, algorithms and implications
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
• Complexity of Supersymmetric Systems and the Cohomology Problem
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Limitations of Clustering Using Quantum Persistent Homology

Cited by in corpus (4)

• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Topological data analysis and machine learning
• A (simple) classical algorithm for estimating Betti numbers
• Quantum Persistent Homology for Time Series