  While quantum computers hold the promise of significant computational
speedups, the limited size of early quantum machines motivates the study of
space-bounded quantum computation. We relate the quantum space complexity of
computing a function f with one-sided error to the logarithm of its span
program size, a classical quantity that is well-studied in attempts to prove
formula size lower bounds.
  In the more natural bounded error model, we show that the amount of space
needed for a unitary quantum algorithm to compute f with bounded (two-sided)
error is lower bounded by the logarithm of its approximate span program size.
Approximate span programs were introduced in the field of quantum algorithms
but not studied classically. However, the approximate span program size of a
function is a natural generalization of its span program size.
  While no non-trivial lower bound is known on the span program size (or
approximate span program size) of any concrete function, a number of lower
bounds are known on the monotone span program size. We show that the
approximate monotone span program size of f is a lower bound on the space
needed by quantum algorithms of a particular form, called monotone phase
estimation algorithms, to compute f. We then give the first non-trivial lower
bound on the approximate span program size of an explicit function.
