A (simple) classical algorithm for estimating Betti numbers

Understand

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}{\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)^{O\left(\frac{1}{\sqrt{\gamma}}\log\frac{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.