  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 the combinatorial Laplacian, our algorithm is an
instance of the generic Incremental Algorithm for computing Betti numbers that
incrementally adds simplices to the simplicial complex and tests whether or not
they create a cycle. In contrast to existing quantum algorithms for computing
Betti numbers that work best when the complex has close to the maximal number
of simplices, our algorithm works best for sparse complexes. To test whether a
simplex creates a cycle, we introduce a quantum span-program algorithm. We show
that the query complexity of our span program is parameterized by quantities
called the effective resistance and effective capacitance of the boundary of
the simplex. Unfortunately, we also prove upper and lower bounds on the
effective resistance and capacitance, showing both quantities can be
exponentially large with respect to the size of the complex, implying that our
algorithm would have to run for exponential time to exactly compute Betti
numbers. However, as a corollary to these bounds, we show that the spectral gap
of the combinatorial Laplacian can be exponentially small. As the runtime of
all previous quantum algorithms for computing Betti numbers are parameterized
by the inverse of the spectral gap, our bounds show that all quantum algorithms
for computing Betti numbers must run for exponentially long to exactly compute
Betti numbers. Finally, we prove some novel formulas for effective resistance
and effective capacitance to give intuition for these quantities.
