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 ${\beta }_r/|S_r|$ up to some additive error $\epsilon$ with running time $\mathcal{O}(\frac{\log (|S_r^K||S_{r+1}^K|)}{{\epsilon }^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 ${\beta }_r$ to a chosen multiplicative accuracy ${\epsilon }^{\prime }$, our algorithm has complexity $\mathcal{O}\left(\frac{\log (|S_r^K||S_{r+1}^K|)}{{\epsilon }^{\prime 2}}\right(\frac{\Gamma }{{\beta }_r}{)}^2(\log |S_r^K|)\log (r\log |S_r^K|))$, where $\Gamma \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 ${\beta }_r\ll |S_r^K|$, which can offer more flexibility and practicability than existing quantum algorithms that achieve the best performance in the regime ${\beta }_r\approx |S_r^K|$.

References in corpus (32)

• Quantum algorithm for solving linear systems of equations
• Quantum machine learning in feature Hilbert spaces
• Quantum Circuit Learning
• Quantum principal component analysis
• Evaluating analytic gradients on quantum hardware
• Circuit-centric quantum classifiers
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• The effect of data encoding on the expressive power of variational quantum machine learning models
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Efficient quantum algorithms for simulating sparse Hamiltonians
• The quest for a Quantum Neural Network
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Toward the first quantum simulation with quantum speedup
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• On the relationship between continuous- and discrete-time quantum walk
• Hamiltonian simulation with nearly optimal dependence on all parameters
• High-order quantum algorithm for solving linear differential equations
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Nearly optimal lattice simulation by product formulas
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicator
• Towards quantum advantage via topological data analysis
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Quantum algorithms for approximate function loading
• Approximate Quantum Circuit Synthesis using Block-Encodings
• Fast estimation of approximate matrix ranks using spectral densities
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
• An Improved Method for Quantum Matrix Multiplication
• A (simple) classical algorithm for estimating Betti numbers
• Clique Homology is QMA1-hard

Cited by in corpus (2)

• The topology of data hides in quantum thermal states
• Provable quantum speedups for computing persistence in topological data analysis