Skip to main navigation Skip to search Skip to main content

Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach

  • QuEra Computing Inc.
  • Stony Brook University

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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 languageEnglish
Article number1955
JournalQuantum
Volume9
DOIs
StatePublished - 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