A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity.

A span program for a function $f: \{0,1\}^n \rightarrow \{0,1\}$ consists of an ambient vector space $V$, target vector $z \in V$, and $2n$ subspaces $U^0_1, U^1_1, ... , U^0_n, U^1_n$. With the condition that:

$$ f(x) = 1 \; \text{if and only if} \; z \in \text{span}\{U^{x_1}_1, ... , U^{x_n}_n\} $$

The classical complexity measure on span programs is size: the sum of the dimensions of all $2n$ subspaces. The quantum complexity measure on span programs is witness size which (is slightly more subtle, but basically) the the norm of the vector that actual shows that $z$ is spanned or proves that it can't be (see here for a proper definition). In particular, we fix specific vectors to span the individual subspaces, and then a witness can be generated for each input by looking at the linear combination of vectors that match $z$, then we take max over all inputs.

To me, these two measures look very different. Are there known correspondences between the programs that minimize the measures? If we take the span program of minimal size, is it possible to pick a basis for the $2n$ subspaces to produce a span program of minimal witness size? Is the minimal span program measured by size the same as the minimal span program measured by witness size?

Related questions

Span programs, witness size, and certificate complexity

  • 4
    $\begingroup$ You mean span, not spam? $\endgroup$ Sep 26, 2011 at 8:02
  • 3
    $\begingroup$ "Minimal quantum spam program" got me interested; a paper for FUN 2012 obviously. $\endgroup$ Sep 26, 2011 at 10:47
  • $\begingroup$ @DaveClarke haha, well that's embarrassing, I've fixed it now. $\endgroup$ Sep 26, 2011 at 15:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.