Revised: November 3, 2021

Published: May 24, 2022

**Keywords:**quantum computing, quantum space complexity, span programs

**ACM Classification:**F.1.1, F.1.3

**AMS Classification:**81P68

**Abstract:**
[Plain Text Version]

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.