A Caltech Library Service

Approximate Span Programs

Ito, Tsuyoshi and Jeffery, Stacey (2015) Approximate Span Programs. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
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.
Record Number:CaltechAUTHORS:20151027-093446138
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:61543
Deposited On:27 Oct 2015 19:12
Last Modified:03 Oct 2019 09:09

Repository Staff Only: item control page