

























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γ}\log\frac{1}{\varepsilon}\right)}$ with $γ$ 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/λ_{\max}\right)^{O\left(\frac{1}{\sqrtγ}\log\frac{1}{\varepsilon}\right)}$ with $λ_{\max} \geq 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, $γ\in Ω(1)$ and $k \in Ω(n)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。