Approximate Span Programs

QuICS Seminar

Stacey Jeffery (Caltech)
Wednesday, June 10, 2015 - 2:00pm
CSS 3100A

Span programs are a model of computation that completely characterize quantum query complexity, and have also been used in some cases to get upper bounds on quantum time complexity. Any span program can be converted to a quantum algorithm that, given an input x, decides whether x is "accepted" by the span program, or "rejected" by the span program.

We consider more general ways of using this model to design quantum algorithms, by relaxing the notion of which inputs are accepted and which inputs rejected by a particular span program. We describe two new types of algorithms that can be constructed from any span program. The first type of algorithm "approximately" evaluates the span program: given an input to the span program, it decides if the input is close to being accepted or far from being accepted. This allows span programs to be used in a natural way to solve property-testing-type problems. The second type of algorithm estimates the span program witness size of an input.

This talk is based on joint work with Tsuyoshi Ito.