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 nO(1γlog1ε) with γ measuring the spectral gap of the combinatorial Laplacian and ε∈(0,1) the additive precision. In the case of a clique complex, the running time of our algorithm improves to (n/λmax)O(1γlog1ε) with λmax≥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, γ∈Ω(1) and k∈Ω(n) .
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 nO(1γlog1ε) with γ measuring the spectral gap of the combinatorial Laplacian and ε∈(0,1) the additive precision. In the case of a clique complex, the running time of our algorithm improves to (n/λmax)O(1γlog1ε) with λmax≥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, γ∈Ω(1) and k∈Ω(n) .
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
Recently, a classical algorithm for estimating the normalized Betti number of an arbitrary simplicial complex was proposed. Motivated by a quantum algorithm with a similar Monte Carlo structure and improved sample complexity, we give a more in-depth analysis of the sample complexity of this classical algorithm. To this end, we present bounds for the variance of the estimators used in the classical algorithm and show that the variance depends on certain combinatorial properties of the underlying simplicial complex. This new analysis leads us to propose an improvement to the classical algorithm which makes the "easy cases easier'', in that it reduces the sample complexity for simplicial complexes where the variance is sufficiently small. We show the effectiveness and limitations of these classical algorithms by considering Erdős-Renyi random graph models to demonstrate the existence of "easy" and "hard" cases. Namely, we show that for certain models our improvement almost always leads to a reduced sample complexity, and also produce separate regimes where the sample complexity for both algorithms is exponential.
Several quantum and classical Monte Carlo algorithms for Betti Number Estimation (BNE) on clique complexes have recently been proposed, though it is unclear how their performances compare. We review these algorithms, emphasising their common Monte Carlo structure within a new modular framework. We derive upper bounds for the number of samples needed to reach a given level of precision, and use them to compare these algorithms. By recombining the different modules, we create a new quantum algorithm with an exponentially-improved dependence in the sample complexity. We run classical simulations to verify convergence within the theoretical bounds and observe the predicted exponential separation, even though empirical convergence occurs substantially earlier than the conservative theoretical bounds.
Torsion detection in clique complexes is conditionally QMA1-hard
Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the kernel of a combinatorial Laplacian. Deciding whether a Betti number of a clique complex is nonzero is QMA1-hard, and remains so under a spectral gap promise on vertex-weighted graphs. Integral homology, however, contains information inaccessible to the Laplacian spectrum. A new part that appears in integral homology is \emph{torsion}: cycles that become boundaries only after being traversed several times, as in a projective plane or a Klein bottle. We provide a simple reduction that allows us to establish the first hardness results for the problem of detecting torsion. We attach to an arbitrary clique complex a fixed 31-vertex triangulation of the projective plane. The kth mod-2 Betti number of the input then reappears as 2-torsion two degrees up, while all rational homology disappears and every combinatorial Laplacian acquires a constant spectral gap. We conclude that detecting torsion in clique complexes of \emph{unweighted} graphs is NP-hard, even under a constant gap promise, and that it is QMA1-hard if mod-2 clique homology is.
Topological data analysis (TDA) is a fast-growing field that utilizes advanced tools from topology to analyze large-scale data. A central problem in topological data analysis is estimating the so-called Betti numbers of the underlying simplicial complex. While the difficulty of this problem has been established as NP-hard, previous works have showcased appealing quantum speedup. In this article, we provide an alternative method for estimating Betti numbers and normalized Betti numbers of given simplicial complex, based on some recent advances in quantum algorithm, specifically, quantum singular value transformation. Our method can be faster than the best-known classical method for finding Betti numbers, and interestingly, it can also find the Betti numbers of the complement graph to our original one. Comparing to the best known quantum algorithm, our method generally requires lower depth circuit, in trade-off for longer running time. Regarding normalized Betti numbers, our method could match the running time of best-known quantum method in the case of dense simplices.
We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis (qTDA). Under the classical planted clique conjecture, no randomized polynomial-time Betti number estimator achieves additive error below 21 with constant advantage. Under a new quantum planted clique conjecture that we introduce, the same conclusion holds for quantum polynomial-time algorithms. We also obtain related conditional hardness results for homology vanishing, additive approximations with larger error tolerances, preparation of simplex and harmonic states, cycle recovery, and counting eigenvalues at low energy. Our reduction clarifies the structural requirements for quantum advantage in TDA and provides a new lens to investigate the classical and quantum complexity of related problems.