An Incremental Span-Program-Based Algorithm and the Fine Print of Quantum Topological Data Analysis

Mitchell Black, William Maxwell, Amir Nayyeri

We introduce a new quantum algorithm for computing the Betti numbers of a simplicial complex. In contrast to previous quantum algorithms that work by estimating the eigenvalues of…