A (simple) classical algorithm for estimating Betti numbers

Abstract

We describe a simple algorithm for estimating the $k$-th normalized Betti number of a simplicial complex over $n$ elements using the path integral Monte Carlo method. For a general simplicial complex, the running time of our algorithm is $n^{O\left(\frac{1}{\sqrt{\gamma }}\log \frac{1}{\epsilon }\right)}$ with $\gamma$ measuring the spectral gap of the combinatorial Laplacian and $\epsilon \in (0,1)$ the additive precision. In the case of a clique complex, the running time of our algorithm improves to ${\left(n/{\lambda }_{\max }\right)}^{O\left(\frac{1}{\sqrt{\gamma }}\log \frac{1}{\epsilon }\right)}$ with ${\lambda }_{\max }\ge k$, where ${\lambda }_{\max }$ is the maximum eigenvalue of the combinatorial Laplacian. Our algorithm provides a classical benchmark for a line of quantum algorithms for estimating Betti numbers. On clique complexes it matches their running time when, for example, $\gamma \in \Omega (1)$ and $k\in \Omega (n)$.

v3: final version, accepted to Quantum

References in corpus (3)

• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits
• Topological data analysis on noisy quantum computers
• Quantum Persistent Homology

Cited by in corpus (6)

• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Quantum and classical query complexities of functions of matrices
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Provable quantum speedups for computing persistence in topological data analysis
• Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes
• Holey graphs: very large Betti numbers are testable