Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach

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 β r / | S r | up to some additive error ϵ with running time O ( log ⁡ ( | S r K | | S r + 1 K | ) ϵ 2 log ⁡ ( log ⁡ | S r K | ) ( r log ⁡ | S r K | ) ) , where | S r | is the number of r -simplexes in the given complex. For the estimation of r -th Betti number β r to a chosen multiplicative accuracy ϵ ′ , our algorithm has complexity O ( log ⁡ ( | S r K | | S r <mm