A (simple) classical algorithm for estimating Betti numbers

Quantum 7, 1202 (2023).

https://doi.org/10.22331/q-2023-12-06-1202

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^{Oleft(frac{1}{sqrt{gamma}}logfrac{1}{varepsilon}right)}$ with $gamma$ measuring the spectral gap of the combinatorial Laplacian and $varepsilon 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)^{Oleft(frac{1}{sqrt{gamma}}logfrac{1}{varepsilon}right)}$ with $lambda_{max} geq 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)$.