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 instead of the general TDA. In contrast to most known quantum algorithms to estimate (normalized) Betti numbers, which rely on homology, we exploit the ‘dual’ approach, namely, cohomology, combining the insight of the Hodge theory and de Rham cohomology. By first randomizing the so-called r-forms as vectors, we leverage several recipes from the block-encoding framework to deform them to their corresponding hamornic forms. Then the r-th Betti number can be found by examining the number of linearly independent harmonic forms. A detailed analysis is provided, showing that our cohomology framework can perform exponentially faster than previous homology methods in several regimes. In particular, our method can be effective when βr ≪ |SrK |, which can offer more flexibility and practicability than existing quantum algorithms that achieve the best performance in the regime βr ≈ |SrK |.
| Original language | English |
|---|---|
| Article number | 1955 |
| Journal | Quantum |
| Volume | 9 |
| DOIs | |
| State | Published - 2025 |
Fingerprint
Dive into the research topics of 'Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver