# Review of a Quantum Algorithm for Betti Numbers

arXiv: https://arxiv.org/abs/1906.07673 · HTML: https://mlsanity.com/paper/1906.07673/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2019.

## Built on by (most cited first, 3 of 3)

- [Quantum Topological Data Analysis with Linear Depth and Exponential Speedup](https://mlsanity.com/paper/2108.02811/) (2021)
- [Topological data analysis on noisy quantum computers](https://mlsanity.com/paper/2209.09371/) (2022)
- [Higher-order topological kernels via quantum computation](https://mlsanity.com/paper/2307.07383/) (2023)

## Abstract (arXiv)

We looked into the algorithm for calculating Betti numbers presented by Lloyd, Garnerone, and Zanardi (LGZ). We present a new algorithm in the same spirit as LGZ with the intent of clarifying quantum algorithms for computing Betti numbers. Our algorithm is simpler and slightly more efficient than that presented by LGZ. We present a thorough analysis of our algorithm, pointing out reasons that both our algorithm and that presented by LGZ do not run in polynomial time for most inputs. However, the algorithms do run in polynomial time for calculating an approximation of the Betti number to polynomial multiplicative error, when applied to some class of graphs for which the Betti number is exponentially large.