Span programs as a linearalgebraic representation of functions
June 8, 2019 1 Comment
I feel like TheEGG has been a bit monotone in the sort of theoretical computer science that I’ve been writing about recently. In part, this has been due to time constraints and the pressure of the weekly posting schedule (it has now been over a year with a post every calendar week); and in part due to my mind being too fixated on algorithmic biology.
So for this week, I want to change things up a bit. I want to discuss some of the math behind a success of cstheory applied to nature: quantum computing. It’s been six years since I blogged about quantum query complexity and the negative adversary method for lower bounding it. And it has been close to 8 years since I’ve worked on the topic.
But I did promise to write about span programs — a technique used to reason about query complexity. So in this post, I want to shift gears to quantum computing and discuss span programs. I doubt this is useful to thinking about evolution, but it never hurts to discuss a cool linearalgebraic representation of functions.
I started writing this post for the CSTheory Community Blog. Unfortunately, that blog is largely defunct. So, after 6 years, I decided to post on TheEGG instead.
Please humour me, dear reader.
Span programs are a linearalgebraic representation of functions. They originated in the work of Karchmer and Wigderson [KW93] on classical complexity, and were introduced into quantum computing by Reichardt and Spalek [RS08] in the context of formulate evaluation. A span program consists of a target in a vector space , and a collection of subspaces for and . For an input , if then the target vector can be expressed as a linear combination of vectors in . For the classical complexity measures on span programs (size) the particular choice of bases for does not matter, but for the quantum witness size it is important to fix the set of “input vectors” that span each subspace.
Formally:
A span program consists of a “target” vector in a finitedimensional innerproduct space over , together with “input” vectors for . Here the index set is
a disjoint union:
corresponds to a function , defined by:
A span program is called strict if . In general, we can assume span programs are strict, a nonempty is only useful for optimizing some algorithmic considerations. In the classical literature only strict span programs were considered [KW93,Gal01,GP03]. In fact, the classical literature considers even more restrictive programs such
as monotone span programs [Gal01,GP03]. A span program is monotone if for all we have . For every monotone function there exists a monotone span program representing it and viceversa. These programs also correspond to linear secretsharing schemes, but as of 2011, were not yet studied from the quantum interpretation (have they since, dear reader?). Unlike monotone circuits, monotone span programs are believed to be less restrictive with respect to the natural classical notion of span program complexity.
The classical notion of complexity for span programs is called size. The size of a span program is the number of input vectors , and the size of a function is then the minimum size over all span programs that represent the function [KW93]. For the correspondence between span programs and quantum query complexity, however, we have to consider a different measure of complexity known as witness size [RS08].
Consider a span program . Let . For each input , let and , and
 If , then there is a witness satisfying . Let be the minimum norm of any such witness:

If , then there is a witness satisfying property B: and . Let
Let the witness size of be .
Note that there is a certain imprecision in how we specified a span program. In particular, if we replace the target vector by (), then we change the witness size by a factor of if or if . Thus we might as well have defined the witness size as:
However, we will see this is unnecessary since we can transform any span program into a canonical span program:
A span program is canonical if , the target vector is , and for all and , .
Using classical techniques [KW93] we can show that this does not increase our complexity measures:
A span program can be converted to a canonical span program that computes the same function, with and . For all with , itself is an optimal witness.
This simplifies the definition of witness size, and we can write down an optimization problem to solve for the smallest witness size of a function, as:
Notice the similarity of the above equation and the dual of the adversary method. The similarity is no coincidence: the former is the dual of the negative adversary method:
For a proof, I direct the interested reader to Ref.[Rei09].
References
[Gal01] Anna Gal. A characterization of span program size and improved lower bounds for monotone span programs. Computational Complexity, 10:277296, 2001.
[GP03] Anna Gal and Pavel Pudlak. A note on monotone complexity and the rank of matrices. Information Processing Letters, 87:321326, 2003.
[KW93] Mauricio Karchmer and Avi Wigderson. On span programs. In Proc. of 8th IEEE Symp. Structure of Complexity Theory, pages 102111, 1993.
[Rei09] Ben W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 544551. IEEE, 2009, arXiv:0904.2759v1.
[RS08] Ben W. Reichardt and Robert Spalek. Spanprogram based quantum algorithm for evaluating formulas. In Proc. 40th ACM STOC, pages 103112, 2008, arXiv:0710.2630.
Pingback: Closing the gap between quantum and deterministic query complexity for easy to certify total functions  Theory, Evolution, and Games Group