← Introduction to Algorithmic Biology: Evolution as Algorithm

Hiding behind chaos and error in the double pendulum →

Span programs as a linear-algebraic representation of functions

June 8, 2019 by Artem Kaznatcheev 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 linear-algebraic 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 linear-algebraic 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 $|t\rangle$ in a vector space $V$ , and a collection of subspaces $V_{j,b} \subseteq V$ for $1 \leq j \leq n$ and $b \in \{0,1\}$ . For an input $x \in D$ , if $f(x) = 1$ then the target vector can be expressed as a linear combination of vectors in $\bigcup_{1 \leq j \leq n} V_{j,x_j}$ . For the classical complexity measures on span programs (size) the particular choice of bases for $V_{j,b}$ 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 $P$ consists of a “target” vector $|t\rangle$ in a finite-dimensional inner-product space $V$ over $\mathbb{C}$ , together with “input” vectors $|v_i\rangle \in V$ for $i \in I$ . Here the index set $I$ is
a disjoint union:

$I = I_{\text{free}} \sqcup \bigsqcup_{1 \leq j \leq n, b \in \{0,1\}} I_{j,b}$

$P$ corresponds to a function $f_P: \{0,1\}^n \rightarrow \{0,1\}$ , defined by:

$f_P(x) = \begin{cases} 1 & \text{if} \; |t\rangle \in \text{Span}\{|v_i\rangle | i \in I_{\text{free}} \sqcup \bigsqcup_{1 \leq j \leq n} I_{j,x_j} \} \\\ 0 & \text{otherwise} \end{cases}$

A span program is called strict if $I_{\text{free}} = \emptyset$ . In general, we can assume span programs are strict, a non-empty $I_{\text{free}}$ 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 $1 \leq j \leq n$ we have $V_{j,1} = \emptyset$ . For every monotone function there exists a monotone span program representing it and vice-versa. These programs also correspond to linear secret-sharing 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 $|I|$ , 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 $P$ . Let $A = \sum_{i \in I} |v_i\rangle\langle i|$ . For each input $x$ , let $I(x) = \sum_{1 \leq j \leq n} I_{j,x_j}$ and $\Pi(x) = \sum_{i \in I(x)} |i \rangle \langle i |$ , and

If $f_P(x) = 1$ , then there is a witness $|w\rangle$ satisfying $A\Pi(x)|w\rangle = |t\rangle$ . Let $\text{wsize}_x(P)$ be the minimum norm of any such witness:
$\text{wsize}_x(P) = \min_{\{|w\rangle: A\Pi(x)|w\rangle = |t\rangle\}} |||w\rangle||^2$
If $f_P(x) = 0$ , then there is a witness $|w'\rangle$ satisfying property B: $\langle t | w' \rangle = 1$ and $Pi(x)A^\dagger|w'\rangle = 0$ . Let

$\text{wsize}_x(P) = \min_\{|w'\rangle \; \text{with prop.}\; B\} ||A^\dagger |w'\rangle ||^2$

Let the witness size of $P$ be $\text{wsize}(P) = \max_{x} \text{wsize}_x(P)$ .

Note that there is a certain imprecision in how we specified a span program. In particular, if we replace the target vector $|t\rangle$ by $c|t\rangle$ ( $c \neq 0$ ), then we change the witness size by a factor of $|c|^2$ if $f_p(x) = 1$ or $1/|c|^2$ if $f_p(x) = 0$ . Thus we might as well have defined the witness size as:

$\sqrt{\max_{\{x:f_P(x) = 0\}} \text{wsize}_x(P) \max_{\{x:f_P(x) = 1\}} \text{wsize}_x(P)}$

However, we will see this is unnecessary since we can transform any span program into a canonical span program:

A span program $P$ is canonical if $V = \mathbb{C}^{|f^{-1}(0)|}$ , the target vector is $|t\rangle = \sum_{x \in f^{-1}(0)} |x\rangle$ , and for all $x \in f^{-1}(0)$ and $i \in I(x)$ , $\langle x | v_i \rangle = 0$ .

Using classical techniques [KW93] we can show that this does not increase our complexity measures:

A span program $P$ can be converted to a canonical span program $\hat{P}$ that computes the same function, with $\text{size}(\hat{P}) \leq \text{size}(P)$ and $\text{wsize}(\hat{P}) \leq \text{wsize}(P)$ . For all $x$ with $f_{P'}(x) = 0$ , $|x\rangle$ 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:

$\begin{aligned} \inf_{P:f_P = f} \text{wsize}(P) & = \inf_{m \in \mathbb{N}, |u_{xj}\rangle \in \mathbb{R}^m} \max_x \sum_{j} ||u_{xj}||^2 \\ & \text{s.t.}\; \sum_{j:x_j \neq y_j} \langle u_{xj} | u_{yj} \rangle = 1 \; \text{if} \; f(x) \neq f(y) \end{aligned}$

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:

$Adv^{\pm}(f) = \inf_{P:f_P = f} \text{wsize}(P)$

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:277-296, 2001.

[GP03] Anna Gal and Pavel Pudlak. A note on monotone complexity and the rank of matrices. Information Processing Letters, 87:321-326, 2003.

[KW93] Mauricio Karchmer and Avi Wigderson. On span programs. In Proc. of 8th IEEE Symp. Structure of Complexity Theory, pages 102-111, 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 544-551. IEEE, 2009, arXiv:0904.2759v1.

[RS08] Ben W. Reichardt and Robert Spalek. Span-program based quantum algorithm for evaluating formulas. In Proc. 40th ACM STOC, pages 103-112, 2008, arXiv:0710.2630.

Filed under Technical Tagged with cstheory, quantum information processing

About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.