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 n^Oleft(frac1√γlogfrac1varepsilonright) with γ measuring the spectral gap of the combinatorial Laplacian and varepsilon ∈ (0,1) the additive precision. In the case of a clique complex, the running time of our algorithm improves to left(n/λmaxright)^Oleft(frac1√γlogfrac1varepsilonright) 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, γ ∈ Omega(1) and k ∈ Omega(n).