Revised: November 3, 2021
Published: May 24, 2022
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.
Licensed under a Creative Commons Attribution License (CC-BY)