Approximate span programs

Span programs are a model of computation that have been used to design quantum algorithms, mainly in the query model. It is known that for any decision problem, there exists a span program that leads to an algorithm with optimal quantum query complexity, however finding such an algorithm is generally challenging. We consider new ways of designing quantum algorithms using span programs. We show how any span program that decides a function f can also be used to decide “threshold” versions of the function f, or more generally, approximate a quantity called the span program witness size, which is some property of the input related to f. We achieve these results by relaxing the requirement that 1-inputs hit some target exactly in the span program, which could potentially make design of span programs significantly easier. In addition, we give an exposition of span program structure, which increases the general understanding of this important model. One implication of this is alternative algorithms for estimating the witness size when the phase gap of a certain unitary can be lower bounded. We show how to lower bound this phase gap in certain cases. As an application, we give the first upper bounds in the adjacency query model on the quantum time complexity of estimating the effective resistance between s and t, R s , t ( G ) . For this problem we obtain O ~ ( 1 ε 3 / 2 n R s , t ( G ) ) , using O ( log ⁡ n ) space. In addition, when μ is a lower bound on λ 2 ( G ) , by our phase gap lower bound, we can obtain an upper bound of O ~ ( 1 ε n R s , t ( G ) / μ ) for estimating effective resistance, also using O ( log ⁡ n ) space