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.