Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 27, 2015 | Submitted
Report Open

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. In this work, we consider new ways of designing quantum algorithms using span programs. We show how any span program that decides a problem f can also be used to decide "property testing" 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. For example, using our techniques, the span program for OR, which can be used to design an optimal algorithm for the OR function, can also be used to design optimal algorithms for: threshold functions, in which we want to decide if the Hamming weight of a string is above a threshold, or far below, given the promise that one of these is true; and approximate counting, in which we want to estimate the Hamming weight of the input up to some desired accuracy. 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 eÕ(^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 Õ(1/є n √R_(s,t)(G)/µ) for estimating effective resistance, also using O(log n) space.

Additional Information

The authors would like to thank David Gosset, Shelby Kimmel, Ben Reichardt, and Guoming Wang for useful discussions about span programs. We would especially like to thank Shelby Kimmel for valuable feedback and suggestions on an earlier draft of this paper. Finally, S.J. would like to thank Moritz Ernst for acting as a sounding board throughout the writing of this paper.

Attached Files

Submitted - 1507.00432v1.pdf


Files (388.3 kB)
Name Size Download all
388.3 kB Preview Download

Additional details

August 20, 2023
August 20, 2023