A (simple) classical algorithm for estimating Betti numbers

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 nO(1γlog⁡1ε) with γ measuring the spectral gap of the combinatorial Laplacian and ε∈(0,1) the additive precision. In the case of a clique complex, the running time of our algorithm improves to (n/λmax)O(1γlog⁡1ε) with λmax≥k, where λ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, γ∈Ω(1) and k∈Ω(n).