Theory of Computing ------------------- Title : Span Programs and Quantum Space Complexity Authors : Stacey Jeffery Volume : 18 Number : 11 Pages : 1-49 URL : https://theoryofcomputing.org/articles/v018a011 Abstract -------- 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 at least the logarithm of its _approximate span program size_ over the reals. Approximate span programs have been 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 explicit 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 monotone span program size of an explicit function. ----------------- A conference version of this paper appeared in the Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020.