Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach

Abstract

Topological data analysis has emerged as a powerful tool for analyzing large-scale data. An abstract simplicial complex, in principle, can be built from data points, and by using tools from homology, topological features could be identified. Given a simplex, an important feature is called the Betti numbers, which roughly count the number of `holes' in different dimensions. Calculating Betti numbers exactly can be $\#$P-hard, and approximating them can be NP-hard, which rules out the possibility of any generic efficient algorithms and unconditional exponential quantum speedup. Here, we explore the specific setting of a triangulated manifold. In contrast to most known methods to estimate Betti numbers, which rely on homology, we exploit the `dual' approach, namely, cohomology, combining the insight of the Hodge theory and de Rham cohomology. Our proposed algorithm can calculate its $r$-th normalized Betti number ${\hat{I}}_r^2/|S_r|$ up to some additive error $\hat{I}\mu$ with running time $\mathcal{O}(\frac{\log (|S_r^K||S_{r+1}^K|)}{\hat{I}{\mu }^2}\log (\log |S_r^K|)(r\log |S_r^K|\left)\right)$, where $|S_r|$ is the number of $r$-simplexes in the given complex. For the estimation of $r$-th Betti number ${\hat{I}}_r^2$ to a chosen multiplicative accuracy $\hat{I}{\mu }^{\prime }$, our algorithm has complexity $\mathcal{O}\left(\frac{\log (|S_r^K||S_{r+1}^K|)}{\hat{I}{\mu }^{\prime 2}}\right(\frac{\hat{I}“}{{\hat{I}}_r^2}{)}^2(\log |S_r^K|)\log (r\log |S_r^K|))$, where $\hat{I}“\le |S_r^K|$ can be chosen. A detailed analysis is provided, showing that our cohomology framework can even perform exponentially faster than previous homology methods in several regimes. In particular, our method is most effective when ${\hat{I}}_r^2\ll |S_r^K|$, which can offer more flexibility and practicability than existing quantum algorithms that achieve the best performance in the regime ${\hat{I}}_r^2\approx |S_r^K|$.