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^{O(\frac{1}{\sqrt{\gamma }}\log \frac{1}{\epsilon })}$ 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\mathrm{/}{\lambda }_{\max }\right)}^{O(\frac{1}{\sqrt{\gamma }}\log \frac{1}{\epsilon })}$ 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 \mathrm{\Omega }(1)$ and $k\in \mathrm{\Omega }(n)$.