  Span programs are a model of computation that have been used to design
quantum algorithms, mainly in the query model. For any decision problem, there
exists a span program that leads to an algorithm with optimal quantum query
complexity, but finding such an algorithm is generally challenging.
  We consider new ways of designing quantum algorithms using span programs. We
show how any span program that decides a problem $f$ can also be used to decide
"property testing" versions of $f$, or more generally, approximate the span
program witness size, a property of the input related to $f$. For example,
using our techniques, the span program for OR, which can be used to design an
optimal algorithm for the OR function, can also be used to design optimal
algorithms for: threshold functions, in which we want to decide if the Hamming
weight of a string is above a threshold or far below, given the promise that
one of these is true; and approximate counting, in which we want to estimate
the Hamming weight of the input. We achieve these results by relaxing the
requirement that 1-inputs hit some target exactly in the span program, which
could make design of span programs easier.
  We also give an exposition of span program structure, which increases the
understanding of this important model. One implication is alternative
algorithms for estimating the witness size when the phase gap of a certain
unitary can be lower bounded. We show how to lower bound this phase gap in some
cases.
  As applications, we give the first upper bounds in the adjacency query model
on the quantum time complexity of estimating the effective resistance between
$s$ and $t$, $R_{s,t}(G)$, of $\tilde
O(\frac{1}{\epsilon^{3/2}}n\sqrt{R_{s,t}(G)})$, and, when $\mu$ is a lower
bound on $\lambda_2(G)$, by our phase gap lower bound, we can obtain $\tilde
O(\frac{1}{\epsilon}n\sqrt{R_{s,t}(G)/\mu})$, both using $O(\log n)$ space.
