<p>A span program is a linear-algebraic way of specifying a boolean function introduced <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=336536&amp;tag=1" rel="nofollow noreferrer">here</a> which has found recent application in quantum query complexity.</p>

<p>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:</p>

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

<p>The classical complexity measure on span programs is <em>size</em>: the sum of the dimensions of all $2n$ subspaces. The quantum complexity measure on span programs is <em>witness size</em> 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 <a href="http://www.computer.org/portal/web/csdl/doi/10.1109/FOCS.2009.55" rel="nofollow noreferrer">here</a> 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.</p>

<p>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?</p>

<h3>Related questions</h3>

<p><a href="https://cstheory.stackexchange.com/q/5701/1037">Span programs, witness size, and certificate complexity</a></p>

CC BY-SA 3.0
2011-09-26T08:02:09.800Z
You mean span, not spam?
Dave Clarke
CC BY-SA 3.0
2011-09-26T10:47:04.827Z
"Minimal quantum spam program" got me interested; a paper for FUN 2012 obviously.
Jukka Suomela
CC BY-SA 3.0
2011-09-26T15:09:33.333Z
@DaveClarke haha, well that's embarrassing, I've fixed it now.
Artem Kaznatcheev
<cc.complexity-theory><quantum-computing><linear-algebra><query-complexity>
Are the minimal quantum and classical span programs the same?
Artem Kaznatcheev
# Are the minimal quantum and classical span programs the same?

(Asked by: username_0 on 2011-09-26)

A span program is a linear-algebraic way of specifying a boolean function introduced [here](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=336536&tag=1) 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](http://www.computer.org/portal/web/csdl/doi/10.1109/FOCS.2009.55) 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](https://cstheory.stackexchange.com/q/5701/1037)

**Tags:** cc.complexity-theory, quantum-computing, linear-algebra, query-complexity
> **Comments:**
> **username_1**: You mean span, not spam?  
> **username_2**: "Minimal quantum spam program" got me interested; a paper for FUN 2012 obviously.  
> **username_0**: @DaveClarke haha, well that's embarrassing, I've fixed it now.  

---

## 0 answers

