%% Theory of Computing
%% File: v008a013.tex
%% Publication date: July 7, 2012
%% Authors: Ben Reichardt and Robert Spalek
%
%
%
%

%

%
%
%
%
%
%
%
%
%
%
%
%
%

\documentclass{toc}

%
%
\tocdetails{%
volume=8, number=13, year=2012, firstpage=291,
%
received={September 22, 2008},
revised={October 5, 2011},
published={July 7, 2012},
doi={10.4086/toc.2012.v008a013}
}
%

%
%
\usepackage{subfigure}
\usepackage{multirow}

\def\place #1#2#3{\mspace{#2}\makebox[0pt]{\raisebox{#3}{#1}}\mspace{-#2}}	%

\newcommand{\bra}[1]{\langle#1|}
\newcommand{\ket}[1]{|#1\rangle}
\newcommand{\braket}[2]{\langle#1|#2\rangle}
\newcommand{\ketbra}[2]{\ket{#1}\!\bra{#2}}
\newcommand{\abs}[1]{\lvert #1\rvert}
\newcommand{\norm}[1]{\| #1 \|}
\newcommand{\eps}{{\epsilon}}
\newcommand{\identity}{\ensuremath{\boldsymbol{1}}} %

\newcommand{\B}{{\{0,1\}}}	%
\newcommand\cL {{\mathcal L}}
\newcommand\cD {{\mathcal D}}
\DeclareMathOperator{\abst}{\operatorname{abs}}

%
\newcommand{\ADV} {\mathrm{Adv}}
\newcommand{\ADVpm} {\ADV^\pm}
\newcommand{\gateset}{\mathcal{S}}
\newcommand\biadj {B}	%

\DeclareMathOperator{\MAJ}{{\operatorname{MAJ}_3}}
\DeclareMathOperator{\EQUAL}{{\operatorname{EQUAL}}}
\DeclareMathOperator{\EXACT}{{\operatorname{EXACT}}}

\newcommand\adjoint{\dagger} %
\newcommand\alto {o}
\newcommand\Deltam {{\overline{\Delta}}}
\newcommand\Pim {{\overline{\Pi}}}
\newcommand\VV {\widehat{V}}

\newcommand{\ri} {r} %
\newcommand{\rj} {\tilde{r}}
\newcommand{\si} {s}
\newcommand{\sj} {\tilde{s}}
\newcommand{\Ui} {z} %
\newcommand{\Uj} {\tilde{z}}
\newcommand{\abi} {\sigma} %
\newcommand{\abj} {\tilde{\sigma}}

%
\newcommand\ACJ {{C}} %
\newcommand{\restrict}[2] {{#1}_{{#2}}} %
\newcommand\cp {{{y}}} %
\newcommand\cm {{\bar{y}}} %
\newcommand\cpp {{{Y}}} %
\newcommand\cmm {{\bar{Y}}} %
%
\newcommand\dcm {{(\Deltam \cm)}} %
\newcommand\dcmm {{\cmm_\Deltam}} %
\newcommand\DeltaXDelta  {{X_\Delta}} %
\newcommand\DeltamXDeltam  {{X_\Deltam}} %
\newcommand\XDeltaSchur {{( X / \DeltaXDelta )}}

\newcommand\resinv {{-1}} %

\DeclareMathOperator{\Span}{\operatorname{Span}}
\DeclareMathOperator{\Range}{\operatorname{Range}}
\DeclareMathOperator{\Kernel}{\operatorname{Ker}}
\DeclareMathOperator{\poly}{\operatorname{poly}}

%
\DeclareMathOperator{\wsizeop}{{\operatorname{wsize}}}		%
\newcommand{\wsize}[1]{{\wsizeop({#1})}}
\newcommand{\wsizeS}[2]{{\wsizeop_{#2}({#1})}}
\newcommand{\wsizex}[2]{{\wsizeop({#1},{#2})}}
\newcommand{\wsizexS}[3]{{\wsizeop_{#3}({#1},{#2})}}
\newcommand\Ifree{I_\mathrm{free}}		%

\newcommand{\hugelpar}[1]{\left(\vbox to #1{}\right.}
\newcommand{\hugerpar}[1]{\left.\vbox to #1{}\right)}
\newcounter{sprows}
\newcounter{spcols}
\newlength{\spheight}
\newlength{\spraise}
\newcommand{\spleft}[2][0pt]{\multirow{\value{sprows}}{*}{%
	\vbox to \spraise{\vss\hbox{$#2 \hugelpar{\spheight}\hskip -#1$}\vss}}}
\newcommand{\spright}[2][0pt]{\multirow{\value{sprows}}{*}{%
	\vbox to \spraise{\vss\hbox{\hskip -#1 $\hugerpar{\spheight} #2$}\vss}}}

\newcommand{\eqnref}[1]{\hyperref[#1]{{(\ref*{#1})}}}
\newcommand{\thmref}[1]{\hyperref[#1]{{Theorem~\ref*{#1}}}}
\newcommand{\lemref}[1]{\hyperref[#1]{{Lemma~\ref*{#1}}}}
\newcommand{\corref}[1]{\hyperref[#1]{{Corollary~\ref*{#1}}}}
\newcommand{\propref}[1]{\hyperref[#1]{{Proposition~\ref*{#1}}}}
\newcommand{\defref}[1]{\hyperref[#1]{{Definition~\ref*{#1}}}}
%
\newcommand{\figref}[1]{\hyperref[#1]{{Figure~\ref*{#1}}}}
\newcommand{\tabref}[1]{\hyperref[#1]{{Table~\ref*{#1}}}}
\newcommand{\remref}[1]{\hyperref[#1]{{Remark~\ref*{#1}}}}
\newcommand{\appref}[1]{\hyperref[#1]{{Appendix~\ref*{#1}}}}
\newcommand{\claimref}[1]{\hyperref[#1]{{Claim~\ref*{#1}}}}
\newcommand{\exampleref}[1]{\hyperref[#1]{{Example~\ref*{#1}}}}

\newcommand{\argmin}{\operatornamewithlimits{arg\ min}}
\allowdisplaybreaks[1]
%



%
\runningtitle{Span-Program-Based Quantum Algorithm for Evaluating Formulas}

%
\tocpdftitle{Span-Program-Based Quantum Algorithm for Evaluating Formulas}


\runningauthor{Ben W. Reichardt and Robert {\v S}palek}
\copyrightauthor{Ben W. Reichardt and Robert {\v S}palek}

\tocpdfauthor{Ben W. Reichardt, Robert Spalek}

\begin{document}

\begin{frontmatter}[classification=text]
\title{Span-Program-Based Quantum Algorithm for Evaluating Formulas}

\author[ben]{Ben W. Reichardt}%
\author[robert]{Robert {\v S}palek}%

%
\begin{abstract}
We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (\eg, NAND, 3-majority).  The algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense.

The main new tool is a correspondence between a classical linear-algebraic model of computation, ``span programs,'' and weighted bipartite graphs.  A span program's evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph.  A quantum computer can therefore evaluate the span program by applying spectral estimation to the graph.  

For example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization of randomized alpha-beta pruning is known to be suboptimal.  In contrast, our algorithm generalizes the optimal quantum AND-OR formula evaluation algorithm and is optimal for evaluating the balanced ternary majority formula.  
\end{abstract}


%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

%
\tocacm{F.1.1, F.2.2} 
%
%
%
%
\tocams{81P68, 68Q05, 68Q12}
%
%
%

%
\tockeywords{span programs, quantum computation, %
query complexity, formula evaluation}

\end{frontmatter}




\section{Introduction}
\nobreak

A formula $\varphi$ on gate set $\gateset$ and of size $N$ is a tree with $N$ leaves, such that each internal node is a gate from $\gateset$ on its children.  The read-once formula evaluation problem is to evaluate $\varphi(x)$ given oracle access to the input string $x = x_1 x_2 \ldots x_N$.  An optimal, $O(\sqrt N)$-query quantum algorithm is known to evaluate ``approximately balanced'' formulas over the gates $\gateset = \{ \text{AND, OR, NOT} \}$~\cite{AmbainisChildsReichardtSpalekZhang07andor}.  We develop an optimal quantum algorithm for evaluating balanced formulas over a greatly extended gate set.  The notion of balance is technical, but includes as a special case layered formulas in which gates at the same depth are all equal.  

The idea of our algorithm is to consider a weighted graph $G(\varphi)$ obtained by replacing each gate of the formula $\varphi$ with a small gadget subgraph, and possibly also duplicating subformulas.  \figref{f:example} has several examples.  We relate the evaluation of $\varphi$ to the presence or absence of small-eigenvalue eigenvectors of the weighted adjacency matrix $A_{G(\varphi)}$ that are supported on the root vertex of $G(\varphi)$.  The quantum algorithm runs spectral estimation to either detect these eigenvectors or not, and therefore to evaluate $\varphi$.  

As a special case, for example, our algorithm implies: 

\begin{theorem} \label{t:balancedmajority}
A balanced ternary majority $(\MAJ)$ formula of depth $d$, on $N = 3^d$ inputs, can be evaluated by a quantum algorithm with bounded error using $O(2^d)$ oracle queries, which is optimal.  
\end{theorem}

\noindent The classical complexity of evaluating this formula is $\Omega((5/2)^d)$, and the previous best quantum algorithm, from~\cite{AmbainisChildsReichardtSpalekZhang07andor}, uses $O(\sqrt{5}{}^d)$ queries.  

\begin{figure}
\centering
\subfigure{\label{f:notsubstitution}\includegraphics[scale=.52]{notsubstitution}}
\quad
\subfigure{\includegraphics[scale=.52]{equalsubstitution}}
\quad
\subfigure{\includegraphics[scale=.52]{orsubstitution}}
\quad
\subfigure{\includegraphics[scale=.52]{majsubstitution}}
\caption{To convert a formula $\varphi$ to the corresponding graph $G(\varphi)$, we recursively apply substitution rules starting at the root to convert each gate into a gadget subgraph.  Some of the rules are shown here, except with the edge weights not indicated.  The dangling edges at the top and bottom of each gadget are the input edges and output edge, respectively.  To compose two gates, the output edge of one is identified with an input edge of the next (see \figref{f:maj3ofmaj3}).} \label{f:example}
\end{figure}

The graph gadgets themselves are derived from ``span programs''~\cite{KarchmerWigderson93span}, establishing a new connection between span programs and quantum algorithms.  The span program computational model has been used previously in classical complexity theory to prove lower bounds on formula size~\cite{KarchmerWigderson93span, BabaiGalWigderson99superpolyspanprogram} and monotone span programs are related to linear secret-sharing schemes~\cite{BeimelGalPaterson96spanprogram}.  (Most, though not all~\cite{AllenderBealsOgihara99span}, applications are over finite fields, whereas we use the definition over $\C$.)  Work subsequent to this paper has shown that span programs are equivalent to quantum query algorithms~\cite{Reichardt09spanprogram-arxivandfocs}.  


\paragraph{Classical and quantum background}

The formula evaluation problem has been well-studied in the classical computer model.  Classically, the case $\gateset = \{ \text{NAND} \}$ is best understood.  A formula with only NAND gates is equivalent to one with alternating levels of AND and OR gates, a so-called ``AND-OR formula,'' also known as a read-once function or a two-player game tree.  Using randomized alpha-beta pruning, one can compute the value of a balanced binary AND-OR formula with zero error in expected time $O(N^{\log_2[(1 + \sqrt{33})/4]}) = O(N^{0.753\ldots})$~\cite{snir:dec, sw:and-or}, and this is optimal even for bounded-error algorithms~\cite{santha:and-or}.  Other formulas have different query complexities; for example, evaluating a single OR gate with $N$ inputs needs $\Theta(N)$ oracle queries.  The best general lower bound of $\Omega(N^{0.51})$~\cite{HeimanWigderson91generalANDOR} has recently been improved to $\Omega(N^{0.746})$~\cite{Amano11andorlower}.  

If we allow the use of a quantum computer with coherent oracle access to the input, however, then the situation is simpler; $\Theta(\sqrt N)$ queries are necessary and sufficient to evaluate {\emph{any}} $\{ \text{AND, OR, NOT} \}$ formula with bounded error.  The general lower bound is due to~\cite{bs:q-read-once}.  For the upper bound, in one extreme case, Grover search~\cite{Grover96search, Grover96searchtime} evaluates an OR gate of degree~$N$ using $O(\sqrt N)$ oracle queries.  In the other extreme case, Farhi, Goldstone and Gutmann devised a breakthrough algorithm for evaluating the depth-$(\log_2 N)$ balanced binary AND-OR formula using $N^{1/2+o(1)}$ queries~\cite{fgg:and-or, ccjy:and-or}.  Ambainis et al.~\cite{AmbainisChildsReichardtSpalekZhang07andor} improved this to $O(\sqrt{N})$ queries, even for ``approximately balanced'' formulas, and also extended the algorithm to arbitrary $\{\text{AND, OR, NOT}\}$ formulas with $N^{\frac12 + o(1)}$ queries and time after a preprocessing step.  More recent work has given a general $O(\sqrt N)$-query upper bound~\cite{Reichardt10advtight, Reichardt09andorfaster}.  

This paper shows other nice features of the formula evaluation problem in the quantum computer model.  
Classically, with the exception of $\{\text{NAND}\}$, $\{\text{NOR}\}$ and a few trivial cases like $\{\text{PARITY}\}$, most gate sets are poorly understood.  In 1986, Boppana asked the complexity of evaluating the balanced, depth-$d$ ternary majority ($\MAJ$) function~\cite{sw:and-or}, and today the complexity is only known to lie between $\Omega((5/2)^d)$ and $O((2.6537\ldots)^d)$~\cite{JayramKumarSivakumar03majority, MagniezNayakSanthaXiao10majority}.  In particular, the na{\" i}ve generalization of randomized alpha-beta pruning---recursively evaluate two random immediate subformulas and then the third if they disagree---runs in expected time $O((8/3)^d)$ and is suboptimal.  This suggests that the balanced ternary majority function is significantly different from the balanced $k$-ary NAND function, for which randomized alpha-beta pruning is known to be optimal~\cite{sw:and-or}.  In contrast, we show that the optimal {quantum} algorithm of~\cite{AmbainisChildsReichardtSpalekZhang07andor} does extend to give an optimal $O(2^d)$-query algorithm for evaluating the balanced ternary majority formula.  Moreover, the algorithm also generalizes to a significantly larger gate set $\gateset$.  


\paragraph{Subsequent work}
The graph gadgets we use are derived from constant-size span programs, but in the conference version of this article~\cite{ReichardtSpalek08spanprogram} we speculated that ``larger span programs could directly give useful new quantum algorithms.''  Later work has borne this out.  Based on span programs, quantum algorithms have been developed for matrix rank~\cite{Belovs11rank}, various subgraph-detection and related problems~\cite{Belovs11triangle, Zhu11learninggraph, LeeMagniezSantha11learninggraph, BelovsReichardt12connectivity}, graph collision~\cite{GavinskyIto12graphcollision}, the $k$-distinctness problem under a certain promise~\cite{BelovsLee11learninggraph}, and further formula-evaluation problems~\cite{Reichardt09andorfaster, Reichardt09unbalancedformula, Reichardt10advtight, ZhanKimmelHassidim11spanprogram, Kimmel11adversary}.  For formula evaluation, the quantum query complexity of arbitrary read-once formulas has been characterized, with no gate set restrictions or balance condition needed.  

In fact, span programs have been shown to be equivalent to quantum query algorithms~\cite{Reichardt09spanprogram-arxivandfocs, Reichardt10advtight, LeeMittalReichardtSpalekSzegedy11stateconversion}.  Formally, the general adversary lower bound on quantum query complexity exactly equals the least span program witness size, which via an algorithm upper bounds query complexity to within a constant factor.  (The general adversary bound is a semi-definite program, which can be solved to find an optimal span program for an arbitrary gate; therefore, we have removed most of the hand-constructed examples present in the conference version of this article.)  

Although the quantum query complexity of read-once formulas is settled, the quantum time complexity is not.  The problem is that operations between queries to the input are not necessarily efficiently implementable.  Our formula-evaluation algorithm is both query optimal and time efficient.  Its strict balance condition has been relaxed, while keeping a time-efficient algorithm, in~\cite{Reichardt09unbalancedformula}.  Compared to this follow-up work, our proof is more technical, but our conclusions are also stronger.  The analysis in~\cite{Reichardt09unbalancedformula, Reichardt09spanprogram-arxivandfocs} is based on showing that the output vertex of the graph has at most a small constant squared overlap on the span of the small-eigenvalue eigenspaces.  Such an ``effective spectral gap'' can be proved relatively easily by studying the eigenvalue-zero eigenvectors.  By contrast, in this article we prove a true spectral gap, \ie, that the output vertex has {no} overlap on small-eigenvalue eigenspaces.  This requires studying eigenvalue-$\lambda$ eigenvectors for small $\lambda \neq 0$, which is not easy (see \secref{s:proof} below).  For the quantum algorithm, an effective spectral gap suffices for applying phase estimation, and only leads to a slightly higher error rate.  


\paragraph{Organization}
In \secref{s:querycomplexity}, we briefly recall the adversary lower bounds on quantum query complexity.  

We introduce span programs and present optimal span programs for all three-bit Boolean functions in \secref{s:spanprograms}.  A span program corresponds to a weighted bipartite graph, and its evaluation corresponds to eigenvalue-zero eigenvectors of the graph (\thmref{t:weakzeroenergy}).  This theorem provides useful intuition.  

We develop a quantitative version of \thmref{t:weakzeroenergy} in \secref{sec:spc}.  We bound from below the overlap of the eigenvalue-zero eigenvector with a known starting state.  This lower bound will imply completeness of our quantum algorithm.  
To show soundness of the algorithm, we also analyze small-eigenvalue eigenvectors in order to prove a spectral gap around zero.  Essentially, we solve the eigenvalue equations in terms of the eigenvalue $\lambda$, and expand a series around $\lambda = 0$.  
The results for small-eigenvalue and eigenvalue-zero eigenvectors are closely related, and are unified using a new complexity measure we term ``span program witness size.''  

In \secref{s:algorithm}, we present a quantum algorithm for evaluating formulas over the gate set~$\gateset$ of all three-bit Boolean functions.  On formulas that are ``adversary-balanced'' (\defref{t:adversarybalanceddef}), the algorithm is optimal.  


\section{Adversary lower bounds on quantum query complexity} \label{s:querycomplexity}

The query complexity or decision-tree complexity of a function $f: \cD \rightarrow E$, with $\cD \subseteq \{0,1\}^n$, is the least number of input bits one must look at in order to evaluate~$f$ on a worst-case input.  The bounded-error quantum query complexity, $Q(f)$, is defined similarly except input queries are allowed to be made in quantum superposition and the output is allowed to be wrong with probability at most~$1/3$.  For a formal definition, see, \eg, the textbook~\cite{NielsenChuang00}.  

To show the optimality of our formula-evaluation algorithm, we will use the general adversary bound: 

\begin{definition}[\cite{HoyerLeeSpalek07negativeadv}] \label{t:adversarydef}
Let $f: \{0,1\}^k \rightarrow \{0,1\}$.  Define the \emph{general adversary bound} $\ADVpm(f)$ by 
\begin{equation} \label{e:adversarydef}
\ADVpm(f) = \max_{\Gamma} \big\{ \norm{\Gamma} : \max_i \norm{ \Gamma \circ D_i } \leq 1 \big\}
 \, .
\end{equation}
The maximum is over all $2^k \times 2^k$ symmetric matrices $\Gamma$ satisfying $\bra{x} \Gamma \ket{y} = 0$ if $f(x) = f(y)$.  $\Gamma \circ D_i$ denotes the entrywise matrix product with $D_i$, a zero-one-valued matrix defined by $\bra{x} D_i \ket{y} = 1$ if and only if $x_i \neq y_i$.  
\end{definition}

\begin{theorem}[\cite{HoyerLeeSpalek07negativeadv}] \label{t:adversaryquerybound}
The bounded-error quantum query complexity of~$f$, $Q(f)$, is $\Omega(\ADVpm(f))$.  
\end{theorem}

The general adversary bound strengthens the adversary bound~\cite{Ambainis06polynomial, BarnumSaksSzegedy03adv}, which is defined as in Equation~\eqnref{e:adversarydef} but with $\Gamma$ required to have non-negative entries.  

To match the lower bound of \thmref{t:adversaryquerybound}, our goal will be to use $O(\ADVpm(\varphi))$ queries to evaluate~$\varphi$.  We will prove the optimality of our algorithm only for formulas satisfying a strict balance condition: 

\begin{definition} \label{t:adversarybalanceddef}
A formula $\varphi$ is \emph{adversary-balanced} if for every gate, the general adversary lower bounds of its input subformulas are equal.  
\end{definition}

This balance condition is motivated by the following composition result: 

\begin{theorem}[\cite{HoyerLeeSpalek07negativeadv}] \label{t:weakadversarycomposition}
Let $f = g \circ (h_1, \ldots, h_k)$, where $\ADVpm(h_1) = \cdots = \ADVpm(h_k)$ and $\circ$ denotes function composition.  Then $\ADVpm(f) \geq \ADVpm(g) \ADVpm(h_1)$.  
\end{theorem}

Subsequent work, using the equivalence between the general adversary bound and span programs, has shown this to be an equality~\cite{Reichardt09spanprogram-arxivandfocs}.  If $\varphi$ is adversary-balanced, then by \thmref{t:weakadversarycomposition} $\ADVpm(\varphi_g)$ is at least the product of the gate adversary bounds along any non-self-intersecting path $\chi$ from $g$ up to an input, $\ADVpm(\varphi_g) \geq \prod_{h \in \chi} \ADVpm(h)$.  Note that $\ADVpm(\neg f) = \ADVpm(f)$, so NOT gates can be inserted anywhere in an adversary-balanced formula.


\section{Span programs and eigenvalue-zero graph eigenvectors} \label{s:spanprograms}

A span program $P$ is a linear-algebraic way of specifying a function $f_P$.  In this section, we will associate~$P$ to a certain structured collection of weighted bipartite graphs $G_P(x)$, in such a way that on input~$x$, $f_P(x) = 1$ if and only if there exists an eigenvalue-zero eigenvector of the adjacency matrix $A_{G_P(x)}$ supported on a distinguished output node (\thmref{t:weakzeroenergy}).  

In turn, this will imply that specifying a span program $P$ for a function $f$ directly gives a quantum algorithm for evaluating $f$, or for evaluating formulas including $f$ as a gate (\secref{s:algorithm}).  The algorithm works by spectral estimation on $A_{G_P(x)}$.  Its running time depends on the span program's ``witness size,'' a new complexity measure we define that bounds the squared length of the above eigenvalue-zero eigenvectors.  

\begin{definition}[Span program~\cite{KarchmerWigderson93span}] \label{t:spanprogramdef}
A span program $P = (n, d, \ket t, V_{\text{free}}, \{V_{j,b}\})$ consists of a ``target'' vector $\ket t \in \C^d$ and finite sets $V_{\text{free}}$ and $V_{1,0}, V_{1,1}, \ldots, V_{n,0}, V_{n,1}$ of ``input'' vectors from $\C^d$.  

To $P$ corresponds a Boolean function $f_P : \{0,1\}^n \rightarrow \{0,1\}$, defined by $f_P(x) = 1$ if and only if $\ket t$ lies in the span of the vectors in $V_{\text{free}} \cup \,\bigcup_{j=1}^n V_{j, x_j}$.  
\end{definition}

For manipulating a span program, it is convenient to index the input vectors so $V_{\text{free}} = \{ v_i : i \in \Ifree \}$ and $V_{j,b} = \{ v_i : i \in I_{j,b} \}$, for disjoint index sets $\Ifree$ and $I_{j,b}$.  Let $I = \Ifree \cup \,\bigcup_{j,b} I_{j,b}$.  Furthermore, let $A$ be the matrix whose columns are the input vectors, \ie, in standard ket notation $A = \sum_{i \in I} \ketbra{v_i}{i}$.  For an input~$x \in \B^n$, let $I(x) = \Ifree \cup \,\bigcup_{j=1}^{n} I_{j,x_j}$ be the indices of the available input vectors, and let $\Pi(x)$ be the projection onto the corresponding columns of $A$, \ie, $\Pi(x) = \sum_{i \in I(x)} \ketbra i i$.  

\begin{definition}[Witness size] \label{t:wsizedef}
Consider a span program $P$, and a vector $s \in [0, \infty)^n$.
Define $S = \sum_{j, b; i \in I_{j,b}} \sqrt{s_j} \ketbra i i$.
Define $P$'s witness size with costs $s$ as 
\[
\wsizeS P s = \max_{x \in \B^n} \wsizexS P x s\,,
\]
where $\wsizexS P x s$ is given by: 
\begin{itemize}
\item If $f_P(x) = 1$, then $\ket{t} \in \Range(A \Pi(x))$, so there is a witness $\ket{w} \in \C^{\abs I}$ satisfying $A \Pi(x) \ket{w} = \ket{t}$.  Then $\wsizexS P x s$ is the minimum squared length of any such witness, weighted by the costs $s$: 
\begin{equation} \label{e:wsizetrue}
\wsizexS P x s 
= \min_{\ket w : \, A \Pi(x) \ket w = \ket t} \norm{S \ket w}^2
 \, .
\end{equation}
\item If $f_P(x) = 0$, then $\ket t \notin \Range(A \Pi(x))$.
Therefore there is a witness $\ket{w'} \in \C^d$ satisfying $\braket{t}{w'} = 1$ and $\Pi(x) A^\adjoint \ket{w'} = 0$.  Then 
\begin{equation} \label{e:wsizefalse}
\wsizexS P x s 
= \min_{\substack{\ket{w'} : \, \braket{t}{w'} = 1 \\ \Pi(x) A^\adjoint \ket{w'} = 0}} \norm{S A^\adjoint \ket{w'}}{}^2
 \, .
\end{equation}
\end{itemize}
\end{definition}

When the subscript~$s$ is omitted, the costs are taken to be uniform, $s = \vec 1 = (1, 1, \ldots, 1)$, \eg, $\wsize P = \wsizeS P {\vec 1}$.  In this case, note that $S = \identity - \sum_{i \in \Ifree} \ketbra i i$.  

Observe that the witness size is invariant under the application of any invertible linear transformation to the target and input vectors.  Moreover, since the witness size does not charge for using vectors in $\Span(V_{\text{free}})$, we may eliminate the free input vectors.  (See~\cite[Lemma~4.12, Prop.~4.10]{Reichardt09spanprogram-arxivandfocs}.)  

\begin{lemma} \label{t:spanprogramremark}
For any span program $P$, we may by an invertible linear transformation on the vectors in~$\C^d$ change the target vector to $(1, 0, 0, \ldots, 0)$.  By projecting all vectors onto the space orthogonal to the span of~$V_{\text{free}}$, we may assume $V_{\text{free}} = \emptyset$.  These operations change neither $f_P$ nor the witness size.  
\end{lemma}


\subsection{Span program as an adjacency matrix}

\begin{definition}[Graphs $G_P$ and $G_P(x)$] \label{t:spanprogramadjacencymatrix}
For a span program $P$, let $G_P$ be the complex-weighted, bipartite graph with biadjacency matrix
\begin{equation} \label{e:spanprogramadjacencymatrix}
\biadj_{G_P} = \left( \begin{matrix} \ket t & A \end{matrix} \right)
 \, .
\end{equation}
That is, $G_P$ has $1 + \abs I$ column vertices and $d$ row vertices.  The first column vertex, called the ``output vertex,'' has incident edges weighted by the coordinates of $\ket t$.  Each of the remaining $\abs I$ column vertices, or ``input vertices,'' has incident edges weighted by an input vector.  The adjacency matrix of $G_P$ is 
\begin{equation}
A_{G_P} = \left( \begin{matrix} 0 & \biadj_{G_P} \\ \biadj_{G_P}^\dagger & 0 \end{matrix} \right)
 \, .
\end{equation}

For an input $x \in \B^n$, let $G_P(x)$ be the same graph, but with weight-one dangling edges attached to the input vertices of $I \smallsetminus I(x)$.  That is, the biadjacency matrix of $G_P(x)$ is 
\begin{equation}
\biadj_{G_P(x)} = \left( \begin{matrix} \ket t & A \\ 0 & \identity-\Pi(x) \end{matrix} \right)
 \, .
\end{equation}
\end{definition}

\begin{theorem} \label{t:weakzeroenergy}
Let $P$ be a span program, and $x$ an input.  Then there is a vector in the kernel of $\biadj_{G_P(x)}$ supported on the output vertex if and only if $f_P(x) = 1$.  There is a vector in the kernel of $\big(A^\dagger, \identity - \Pi(x)\big)$, the first $d$ coordinates of which having nonzero inner product with~$\ket t$, if and only if $f_P(x) = 0$.  
\end{theorem}

\begin{proof}
A vector $(a_O, \ket w) \in \C \times \C^{\abs I}$ is in the kernel of $\biadj_{G_P(x)}$ if and only if $a_O \ket t + A \ket w = 0$ and $(\identity - \Pi(x)) \ket w = 0$.  The second condition says that the support of $\ket w$ contains only vertices corresponding to indices in $I(x)$.  The first condition says that the corresponding linear combination of input vectors is~$-a_O \ket t$.  When $a_O \neq 0$, the existence of a $\ket w$ satisfying these conditions is equivalent to $f_P(x) = 1$.  

Next, we have that $f_P(x) = 0$ if and only if $\ket t \notin \Range(A \Pi(x))$, which in turn holds if and only if there is a vector $\ket{w'} \in \C^d$ with $\braket{t}{w'} \neq 0$ and $\Pi(x) A^\dagger \ket{w'} = 0$.  This is equivalent to the existence of a vector $(\ket{w'}, \ket{w''}) \in \C^d \times \C^{\abs I}$ in the kernel of $\big(A^\dagger, \identity - \Pi(x)\big)$ with $\braket{t}{w'} \neq 0$ (for $i \in I \smallsetminus I(x)$, set $\braket{i}{w''} = -\bra i A^\dagger \ket{w'}$).  
\end{proof}

\begin{example} \label{t:maj3example}
The span program $P$ with $n=3$, $d=2$, $\ket t = (1,0)$, $V_{\text{free}} = V_{1,0} = V_{2,0} = V_{3,1} = \emptyset$, $V_{1,1} = \{ (1, \alpha) \}$, $V_{2,1} = \{ (1, \beta) \}$, $V_{3,0} = \{ (1, \gamma) \}$ computes the function $\MAJ(x_1, x_2, \bar x_3)$, provided $\alpha, \beta, \gamma$ are distinct and nonzero.  The biadjacency matrix $\biadj_{G_P(101)}$ is
\[
\left( \begin{array}{c | c c c}
1 & 1 & 1 & 1 \\
0 & \alpha & \beta	 & \gamma \\
\hline
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{array} \right) \, .
\]
\end{example}


\subsection{Dual span program} \label{s:dualspanprogram}

Observe that attaching a dangling weight-one edge to the output vertex complements the %
conditions of \thmref{t:weakzeroenergy}.  Therefore a length-one path can be thought of as a NOT gate gadget.  The construction of $G_P(x)$ from $G_P$ is also based on adding NOT gates to false inputs.  

\begin{definition}[Dual span program]
For a span program $P$, define its dual $P^\adjoint$ by complementing the output and all inputs with dangling weight-one edges, and also switching each input vector set $V_{j,b}$ with~$V_{j,1-b}$.  
\end{definition}

\begin{example} \label{t:dualspanprogramexample}
For distinct, nonzero $\alpha, \beta, \gamma$, the span program\!\!\!
\[
\setcounter{sprows}{4}
\setlength{\spheight}{30pt}
\setlength{\spraise}{6pt}
\begin{array}{r@{}c@{}l r@{\ }c@{\ }c@{\ }*{2}{c@{\ }}c@{}l}
& & & & \multicolumn{2}{c}{\!\!\!\top} & \bar x_1 & \bar x_2 & x_3 &  \\
\noalign{\smallskip}
\spleft{\ket t=} & 1 & \spright{,} & \spleft[2pt]{A=} & 1 & 0 & 0 & 0 & 0 & \spright[2pt]{} \\
            & 0 &             &                    & 1 & \alpha & 1 & 0 & 0 & \\
            & 0 &             &                    & 1 & \beta & 0 & 1 & 0 & \\
            & 0 &             &                    & 1 & \gamma & 0 & 0 & 1 & \\
\end{array}
\place{$\overbrace{\;}$}{-97mu}{21pt}
\]
computes $\neg \MAJ(x_1, x_2, \bar x_3)$.  Here, we have introduced the notation that $\top$ labels input vectors in $V_{\text{free}}$, and input vectors in $V_{j,1}$ or $V_{j,0}$ are indicated by the positive or negative literals $x_j$ or $\bar x_j$, respectively; thus, \eg, $V_{3,1} = \{ (0,0,0,1) \}$.  This span program is dual to the span program in \exampleref{t:maj3example}.  
\end{example}

{}From \defref{t:wsizedef}, it is immediate that the dual span program $P^\dagger$ satisfies $f_{P^\adjoint} = \neg f_P$ and $\wsize{P^\adjoint} = \wsize P$.  (See also~\cite[Lemma~4.1]{Reichardt09spanprogram-arxivandfocs}.)  

Alternative constructions of dual span programs are given in~\cite{CramerFehr02secretshare, NikovNikovaPreneel05spanprogram}.  


\subsection{Span program composition}

\begin{definition}[Composed graph and span program] \label{t:composespanprogramdef}
Consider span program $P = (n, d, \ket t, V_{\text{free}}, \{V_{j,b}\})$ and span programs $Q_j$ and $Q_j^\dagger$ for $j = 1, \ldots, n$.  The composed graph is defined by attaching $G_P$ to copies of the $G_{\smash{Q_j}}$ and $G_{\smash{Q_j^\dagger}}$ graphs as follows: each input vertex associated to $V_{j,1}$ should be identified with the output vertex of a copy of $G_{\smash{Q_j}}$; and each input vertex associated to $V_{j,0}$ should be identified with the output vertex of a copy of $G_{\smash{Q_j^\dagger}}$.  The composed span program is the span program corresponding to this composed graph.  
\end{definition}

\def\majmajspanprogramexample{
\setcounter{sprows}{4}\setlength{\spheight}{29pt}\setlength{\spraise}{4pt}
\begin{array}{r@{}c@{}l r@{}*{5}{c@{\ }}c@{}l}
& & &  & x_1 & x_2 & \top & x_3 & x_4 & x_5 & \\
\noalign{\smallskip}
\spleft{\ket t =} & 1 & \spright{,} & \spleft[2pt]{A=} & 1&1&1&0&0&0& \spright[2pt]{} \\
& 0 & & & \alpha&\beta&\gamma&0 & 0& 0&\\
& 0 & & & 0 & 0& 1& 1& 1& 1& \\
& 0 & & & 0 & 0& 0& \alpha&\beta&\gamma&\\
\end{array}
}

The composed span program computes the composed function $f_P \circ (f_{Q_1}, \ldots, f_{Q_n})$.  Two examples are given in \figref{f:maj3ofmaj3}.  Span program composition is studied in more detail in~\cite[Sec.~4.2]{Reichardt09spanprogram-arxivandfocs}.  

\begin{figure}
\begin{center}
\subfigure[]{\raisebox{1cm}{$\majmajspanprogramexample$}\vspace{1cm}}
$\qquad$
\subfigure[]{\includegraphics[scale=.62]{majmajcompositiongraph2}}
$\qquad$\subfigure[]{\includegraphics[scale=.52]{exampleformulagraphxlabeled}}
\end{center}
\vskip -10pt
\caption{
(a) A composed span program that computes the function $\MAJ(x_1, x_2, \MAJ(x_3, x_4, x_5))$, provided $\alpha, \beta, \gamma$ are distinct and nonzero.  (b) The associated composed graph, with labeled input vertices.  (c) Graph for $\MAJ(x_1, x_2, x_3) \oplus x_4$, evaluated on input $x=1100$.  The span program for PARITY is from \secref{s:gatebygate}.  The eigenvalue-zero eigenvector promised by \thmref{t:weakzeroenergy} is supported on the black vertices.  
} \label{f:maj3ofmaj3}
\end{figure}


\subsection{Examples: Span programs for three-bit gates} \label{s:gatebygate}

\begin{table}
\begin{center}
\begin{tabular}{|c|c|}
\hline \hline
Gate $g$& $\ADVpm(g)$\\
\hline
0 & 0 \\[.035cm]
$x_1$ & 1 \\[.035cm]
$x_1 \wedge x_2$ & $\sqrt 2$ \\
$x_1 \oplus x_2$ & 2 \\
$x_1 \wedge x_2 \wedge x_3$ & $\sqrt 3$ \\
$x_1 \vee (x_2 \wedge x_3)$ & $\sqrt 3$ \\
$x_1 \oplus (x_2 \wedge x_3)$ & $1+\sqrt 2$ \\
\hline \hline
\end{tabular}\hspace{.5cm}
\begin{tabular}{|c|c|}
\hline \hline
Gate $g$& $\ADVpm(g)$ \\
\hline
$x_1 \vee (x_2 \oplus x_3)$ & $\sqrt{5}$ \\
$x_1 \oplus x_2 \oplus x_3$ & 3 \\
$(x_1 \wedge x_2 \wedge x_3) \vee (\bar x_1 \wedge \bar x_2)$ & $\sqrt{3+\sqrt 3}$ \\
$\mathrm{IF}$-$\mathrm{THEN}$-$\mathrm{ELSE}(x) = (x_1 \wedge x_2) \vee (\bar x_1 \wedge x_3)$ & 2 \\
$\MAJ(x) = (x_1 \wedge x_2) \vee ((x_1 \vee x_2) \wedge x_3)$ & 2 \\
$\EQUAL_3(x) = (x_1 \wedge x_2 \wedge x_3) \vee (\bar x_1 \wedge \bar x_2 \wedge \bar x_3)$ & $3/\sqrt 2$ \\
$\mathrm{EXACT}_{\text{2 of 3}}(x) = \MAJ(x) \wedge (\bar x_1 \vee \bar x_2 \vee \bar x_3)$ & $\sqrt 7$ \\
\hline \hline
\end{tabular}
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
\end{center}
\caption{Inequivalent binary gates on up to three bits $x = x_1 x_2 x_3 \in \{0,1\}^3$, and their adversary bounds.} \label{f:threebitgates}
\end{table}

In order to make the above formalism more concrete, we now present span programs for every function $\{0,1\}^3 \rightarrow \{0,1\}$.  Up to permutation of inputs and complementation of some or all inputs or output, there are fourteen inequivalent three-bit functions.  
\tabref{f:threebitgates} lists these functions together with their general adversary bounds, as computed by~\cite{HoyerLeeSpalek07negativeadvurl}.  For all three-bit functions, the general adversary bound and the adversary bound are equal.  Based on our algorithm in \secref{s:algorithm} below, it will follow that the general adversary bound is a lower bound on span program witness size.  Therefore the span programs we give here are optimal.  

\begin{theorem} \label{t:wsizegates}
For every three-bit function $g: \{0,1\}^3 \rightarrow \{0,1\}$, there exists a span program $P$ with~$f_P = g$, such that the witness size of $P$ with uniform costs is  
\begin{equation}
\wsize{P} = \ADVpm(g)
 \, .
\end{equation}
\end{theorem}

\goodbreak
\begin{proof}
We begin by giving optimal span programs for the functions $\MAJ$, following \exampleref{t:maj3example}, and AND (equivalent to OR).  We construct optimal span programs for the other functions by combining these two basic span programs.  

\begin{claim} \label{t:majwsize}
Let $P_{\MAJ}$ be the span program from \exampleref{t:maj3example} with $(\alpha, \beta, \gamma) = (1, e^{2\pi i/3}, e^{-2\pi i/3})$.  Then if $\MAJ(x) = 0$, $\wsizex {P_{\MAJ}} x \leq 6$, while if $\MAJ(x) = 1$, $\wsizex {P_{\MAJ}} x \leq 2/3$.  
\end{claim}

\begin{proof}
Substitute $P_{\MAJ}$ into \defref{t:wsizedef}.  Some of the witnesses are $\ket{w'_{000}} = (1, 0)$, $\ket{w'_{100}} = (1, -1)$, and $\ket{w_{110}} = (e^{-i \pi/6}, e^{i \pi/6}, 0)/\sqrt 3$, $\ket{w_{111}} = (1,1,1)/3$.  The other witness vectors are symmetrical.  
\end{proof}

The cases $\MAJ(x) = 0$ or $1$ can be balanced by scaling the input vectors by a factor of $1/\sqrt 3$, yielding a span program with witness size two.  

For functions $b$ and $b'$ on disjoint inputs, the general adversary bound satisfies $\ADVpm(b \oplus b') = \ADVpm(b) + \ADVpm(b')$ and $\ADVpm(b \vee b') = ({{\ADVpm(b)^2 + \ADVpm(b')^2}})^{1/2}$~\cite{bs:q-read-once, HoyerLeeSpalek07negativeadv}; we obtain matching upper bounds for span program witness size.  

\begin{claim} \label{t:orwsize}
Let $s \in (0, \infty)^n$ and let $P$ be the span program with target
vector $\ket t = 1$, and input vectors 
\[
V_{j,1} = \left\{ \frac{\sqrt{s_j} }{ \sqrt[4]{\sum_i s_i^2}} \right\}\quad \text{and}
\quad V_{j,0} = V_{\text{free}} = \emptyset\,.
\]
Then $f_P$ is the $n$-bit $\mathrm{OR}$ function, and $\wsizeS P s = \sqrt{\sum_j s_j^2}$.  
\end{claim}

\begin{proof}
On input $x = 0^n$, the unique witness $\ket{w'} = 1$ satisfies 
\[
\braket{t}{w'} = 1\quad\text{and}\quad \norm{S A^\dagger \ket{w'}}^2 =
\sqrt{\sum_j s_j^2}\,.
\]
On input $x = 10^{n-1}$, the unique witness $\ket w$, with coefficient
$\sqrt[4]{\sum_i s_i^2} / \sqrt{s_1}$ on the $V_{1,1}$ input vector,
satisfies 
\[
A \ket w = \ket t\quad \text{and}\quad \norm{S \ket w}^2 =
\sqrt{\sum_j s_j^2}\,.
\]
The other inputs with Hamming weight one are symmetrical, and the witness size only decreases for larger Hamming weight inputs.  
\end{proof}

DeMorgan's laws allow for converting ANDs into ORs.  For example, a
span program $P$ for $x_1 \wedge x_2$ has 
\[
\ket t = \frac{1}{\sqrt[4]{s_1^2 + s_2^2}} \,(\sqrt{s_1},\sqrt{s_2}) \,, \quad
V_{j,1} = \{ (1,0) \} \quad \text{and}\quad V_{j,2} = \{ (0,1) \}\,.
\]
Then $\wsizeS P s = \sqrt{s_1^2 + s_2^2}$.  

Other span programs can be written by combining the above span programs for AND and for OR.  Our span program for PARITY is based on the identity $x_1 \oplus x_2 = (x_1 \wedge \bar x_2) \vee (\bar x_1 \wedge x_2)$, as follows: 
\[
\begin{array}{r@{}c@{}l r@{}*{1}{c@{\ }}c@{}l}
& & &  & x_1 \wedge \bar x_2 & \bar x_1 \wedge x_2 & \\
\noalign{\smallskip}
\ket t = ( & 1 & )\,, & A = ( & 1 & 1 & )
 \, .
\end{array}
\]
Here, we have introduced a convenient shorthand notation of labeling input vectors by AND gates on subsets of the input bits (such input vectors are termed ``grouped input vectors'' in~\cite{ReichardtSpalek08spanprogram}).  This should be interpreted as indicating a composition with an \emph{unweighted} span program for the AND gate, \ie, as the span program 
\begin{equation} \label{e:parity}
\setcounter{sprows}{5}\setlength{\spheight}{36pt}\setlength{\spraise}{4pt}
\begin{array}{r@{}c@{}l r@{}*{5}{c@{\ }}c@{}l}
& & &  & \top & x_1 & \bar x_2 & \top & \bar x_1 & x_2 & \\
\noalign{\smallskip}
\spleft{\ket t =} & 1 & \spright{,} & \spleft[2pt]{A=} & 1&0&0&1&0&0& \spright[2pt]{} \\
& 0 & & & 1 & 1& 0&0 & 0& 0&\\
& 0 & & & 1 & 0& 1& 0& 0& 0& \\
& 0 & & & 0& 0& 0& 1 &1&0&\\
& 0 & & & 0& 0& 0& 1 &0&1&\\
\end{array}\,.
\end{equation}

\begin{claim} \label{t:paritywsize}
The span program~$P$ from Equation~\eqnref{e:parity} has $f_P(x) = x_1 \oplus x_2$ and $\wsizeS P s = s_1 + s_2$.  
\end{claim}

The proof is an easy calculation.  

Optimal span programs for most three-bit functions can be constructed
using Claims~\ref{t:majwsize}, \ref{t:orwsize}
and~\ref{t:paritywsize}, \eg, the function EXACT$_{\text{2 of 3}}(x_1,
x_2, x_3) = \MAJ(x_1, x_2, x_3) \wedge (\bar x_1 \vee \bar x_2 \vee
\bar x_3)$, so there is a span program with witness size at most
\[
\sqrt{\wsize\MAJ{}^2 + \wsize{\mathrm{OR}_3}{}^2} = \sqrt{7}\,.
\]
The only exceptions are $(x_1 \wedge x_2 \wedge x_3) \vee (\bar x_1 \wedge \bar x_2)$ and the equality function.  For the former function, use the span program 
\[
\setcounter{sprows}{2}
\setlength{\spheight}{14pt}
\setlength{\spraise}{6pt}
\begin{array}{r@{}c@{}l r@{}*{2}{c@{\ }}c@{}l}
& & &  & x_1 \wedge x_2 & x_3 & \bar x_1 \wedge \bar x_2 & \\
\noalign{\smallskip}
\spleft{\ket t =} & 1 & \spright{,} & \spleft[2pt]{A=}
  & \alpha_1 & 0 & \alpha_1 \alpha_2 & \spright{} \\
& 0 & & & \alpha_2 & 1 & 0 &
\end{array}
\]
where $\alpha_1 = \sqrt[4]{1 + \frac 1 {\sqrt 3}}$ and $\alpha_2 = \sqrt{\sqrt3 - 1}$.  
This expands out to 
\[
\setcounter{sprows}{6}
\setlength{\spheight}{42pt}
\setlength{\spraise}{20pt}
\begin{array}{r@{}c@{}l r@{}*{6}{c@{\ }}c@{}l}
& & &  & \top & x_1 & x_2 & x_3 & \top & \bar x_2 & \bar x_3 \\
\noalign{\smallskip}
\spleft{\ket t =} & 1 & \spright{,} & \spleft[2pt]{A=}
  & \alpha_1 & 0 & 0 & 0 & \alpha_1 \alpha_2 & 0 & 0 & \spright{} \\
& 0 & & & \alpha_2 & 0 & 0 & 1 & 0 & 0 & 0 \\
& 0 & & & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
& 0 & & & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
& 0 & & & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
& 0 & & & 0 & 0 & 0 & 0 & 1 & 0 & 1 
\end{array}\,.
\]
The witness size is $\sqrt{3 + \sqrt 3}$, matching the adversary bound.\footnote{A calculation gives that the optimal adversary matrix $\Gamma$ in \defref{t:adversarydef} comes from the matrix 
\[
\bigg(\begin{smallmatrix}
1 & a & \sqrt{3} \\
1 & a & \sqrt{3} \\
b & 0 & \sqrt{3} 
\end{smallmatrix}\bigg)\,,\quad
\text{where}\quad
a = \big(\tfrac12(5-\sqrt{13-6\sqrt{3}})\big)^{1/2}\,, \quad  b =
\tfrac12 \big(-1-\sqrt{3}+\sqrt{2(8+\sqrt{3})}\big)\,,
\]
and the rows correspond to inputs $011$, $101$, $110$, the columns to inputs $000$, $001$, $111$.}  Finally, 

\begin{claim}
Using the condensed notation introduced for PARITY, an optimal span program for the equality function, $\EQUAL_n(x) = ( \wedge_{j=1}^n x_j ) \vee ( \wedge_{j=1}^n \bar x_j )$, is given by 
\[
\begin{array}{r@{}c@{}l r@{}*{1}{c@{\ }}c@{}l}
& & &  & \wedge_j x_j & \wedge_j \bar x_j & \\
\noalign{\smallskip}
\ket t = ( & 1 & )\,, & A = ( & \sqrt[4]{n-1} & \sqrt[4]{n-1} & )
 \, .
\end{array}
\]
This span program has witness size $n/\sqrt{n-1}$, which equals the
adversary bound.\footnote{The optimal adversary matrix $\Gamma$ comes
  from the $2 \times 2 n$ matrix 
\[
\big(\begin{smallmatrix}1 & 1 & \cdots & a & a & \cdots \\ a & a &
  \cdots & 1 & 1 & \cdots \end{smallmatrix}\big)\,,
\] where the rows correspond to inputs $0^n$ and~$1^n$, and the columns correspond to inputs of Hamming weight $1$ and $n-1$, and $a = 1 / (n-1)$.}
\end{claim}

%
\begin{proof}
The unweighted AND span program has witness size~$n$ on input $x = 1^n$, and $1/(n - \abs x)$ otherwise.  

For the above span program, therefore, on input $x = 1^n$, the witness
$\ket w = (1/\sqrt[4]{n-1}, 0)$ gives a witness size of $n /{\sqrt{n-1}}$, where the factor of~$n$ is from the AND gate.   The input $x = 0^n$ is symmetrical.  

On a false input~$x$, $\ket{w'} = (1)$ gives a witness size of 
\[
\sqrt{n-1} \left( \frac{1}{n - \abs x} + \frac{1}{\abs x} \right) \leq \frac{n}{\sqrt{n-1}}\,.
\]  
\end{proof}
This completes the proof of \thmref{t:wsizegates}.  
\end{proof}

Many more optimal span programs, for various four-bit functions, can be found in an earlier arXiv version of this article~\cite{ReichardtSpalek08spanprogram}.  


\section{Small-eigenvalue analysis of composed span programs} \label{sec:spc}

\begin{definition}[Formula graph and span program] \label{t:formulagraphdef}
Given span programs for each gate in a formula $\varphi$, span program $P(\varphi)$ is defined as their composition according to the formula.  Let $G(\varphi, x)$ be the composed graph on input $x$, $G(\varphi, x) = G_{P(\varphi)}(x)$---except with length-two, weight-one paths attached to each input vertex in $I(x)$.  
\end{definition}

\thmref{t:weakzeroenergy} establishes that $\varphi(x) = 1$ if and only if $G(\varphi, x)$ has an eigenvalue-zero eigenvector supported on the output vertex.  (Attaching length-two paths to the $I(x)$ inputs clearly does not change this property.)  Thus if $\varphi(x) = 0$, the graph has a spectral gap centered on zero.  The goal of this section is to make \thmref{t:weakzeroenergy} more quantitative, so that a phase estimation-based quantum algorithm for evaluating~$\varphi$ can be constructed and analyzed.  

Since $G(\varphi, x)$ is a bipartite graph, it suffices to study eigenvectors with non-negative eigenvalues.  Let $\lambda \geq 0$ and assume that $\ket{\psi_\lambda}$ is a unit-normalized eigenvalue-$\lambda$ eigenvector of the adjacency matrix $A_{G(\varphi, x)}$---except possibly not satisfying the eigenvector constraint at the output vertex.  The output vertex constraint is the only constraint that changes if we compose $\varphi$ as an input to another span program, so leaving it out facilitates proofs by induction in the formula depth.  Let $a_O$ be the coefficient of $\ket{\psi_\lambda}$ on the output vertex and~$b_O$ be the coefficient of $A_{G(\varphi, x)} \ket{\psi_\lambda}$ on the output vertex.  
\begin{itemize}
\item
For $\lambda = 0$, we will place a lower bound on the achievable $\abs{a_O}^2$ when $\varphi(x) = 1$.  This will enable the algorithm to detect if $\varphi(x) = 1$ by starting a quantum walk at the output vertex.  
\item
For small enough eigenvalues $\lambda > 0$, we will show that the evaluation $\varphi(x)$ corresponds to the \emph{ratio} of the two output coefficients $a_O$ and $b_O$.  Let $\ri_{O} = a_O / b_O$.  If $\varphi(x) = 1$, then $\ri_{O}$ is large and negative, roughly of order $-1/\lambda$.  If $\varphi(x) = 0$, then $\ri_{O}$ is small and positive, of order $\lambda$.  It will follow that if $\varphi(x) = 0$, then there is a significant spectral gap centered on zero of eigenvectors with any support on the output vertex.  This spectral gap will prevent the algorithm from outputting false positives.  
\end{itemize}

These two cases are considered in Sections~\ref{s:lambdazerocase} and~\ref{s:lambdasmallcase} below.  In our main theorem, \thmref{t:formulaspectrum} in \secref{s:spectralgap}, we will reimpose the output vertex constraint.  For small enough $\lambda > 0$, it will give a contradiction when $\varphi(x) = 0$, implying that the graph has a significant spectral gap.  

Assume for simplicity that the span programs used in $\varphi$, including dual span programs, have no free input vectors, \ie, $V_{\text{free}} = \emptyset$.  By \lemref{t:spanprogramremark}, this assumption is without loss of generality.  The span program $P(\varphi)$ will still have free input vectors at vertices between gates (as shown, \eg, in \figref{f:maj3ofmaj3}).  We do \emph{not} eliminate these free inputs, since doing so would make the graph dense, preventing an efficient implementation of a quantum walk.  


\subsection{The case \texorpdfstring{$\lambda = 0$}{lambda=0}} \label{s:lambdazerocase}

We begin the $\lambda = 0$ analysis by defining two subformula complexity measures.  For each node $v$ in a formula~$\varphi$, let $P_v$ be the associated span program, and let 
\begin{align} \label{e:subformulacomplexitymeasures}
\pi(v) &= \max_\xi \prod_{w \in \xi} \wsize{P_w}\,, &
\sigma(v) &= 1 + \max_\xi \sum_{w \in \xi} \frac{1}{\pi(w)}
 \, , 
\end{align}
where the maximizations are both over simple paths in $\varphi$ from $v$ through its inputs to a leaf.  The leaf itself contributes $+1$ to $\sigma(v)$.  Let $\pi(\varphi), \sigma(\varphi)$ be the same quantities evaluated at the root of $\varphi$.  The second quantity, $\sigma(\varphi)$, accounts for amplitude on free inputs, and will be a constant in our ultimate application.  

\begin{lemma} \label{t:eigenvaluezero}
If $\varphi(x) = 1$, then $A_{G(\varphi, x)}$ has an eigenvalue-zero eigenvector $\ket{\psi_0}$ with output coefficient $a_O$ satisfying 
\begin{equation}
\frac{\norm{\ket{\psi_0}}^2}{\abs{a_O}^2} \leq \pi(\varphi) \sigma(\varphi) 
 \, .
\end{equation}
\end{lemma}

\begin{proof}
The proof is by induction in the depth of the formula.  

If the depth is zero, \ie, $\varphi$ consists of a single variable $x_j$ or its negation, then since $\varphi(x) = 1$, $G(\varphi, x)$ is just a length-two path, with eigenvector $\ket{\psi_0} = (1, 0, -1)$.  Thus $\abs{a_O}^2 = \frac12 \norm{\ket{\psi_0}}^2$ and $\pi(\varphi) = 1$, $\sigma(\varphi) = 2$.  

Now for the induction step, assume that for each available input $i$
of the base span program $P$ we have constructed an eigenvalue-zero
eigenvector $\ket{\psi_0^{(i)}}$ of the corresponding subformula graph
that satisfies the induction hypothesis: 
\[
\frac{\norm{\ket{\psi_0^{(i)}}}^2}{\abs{a_O^{(i)}}^2} \leq \pi(v_i)
\sigma(v_i)\,,
\]
where $v_i$ is the gate in $\varphi$ corresponding to input~$i$.  Let $\ket w$ be an optimal witness for $P$, achieving the minimum in Equation~\eqnref{e:wsizetrue}.  Let $a_O = -1$ and scale the $i$th eigenvector by the coefficient $\braket i w / a_O^{(i)}$, combining them to give $\ket{\psi_0}$, an eigenvalue-zero eigenvector for~$G(\varphi, x)$.  Then 
\begin{equation*}\begin{split}
\frac{\norm{\ket{\psi_0}}^2}{\abs{a_O}^2} 
= \norm{\ket{\psi_0}}^2 
&= 1 + \sum_i \frac{ \abs{\braket i w}^2 }{ \abs{a_O^{(i)}}^2 } \norm{\ket{\psi_0^{(i)}}}^2 \\
&\leq 1 + \norm{\ket w}^2 \cdot \max_i \frac{ \norm{\ket{\psi_0^{(i)}}}^2 }{\abs{a_O^{(i)}}^2} \\
&\leq 1 + \wsize P \cdot \max_i \pi(v_i) \cdot \max_i \sigma(v_i) \\
&= \pi(\varphi) \sigma(\varphi)
 \, . \qedhere
\end{split}\end{equation*}
\end{proof}

\subsection{The case \texorpdfstring{$\lambda > 0$}{lambda>0}} \label{s:lambdasmallcase}

Now consider $\lambda > 0$.  Similar to the proof of \lemref{t:eigenvaluezero}, our goal will be to construct an eigenvalue-$\lambda$ eigenvector $\ket{\psi_\lambda}$ for $G(\varphi, x)$ inductively, based on joining together appropriately scaled eigenvectors for the input subformula graphs.  

Let $P$ be the root span program, with \emph{unit-length} target vector $\ket t$ and matrix of input vectors $A$.  Assume that for each input $i$, we have constructed states $\ket{\psi_\lambda^{(i)}}$ satisfying the eigenvalue-$\lambda$ constraints for all the $i$th subgraph's vertices except at the output vertex.  Let $a_i$ and $b_i$ be the output coefficients for the $i$th subgraph.  Assume that there exists an $\ri_i \neq 0$ such that $a_i = \ri_i b_i$.\footnote{In \defref{t:formulagraphdef} we attached length-two paths to vertices in $I(x)$ entirely so that this $\ri_i$ exists even when input $i$ is a single literal, not another span program, and so that no special case in the analysis is needed.}  

Let $\bra \alto = \bra t A$ and let $\ACJ = (\identity - \ketbra t t) A$, so $A = \ACJ + \ketbra{t}{\alto}$.  Let $\ket{a_I}$ and $\ket{b_I}$ denote the vectors of scaled output coefficients for the input subgraphs, and let $\ket{b_C}$ be the other row-vertex coefficients of $\ket{\psi_\lambda}$ in the subgraph~$G_P$.  The notation is meant to be suggestive: $O$ for ``output,'' $I$ for ``input'' and $C$ for ``constraints.''  \figref{f:gadget} places these coefficients on~$G_P$.  
{}From Equation~\eqnref{e:spanprogramadjacencymatrix}, the additional eigenvalue-$\lambda$ eigenvector equations imposed by composition with $G_P$ are 
\begin{subequations} \label{e:zeroenergyequations}
\begin{align}
\lambda \ket{b_C} &= C \ket{a_I}\,, \label{e:zeroenergyequationsbC} \\ 
\lambda b_O &= \braket{o}{a_I} + a_O\,, \label{e:zeroenergyequationsbO} \\
\lambda \ket{a_I} &= \ket{b_I} + \ket o b_O + C^\adjoint \ket{b_C}\,. \label{e:zeroenergyequationsaI}
\end{align}
\end{subequations}
Here, we have left off the eigenvalue-$\lambda$ constraint at the output vertex, $\lambda a_O = b_O$, since this constraint will be modified by later composition steps, as in~\eqnref{e:zeroenergyequationsaI} for the input subgraphs.  Letting $\ri = \sum_i \ri_i \ketbra i i$, our goal is to solve Equations~\eqnref{e:zeroenergyequations} with the subgraph output coefficients constrained by  
\begin{equation} \label{e:inputratios}
\ket{a_I} = r \ket{b_I}
 \, .
\end{equation}

\begin{figure}
\begin{equation*}
\hskip-10pt
\raisebox{-32pt}{\includegraphics[scale=.6]{gadget.pdf}}
\qquad\qquad
\setcounter{sprows}{3}
\setlength{\spheight}{24pt}
\setlength{\spraise}{4pt}
\biadj_{G_P} = 
\raisebox{5pt}{$\begin{array}{*{2}{@{\ }c} *{2}{@{\ }c} @{} r}
& \multispan1{$\!\!a_O$} & a_I & & \\
& \multispan1{} & \overbrace{\quad} & & \\
\noalign{\vskip-2pt}
\spleft{} & \!1 & \raisebox{1pt}{$\bra{\alto}$} & \!\!\spright{} & b_O \\
& \!\!\!\begin{matrix}0\\[-5pt] :\\[-3pt]\vphantom{(} 0\end{matrix}\!\!\! & \ACJ & & \Big\} b_C \\
\end{array} \place{\rule{8ex}{.33pt}}{-85mu}{-.5pt}\place{\rule{.33pt}{8.5ex}}{-92mu}{-30pt} $} 
\end{equation*}
\caption{The graph $G_P$ with coefficients $a_O, b_O, \ket{a_I}, \ket{b_I}, \ket{b_C}$ indicated, in the case $\ket t = (1, 0, \ldots, 0)$.}
\label{f:gadget}
\end{figure}

Our main technical theorem is: 

\begin{theorem} \label{t:strongsmallenergy}
Fix an input $x$ to $\varphi$, and let $\tilde x$ be the input to the root span program~$P$.  For each input index~$i$, let $\si_i = \ri_i / \lambda$ if the input evaluates to~$0$ and let $\si_i = -\ri_i^{-1} / \lambda$ if it evaluates to~$1$.  Assume that each~$\si_i > 0$.  

Then there exist $\eps_P, \delta_P > 0$, constants depending only on the span program $P$, such that, provided $0 < \lambda \leq \eps_P \min\{ 1, 1/ \max_i \si_i \}$, there exists an $r_O \neq 0$ such that any solution to Equations~\eqnref{e:zeroenergyequations} and~\eqnref{e:inputratios} satisfies $a_O = r_O b_O$.  Moreover, if $s_O$ is defined as be either $r_O / \lambda$ or $-r_O^{-1} / \lambda$, depending on whether $\varphi(x)$ is $0$ or~$1$, respectively, $s_O$ satisfies 
\begin{equation} \label{e:unifiedsolution}
0 < s_O < \wsizex P {\tilde x} \cdot \max_i \si_i \cdot (1 + \delta_P \lambda^2 \max_i \si_i^2) + \delta_P
 \, .
\end{equation}
\end{theorem}

The proof of this theorem has two main parts.  First, in \secref{s:equivalentwsizeexpressions} below, we will derive several alternative expressions for span program witness size.  Second, in \secref{s:proof}, we will compute the Taylor series of the inverse of a certain matrix, in order to solve Equations~\eqnref{e:zeroenergyequations} and~\eqnref{e:inputratios}.  The lowest-order term in the solution will be related to the witness size of $P$, and we will bound the higher-order terms.  

We will rely on the following notion of a matrix pseudoinverse: 

\begin{definition}
For a matrix $M$ with singular-value decomposition $M = \sum_k m_k \ketbra{k}{k'}$ with all $m_k > 0$~and sets of orthonormal vectors $\{\ket{k}\}$, $\{\ket{k'}\}$, let $M^+ = \sum_k m_k^{-1} \ketbra{k'}{k}$, the \emph{Moore-Penrose pseudoinverse}~of~$M$.  
\end{definition}

If $M$ is invertible, then $M^+ = M^{-1}$.  In general, $M M^+ =
\sum_k \ketbra{k}{k}$ is the orthogonal projection onto the range of
$M$.  If $\ket b$ is in the range of $M$, then 
\[
M^+ \ket{b} = {\arg \min}_{\ket{x} : M \ket{x} = \ket{b}} \norm{
  \ket{x} }\,.
\]
A convenient identity, immediate from the singular-value decomposition, is $M^+ = (M^\adjoint M)^+ M^\adjoint = M^\adjoint (M M^\adjoint)^+$.  The norms of pseudoinverses can be bounded using the following claim: 

\begin{claim} \label{t:hyperplanes}
For matrices $A$ and $B$ with $\Range(B^\adjoint) \subseteq \Range(A)$ (\ie, $B = B A A^+$), $\norm{A (B A)^+} \leq \norm{B^+}$ and $\norm{(B A)^+} \leq \norm{A^+} \norm{B^+}$.  
\end{claim}
\begin{proof}
Since $A (B A)^+ = A (B A)^+ B B^+ = \big[A (BA)^+ (BA) A^+\big] B^+$ and the bracketed term is a projection, $\norm{A (B A)^+} \leq \norm{B^+}$.  
The second claimed bound follows, since $(B A)^+ = A^+ \cdot A (B A)^+$.  
\end{proof}


\subsubsection{Equivalent expressions for the witness size} \label{s:equivalentwsizeexpressions}

\begin{lemma} \label{t:spcinterpretation}
For $S$ any positive-definite, diagonal matrix, let 
\begin{align} \label{e:wsizexSdef}
\wsizexS P x S &= \left\{ \begin{array}{cc}
\smallskip
\min_{\ket w : A \Pi \ket{w} = \ket{t}} \norm{S \ket{w}}^2 & \text{if $f_P(x) = 1$,} \\
\min_{\substack{\ket{w'} : \braket{t}{w'} = 1 \\ \Pi A^\adjoint \ket{w'} = 0}} \norm{S A^\adjoint \ket{w'}}^2 & \text{if $f_P(x) = 0$.}
\end{array}\right. 
\intertext{Then if $f_P(x) = 1$,}
\label{e:spcinterpretationtrue}
\wsizexS P x S
&= { \min_{\substack{\ket w : \bra{w} \Pi \ket{w} = 1 \\ \ACJ \Pi S^{-1} \ket{w} = 0}} \abs{ \bra{\alto} \Pi S^{-1} \ket{w} }^{-2} } \\
&= \norm{ (A \Pi S^{-1})^+ \ket{t} }^2 \nonumber \\
&= \norm{ (\Pi - (\ACJ \Pi S^{-1})^+ \ACJ \Pi S^{-1}) S^{-1} \ket{\alto} }^{-2} \nonumber \\
\intertext{and, if $f_P(x) = 0$, letting $\Pim = \identity - \Pi$, $\Delta = \ACJ \Pi (\ACJ \Pi)^+$ and $\Deltam = \identity - \Delta$, }
\label{e:spcinterpretationfalse}
\wsizexS P x S
&= { \min_{\substack{\ket{w'} : \norm{S A^\adjoint \ket{w'}} = 1 \\ \Pi A^\adjoint \ket{w'} = 0}} \abs{ \braket{t}{w'} }^{-2} } \\
&= \norm{ \big(\identity + (\Pim (A S)^+ A S - \identity)^+ \Pi \big) (A S)^+ \ket{t} }^{-2} \nonumber \\
&= \norm{(\identity-(\Deltam \ACJ S)^+ \Deltam \ACJ S) S (\identity - \ACJ^\adjoint (\Pi \ACJ^\adjoint)^+) \ket{\alto}}^2 \nonumber
 \, .
\end{align}
Moreover,
\begin{align*}
\ket{w_S^*} &= {\arg \min}_{\ket w : A \Pi \ket{w} = \ket{t}} \norm{S \ket{w}}^2 = S^{-1} (A \Pi S^{-1})^+ \ket t \mbox{ has norm $\norm{\ket{w_S^*}} = O(1)$ and} \\
\ket{w_S'^*} &= 
{\arg \min}_{\substack{\ket{w'} : \braket{t}{w'} = 1 \\ \Pi A^\adjoint \ket{w'} = 0}} \norm{S A^\adjoint \ket{w'}}^2
= \ket t - (\Pi \ACJ^\adjoint)^+ \Pi \ket{\alto} - (S \ACJ^\adjoint \Deltam)^+ S (\identity - \ACJ^\adjoint (\Pi \ACJ^\adjoint)^+) \ket{\alto}
\end{align*}
has norm $\norm{\ket{w_S'^*}} = O(1)$.
\end{lemma}

\begin{proof}
Assume $f_P(x) = 1$.  Since $\ket t$ is in the range of $A \Pi$, 
\[
\min_{\ket w : A \Pi S^{-1} \ket{w} = \ket{t}} \norm{\ket{w}}^2 =
\norm{ (A \Pi S^{-1})^+ \ket{t} }^2\,.
\]
This is the second of the three expressions for $\wsizexS P x S$ in
Equation~\eqnref{e:spcinterpretationtrue}.  The other two expressions
follow by basic geometry: in general, for a vector $\ket v \in \R^m$
and a subspace $V $, 
\[
\min_{\ket w \in V : \braket v w = 1} \norm{\ket w}^2 = \min_{w \in V
  : \norm{\ket w} = 1} \abs{\braket v w}^{-2} = \norm{\Pi_V \ket
  v}^{-2}\,,
\]
where $\Pi_V$ is the orthogonal projection onto~$V$.  Substitute $\ket v = S^{-1} \Pi \ket{\alto}$ and $V = \Kernel(\ACJ \Pi S^{-1})$ to complete the proof of Equation~\eqnref{e:spcinterpretationtrue}.  

Next assume $f_P(x) = 0$.  As above, 
\[
\min_{\substack{\ket{w'} : \braket{t}{w'} = 1 \\ \Pi A^\adjoint
    \ket{w'} = 0}} \norm{S A^\adjoint \ket{w'}}^2 =
\min_{\substack{\ket{w'} : \norm{S A^\adjoint \ket{w'}} = 1 \\ \Pi
    A^\adjoint \ket{w'} = 0}} \abs{ \braket{t}{w'} }^{-2}\,.
\]  
Now, without loss of generality, $\ket{t} \in \Range(A) = \Range(A S)$, since otherwise $f_P$ is false on every input.  Therefore, $\braket{t}{w'} = \bra{t} (S A^\adjoint)^+ (S A^\adjoint) \ket{w'} = \bra{t} (S A^\adjoint)^+ \ket w$ if $\ket w= S A^\adjoint \ket{w'}$.  We want to find the length-one vector $\ket w$ that is in the range of $S A^\adjoint$ and also of $\Pim$, and that maximizes $\abs{ \bra{t} (S A^\adjoint)^+ \ket w }^2$.  The answer is clearly the normalized projection of $(A S)^+ \ket{t}$ onto the intersection $\Range(S A^\adjoint) \cap \Range(\Pim)$.  In general, given two projections $\Pi_1$ and $\Pi_2$, the projection onto the intersection of their ranges can be written $\identity - (\Pi_1 \Pi_2 - \identity)^+ (\Pi_1 \Pi_2 - \identity)$.  Substituting $\Pi_1 = \Pim$ and $\Pi_2 = (A S)^+ A S$ gives the second claimed expression. 

Finally, we show that 
\[
\min_{\substack{\ket{w'} : \braket{t}{w'} = 1 \\ \Pi A^\adjoint
    \ket{w'} = 0}} \norm{S A^\adjoint \ket{w'}}^2 =
\norm{(\identity-(\Deltam \ACJ S)^+ \Deltam \ACJ S) S (\identity -
  \ACJ^\adjoint (\Pi \ACJ^\adjoint)^+) \ket{\alto}}^2\,.
\]
Since $f_P(x) = 0$, $\ket t$ does not lie in the span of the available input vectors, $\ket t \notin \Range(A \Pi)$, or equivalently $\Pi \ket\alto \in \Range(\Pi \ACJ^\adjoint)$.  Therefore, there exists a vector $\ket{w'} = \ket{t} + \ket{b_C}$ that is orthogonal to the span of the columns of $A \Pi$ and has inner product one with $\ket t$.  Any such $\ket{b_C}$ has the form 
\[
\ket{b_C} = - (\Pi \ACJ^\adjoint)^+ \Pi \ket{\alto} + \Deltam \ket{v} \, ,
\]
where $\ket{v}$ is an arbitrary vector with $\braket{t}{v} = 0$.  We want to choose $\ket v$ to minimize the squared length of 
\begin{align*}
\Pim S A^\adjoint \ket{w'} &= 
S \Pim (\ket{\alto} + \ACJ^\adjoint \ket{b_C}) \nonumber \\
&= S (\identity - \ACJ^\adjoint (\Pi \ACJ^\adjoint)^+) \ket{\alto} + S \ACJ^\adjoint \Deltam \ket{v} 
 \, .
\end{align*}
The answer is clearly the squared length of $S (\identity - \ACJ^\adjoint (\Pi \ACJ^\adjoint)^+) \ket{\alto}$ projected to the orthogonal complement of the range of $S \ACJ^\adjoint \Deltam$, as claimed.  This corresponds to setting $\ket{v} = -(S \ACJ^\adjoint \Deltam)^+ S (\identity - \ACJ^\adjoint (\Pi \ACJ^\adjoint)^+) \ket{\alto}$.

The norms of $\ket{w_S^*}$ and $\ket{w_S'^*}$ are bounded using \claimref{t:hyperplanes}.  
\end{proof}

It is immediate that $\wsizexS P x s$ is monotone increasing in each input complexity $\si_i$. In the other direction, we can show the following estimates: 

\begin{lemma} \label{t:wsizefudgefactors}
Let $S$ and $T$ be any positive-definite diagonal matrices.  Then 
\begin{align}
\label{e:wsizefudgefactorstimes}
\wsizexS P x {S \sqrt{1+T}} &\leq \wsizexS P x S \cdot (1 + \norm{T}) \,, \\
\label{e:wsizefudgefactorsplus}
\wsizexS P x {\sqrt{S^2 + T^2}} &\leq \wsizexS P x S + O(\norm{T}^2)
 \, .
\end{align}
\end{lemma}
\begin{proof}
Equation~\eqnref{e:wsizefudgefactorstimes} is immediate from the definition in Equation~\eqnref{e:wsizexSdef}.  To derive Equation~\eqnref{e:wsizefudgefactorsplus}, first note that $\norm{\sqrt{S^2 + T^2} \ket v}^2 = \norm{S \ket v}^2 + \norm{T \ket v}^2$.  Then when $f_P(x) = 1$, 
\[
\min_{\ket w : A \Pi \ket w = \ket t} (\norm{S \ket w}^2 + \norm{T \ket w}^2)
\leq
\norm{S \ket{w_S^*}}^2
+ \norm{T \ket{w_S^*}}^2 = 
\wsizexS P x S
+ O(\norm{T}^2) \, ,
\]
where we have used that 
\[
\ket{w_S^*} = \argmin_{\ket w  : A \Pi \ket w = \ket t} \norm{S
  \ket w}^2
\]
has norm $\norm{\ket{w_S^*}} = O(1)$ by \lemref{t:spcinterpretation}.  The argument when $f_P(x) = 0$ is similar:
\begin{equation*}
\min_{\substack{\ket{w'} : \braket{t}{w'} = 1 \\ \Pi A^\adjoint \ket{w'} = 0}} (\norm{S A^\adjoint \ket{w'}}^2 + \norm{T A^\adjoint \ket{w'}}^2)
\leq 
\wsizexS P x S + \norm{T A^\adjoint \ket{w_S'^*}}^2 \, ,
\end{equation*}
where 
\[
\ket{w_S'^*} = \argmin_{\substack{\ket{w'} : \braket{t}{w'} = 1 \\
    \Pi A^\adjoint \ket{w'} = 0}} \norm{S A^\adjoint \ket{w'}}^2
\]
has $O(1)$ norm by \lemref{t:spcinterpretation}.  
\end{proof}


\subsubsection{Proof of \texorpdfstring{\thmref{t:strongsmallenergy}}{Theorem~\ref{t:strongsmallenergy}}} \label{s:proof}

Our proof will require two further matrix identities.  First is a special case of the Woodbury matrix inversion formula~\cite{GolubVanloan96matrixcomputations}: for matrices $A$ and $B$ of the correct sizes, if $A$ and $\identity + B^\dagger A^{-1} B$ are invertible, then so is $A + B B^\dagger$, and 
\begin{equation} \label{e:woodbury}
(A + B B^\dagger)^{-1} = A^{-1} - A^{-1} B (\identity + B^\dagger A^{-1} B)^{-1} B^\dagger A^{-1} 
 \, .
\end{equation}
Multiply the right-hand side by $A + B B^\dagger$ to verify the identity.  Second is the following claim: 

\begin{claim} \label{t:ABinverseclaim}
Let $A \succcurlyeq 0$, $B \succ 0$ be positive semi-definite and positive definite matrices, respectively, of the same size, and let $\Delta = A A^+$ and $\Deltam = \identity - \Delta$ be projections onto the range of $A$ and its complement.  Denote by $B_\Deltam^{-1}$ the pseudoinverse $(\Deltam B \Deltam)^+$.  Assume that $A^+ \succcurlyeq A^+ (B - B B_\Deltam^{-1} B) A^+$.  Then $B-A$ is invertible and 
\begin{equation} \label{e:ABinverseclaim}
(B - A)^{-1} 
= 
B_\Deltam^{-1} - (\identity - B_\Deltam^{-1} B) \big( A - \Delta (B - B B_\Deltam^{-1} B) \Delta \big)^+ (\identity - B B_\Deltam^{-1})
 \, .
\end{equation}
\end{claim}

\begin{proof}
By the assumption $A^+ \succcurlyeq A^+ (B - B B_\Deltam^{-1} B) A^+$, $\identity - \sqrt{A^+} (B - B B_\Deltam^{-1} B) \sqrt{A^+}$ is invertible on $\Delta$.  To finish, multiply the claimed expression for $(B-A)^{-1}$ by $B-A$, and simplify using $B_\Deltam^{-1} B = \Deltam + B_\Deltam^{-1} B \Delta$.  
\end{proof}

With the necessary technical tools in place, we are ready to begin our proof.  

\begin{proof}[Proof of \thmref{t:strongsmallenergy}]
  Let $\Pi = \sum_{i \in I(\tilde x)} \ketbra i i$ be the projection
  onto the available inputs~$i$, and let
  \[
  \Pim = \sum_{i \in I \smallsetminus I(\tilde x)} \ketbra i i
  \]
  be the projection onto the other inputs.  With $\ri = \sum_i \ri_{i}
  \ketbra i i$ and $\si = \sum_i \si_{i} \ketbra i i$, we have 
\[
\si = \frac{1}{\lambda} (-\Pi \ri^{-1} + \Pim \ri)\,.
\]
Let 
\[
\rj = (\ri^{-1} - \lambda)^{-1} \quad \text{and} \quad \sj =
\frac1\lambda (-\Pi \rj^{-1} + \Pim \rj)\,.
\]
Whereas $\ri_i$ is the ratio between $a_i$ and the amplitude $b_i$ arriving from deeper in the formula, $-\rj_i$ can be seen to be the ratio between $a_i$ and the amplitude arriving from shallower vertices.  We first claim that $\rj$ and $\sj$ are well-defined: 

\begin{lemma} \label{t:groupedinputs}
Assume that $0 < \lambda \leq {1}/{\sqrt 2}$ and $0 < \si_i \lambda \leq {1}/{\sqrt 2}$ for all $i \in I$.  Then $\rj = (\ri^{-1} - \lambda)^{-1}$ exists.  Moreover, for each input $i$, $\si_i < \sj_i \leq \si_i + 1$.  
\end{lemma}

\begin{proof}
If input $i \in I(\tilde x)$, then using $0 < \si_i = -1/(\lambda \ri_i)$, $\rj_i = (\ri_i^{-1}-\lambda)^{-1}$ exists, and $\sj_i = -1 / (\lambda \rj_i) = \si_i + 1$.  If input $i \notin I(\tilde x)$, then using $\ri_i = \si_i \lambda < 1$, again $\rj_i$ exists, and $\sj_i = \rj_i / \lambda = \si_i / (1 - \si_i \lambda^2)$.  It follows that $\si_i < \sj_i \leq \si_i + 1$.  
\end{proof}

Next we solve Equations~\eqnref{e:zeroenergyequations} and~\eqnref{e:inputratios} to derive an exact expression for $\ri_O$: 

\begin{lemma}
Any solution to Equations~\eqnref{e:zeroenergyequations} and~\eqnref{e:inputratios} has $a_O = r_O b_O$, where 
\begin{equation} \label{e:gadgetgeneralratio}
\ri_{O} 
= \lambda + \bra\alto \Big( \rj - \lambda \rj \ACJ^\adjoint (\lambda^2 + \lambda \ACJ \rj \ACJ^\adjoint)^{-1} \ACJ \rj \Big) \ket\alto
 \, ,
\end{equation}
provided that $\rj = (\ri^{-1} - \lambda)^{-1}$ exists and $\lambda^2 + \lambda \ACJ \rj \ACJ^\adjoint$ is invertible.
\end{lemma}

\begin{proof}
Substituting Equations~\eqnref{e:inputratios}
and~\eqnref{e:zeroenergyequationsbC}
into~\eqnref{e:zeroenergyequationsaI}, and rearranging terms gives 
\[
\big( \lambda - \ri^{-1}  - \frac 1 {\lambda} \ACJ^\adjoint \ACJ \big)
\ket{a_I} = \ket\alto b_O\,.
\]
{}From Equation~\eqnref{e:zeroenergyequationsbO}, 
\[
a_O = \lambda b_O - \braket \alto {a_I} = \lambda b_O + \bra\alto \left(
\rj^{-1} + \frac1 {\lambda} \ACJ^\adjoint \ACJ\right)^{-1} \ket\alto b_O\,.
\]
Equation~\eqnref{e:gadgetgeneralratio} then follows by the Woodbury identity, Equation~\eqnref{e:woodbury}, provided that $\rj$ and $(\identity + (1/{\lambda}) \ACJ \rj \ACJ^\adjoint)^{-1}$ exist.  
\end{proof}

Let $S = \sqrt{\sj}$, $\cp = \ACJ S^{-1} \Pi$, $\cm = \ACJ S \Pim$, $\cpp = \cp \cp^\adjoint$ and $\cmm = \cm \cm^\adjoint$.  Observe that $\norm{\cmm} = O(\norm{\sj})$ and also, since $\cpp^+ = (\cp^\dagger)^+ \cp^+$, by \claimref{t:hyperplanes} $\norm{\cpp^+} = O(\norm{\sj})$.  Let 
\[
X = \lambda^2 + \lambda \ACJ \rj \ACJ^\adjoint = \lambda^2 (\identity + \cmm) - \cpp\,.
\]
Provided that $X$ is invertible, we have from Equation~\eqnref{e:gadgetgeneralratio} that 
\begin{align} \label{e:rOintermsofX}
\ri_{O} 
&=
\lambda - \frac1{\lambda} \bra\alto S^{-2} \Pi \ket\alto + \lambda \bra\alto S^2 \Pim \ket\alto - \Bigg(\begin{aligned}
\dfrac1{\lambda} \bra\alto S^{-1} \cp^\adjoint X^{-1} \cp S^{-1} \ket\alto + \lambda^3 \bra\alto S \cm^\adjoint X^{-1} \cm S \ket\alto \\
- \lambda \big( \bra\alto S^{-1} \cp^\adjoint X^{-1} \cm S \ket\alto + \bra\alto S \cm^\adjoint X^{-1} \cp S^{-1} \ket\alto \big) 
\end{aligned}\Bigg) \, .  
\end{align}

To evaluate $X^{-1}$, we will apply \claimref{t:ABinverseclaim} with $A = \cpp$ and $B = \lambda^2 (\identity + \cmm)$.  
By a singular-value decomposition $\Deltam \cm = \sum_k m_k
\ketbra{k}{k'}$, we obtain 
\[
\cm^\dagger (\identity + \cmm)_\Deltam^{-1} \cm = \sum_k
\frac{m_k^2}{1+m_k^2} \ketbra{k'}{k'} \prec \identity\,.
\]
Therefore, using our bounds on $\norm{\cpp^+}$ and $\norm{\cm}$,
provided that $\lambda \norm{\sj}$ is at most a sufficiently small
constant, 
\[
\identity - \sqrt{A^+} (B - B B_\Deltam^{-1} B) \sqrt{A^+} = \identity
- \lambda^2 \sqrt{\cpp^+} (\identity + \cmm - \cmm (\identity +
\cmm)_\Deltam^{-1} \cmm) \sqrt{\cpp^+} \succ 0\,.
\]
By \claimref{t:ABinverseclaim}, $X = B-A$ is invertible.  

Substitute Equation~\eqnref{e:ABinverseclaim} and the series expansion 
\[
\big( A - \Delta (B - B B_\Deltam^{-1} B) \Delta \big)^+ =
\sum_{j=0}^{\infty} \sqrt{A^+} \Big[ \sqrt{A^+} (B - B B_\Deltam^{-1}
B) \sqrt{A^+} \Big]^j \sqrt{A^+}
\]
into Equation~\eqnref{e:rOintermsofX}, and collect terms with like powers of $\lambda$.  The lowest-order term is 
\[
-\frac1{\lambda} \bra\alto S^{-2} \Pi \ket\alto + \frac1{\lambda} \bra\alto S^{-1} \cp^\dagger A^+ \cp S^{-1} \ket\alto
= -\frac{1}{\lambda} \norm{(\identity - \cp^+ \cp) S^{-1} \Pi \ket\alto}^2
\]
since $\cp^\dagger A^+ \cp = \cp^\dagger (\cp^\dagger)^+ \cp^+ \cp = \cp^+ \cp$.  Including the other terms gives  
\begin{equation}\begin{split} \label{e:rOfullTaylorseries}
\ri_O 
= 
&-\frac{1}{\lambda} \norm{(\identity - \cp^+ \cp) S^{-1} \Pi \ket\alto}^2 
+ \lambda \Big( 1 + \bra v V \ket v + \norm{(\cp^\dagger)^+ S^{-1} \ket\alto}^2 \Big) \\ 
&+ \sum_{j=0}^{\infty} \lambda^{3 + 2j} \Big\lVert \big(\cp^+ (\identity + \cm V \cm^\dagger) (\cp^\dagger)^+\big)^{j/2} \cp^+ \big( \cm V \ket{v} - (\cp^\dagger)^+ S^{-1} \ket\alto \big) \Big\rVert^2
\end{split}\end{equation}
where we have let $V = \identity - \cm^\dagger (\identity + \cmm)_\Deltam^{-1} \cm \succ 0$ and $\ket v = (S \Pim - \cm^\dagger (\cp^\dagger)^+ S^{-1}) \ket\alto$.  Observe that all coefficients, except the first, are non-negative, and that the coefficient of $\lambda^{3 + 2j}$ is of order $O(\norm{\sj}^{3 + 2j})$.  

\smallskip

When $\varphi(x) = f_P(\tilde x) = 1$, the first term in~\eqnref{e:rOfullTaylorseries} is $-1 / (\lambda \, \wsizexS P {\tilde x} S)$, using the last expression of Equation~\eqnref{e:spcinterpretationtrue} for $\wsizexS P {\tilde x} S$.  Therefore, 
\[
-\lambda \norm{\sj} \ri_O \geq {\wsize P}^{-1} - O(\lambda^2 \norm{\sj}^2) > 0\,,
\]
so $\si_O = -1/(\lambda \ri_O)$ satisfies 
\begin{equation}
\wsizexS P {\tilde x} S \leq \si_O 
\leq \wsizexS P {\tilde x} S \big(1 + O(\lambda^2 \norm{\sj}^2)\big)
 \, .
\end{equation}
In particular, since each $\sj_i \leq \si_i + 1$
(\lemref{t:groupedinputs}), by \lemref{t:wsizefudgefactors}, 
\[
\si_O
\leq \wsizex P {\tilde x} \norm{\si} \big(1 + O(\lambda^2
\norm{\si}^2\big) + O(1)\,.
\]

Assume then that $\varphi(x) = f_P(\tilde x) = 0$, \ie, $\Pi \ket\alto \in \Range(\Pi \ACJ^\adjoint)$.  The first term in~\eqnref{e:rOfullTaylorseries} is zero.  Consider the second term.  Using $\Pi \ACJ^\adjoint (\Pi \ACJ^\adjoint)^+ \ket\alto = \Pi \ket\alto$ and $(\cp^\adjoint)^+ S^{-1} \ket\alto = (\Pi S^{-1} \ACJ^\adjoint)^+ S^{-1} \Pi \ket\alto = (\Pi \ACJ^\adjoint)^+ \ket\alto$, 
\begin{equation*}\begin{split}
\ket{v} 
&= (S \Pim - \cm^\adjoint (\Pi \ACJ^\adjoint)^+) \ket\alto + S \Pi (\identity - \ACJ^\adjoint (\Pi \ACJ^\adjoint)^+) \ket\alto \\
&= S (\identity - \ACJ^\adjoint (\Pi \ACJ^\adjoint)^+) \ket\alto
 \, .
\end{split}\end{equation*}
Furthermore, from the singular-value decomposition of $M = \Deltam
\cm$, one infers that 
\[
V = \identity - M^\adjoint (\identity + M M^\adjoint)^{-1} M =
(\identity - M^+ M) + M^+ (\identity - (\identity + M
M^\adjoint)^{-1}) (M^\adjoint)^+\,.
\]
Substituting this into Equation~\eqnref{e:rOfullTaylorseries}, the second term becomes 
\begin{equation*}
\lambda \Big(\norm{(\identity - \dcm^+ \dcm) \ket{v}}^2 + 1 + \norm{(\Pi C^\dagger)^+ \ket\alto}^2 + \norm{(\identity - (\identity + \Deltam \cmm \Deltam)^{-1})^{1/2} (\cm^\dagger \Deltam)^+ \ket{v}}^2 \Big)
 \, .
\end{equation*}
Moreover, as $\Deltam \ACJ \Pi = 0$, $\Deltam \cm = \Deltam \ACJ S \Pim = \Deltam \ACJ S$.  Therefore, $\norm{(\identity - \dcm^+ \dcm) \ket{v}}^2 = \wsizexS P {\tilde x} S$, using the last expression of Equation~\eqnref{e:spcinterpretationfalse} for $\wsizexS P {\tilde x} S$.  
Also, 
\[
\norm{(\identity - (\identity + \Deltam \cmm \Deltam)^{-1})^{1/2}
  (\cm^\dagger \Deltam)^+ \ket{v}}^2 = O(1)\,,
\]
since $\norm{(\cm^\dagger \Deltam)^+ \ket{v}} = O(\norm{S \dcm^+}) = O(1)$ (\claimref{t:hyperplanes}).  
Thus $\si_O = \ri_O / \lambda$ satisfies 
\begin{equation}\begin{split}
\wsizexS P {\tilde x} S + 1 \leq 
\si_O
&\leq \wsizexS P {\tilde x} S + O(1) + O(\lambda^2 \norm{\sj}^3) \\
&\leq \wsizexS P {\tilde x} s + O(\lambda^2 \norm{\si}^3) + O(1) 
 \, ,
\end{split}\end{equation}
where we have used $\norm{\sj} \leq \norm{\si} + 1$ (\lemref{t:groupedinputs}) and $\wsizexS P {\tilde x} S \leq \wsizexS P {\tilde x} s + O(1)$ (\lemref{t:wsizefudgefactors}).  

Thus in either case $\varphi(x) = 1$ or $\varphi(x) = 0$ we have found 
\[
0 < \si_O \leq \wsizex P {\tilde x} \norm{\si} \big(1 + O(\lambda^2
\norm{\si}^2)\big) + O(1)\,,
\]
as desired.  This concludes the proof of \thmref{t:strongsmallenergy}.  
\end{proof}


\subsection{Span program spectral analysis of \texorpdfstring{$\varphi$}{phi}} \label{s:spectralgap}

To study the spectra of the composed graphs~$G(\varphi, x)$ of \defref{t:formulagraphdef}, and argue that in the case $\varphi(x) = 0$ there is an $\Omega(1/\pi(\varphi))$ spectral gap, we will solve the recursion set up by \thmref{t:strongsmallenergy}: 

\begin{theorem} \label{t:formulaspectrum}
Let $\varphi$ be a formula.  For each node $v$, let $P_v$ be the associated span program and assume that $\wsize{P_v} \geq 1$.  Let $\pi(v)$, $\sigma(v)$ be defined as in Equation~\eqnref{e:subformulacomplexitymeasures}, and let $\bar\sigma(v)$ be given by 
\begin{equation}\begin{split} \label{e:subformulacomplexitymeasures2}
\bar\sigma(v) &= \max_\xi \sum_{w \in \xi} \pi(w)^2
 \, , 
\end{split}\end{equation}
where the maximization is over simple paths in $\varphi$ from $v$ through its inputs to a leaf.  Let $\pi(\varphi), \sigma(\varphi), \bar\sigma(\varphi)$ be the same quantities evaluated at the root of $\varphi$.  Let $C = \max\{ \sigma(\varphi), \bar\sigma(\varphi)/\pi(\varphi)^2 \}$.  For a constant span program $P$, let $\delta_P, \epsilon_P$ be the constants from \thmref{t:strongsmallenergy}.  Let $\delta = \max\{1, \max_v \delta_{P_v} \}$ and $\epsilon = 1/(8 C^3 \delta^2)$.  

For an input $x$, let $G(\varphi, x)$ be the composed graph from \defref{t:formulagraphdef}, and let $\tilde G(\varphi, x)$ be the same except with the weights of edges to the final output vertex scaled by a factor of $f = 1/\sqrt{C \pi(\varphi)}$.  (Equivalently, scale the target vector of the root span program by the same factor~$f$.)  Then, 
\begin{itemize}
\item
If $\varphi(x) = 1$, there exists an eigenvalue-zero eigenvector $\ket{\tilde \psi_0}$ of the adjacency matrix $A_{\tilde G(\varphi, x)}$ with at least half of its weight on the output vertex, \ie, $\abs{\tilde a_O}^2 / \norm{\ket{\tilde \psi_0}}^2 \geq 1/2$.  
\item
If $\varphi(x) = 0$, then $A_{\tilde G(\varphi, x)}$ does not have any
eigenvalue-$\lambda$ eigenvectors with nonzero output
coefficients~$\tilde a_O$ or~$\tilde b_O$ for 
\[
\abs{\lambda} \leq \dfrac{1}{\pi(\varphi)} \min\Big\{ \sqrt{\epsilon /
  \delta}, \min\{1, \min_v \epsilon_{P_v}\} / (2 \delta C) \Big\}\,.
\]
\end{itemize}
\end{theorem}

\begin{proof}
If $\varphi(x) = 1$, then by \lemref{t:eigenvaluezero}, $G(\varphi,
x)$ has an eigenvalue-zero eigenvector $\ket{\psi_0}$ with output
coefficient $a_O$ satisfying
\[
\frac{\abs{a_O}^2}{\norm{\ket{\psi_0}}^2} \geq \frac{1}{\pi(\varphi)
\sigma(\varphi)} \geq f^2\,.
\]
Let $\ket{\tilde \psi_0}$ be the same vector, except with output coefficient $\tilde a_O = \frac{1}{f} a_O$.  Then $\ket{\tilde \psi_0}$ is an eigenvalue-zero eigenvector of $\tilde G(\varphi, x)$, and 
\[
\frac{\abs{\tilde a_O}^2}{\norm{\ket{\tilde \psi_0}}^2} 
= \frac{\frac{1}{f^2} \abs{a_O}^2}{\big(\frac{1}{f^2}-1\big)\abs{a_O}^2 + \norm{\ket{\psi_0}}^2}
\geq \frac{1}{2 - f^2}
 \, .
\]

Now assume that $\varphi(x) = 0$.  By \thmref{t:weakzeroenergy}, there does not exist any eigenvalue-zero eigenvector with $\tilde a_O \neq 0$.  Also $\tilde b_O = 0$ necessarily at $\lambda = 0$ by the constraint $\lambda \tilde a_O = f \tilde b_O$.  

For $\lambda \neq 0$, we need to solve the recursion from \thmref{t:strongsmallenergy}, then impose the final output vertex constraint.  The base cases are: at a false input, by the eigenvalue-$\lambda$ constraint for a path of length one, $a_i = \lambda b_i$, so $\si_i = 1$; and at a true input, by the eigenvalue-$\lambda$ constraints for a path of length two, similarly $\si_i = 1 / (1-\lambda^2)$.  
{}From Equation~\eqnref{e:unifiedsolution}, we have that provided $\abs \lambda \leq \eps_P \min\{ 1, 1/ \max_i \si_i \}$, 
\begin{equation*}
s_O < \wsize P \cdot \max_i \si_i \cdot (1 + \delta_P \lambda^2 \max_i \si_i^2) + \delta_P
 \, .
\end{equation*}
The following claim solves this recursion, somewhat conservatively, assuming that $\abs{\lambda}$ is sufficiently small.  

\begin{claim} \label{t:recursionsolution}
Define a quantity $s(v)$ recursively by 
\begin{equation}\begin{split} \label{e:recursionsolution}
s(v) = \begin{cases} 
2 & \text{if $v$ is a leaf of $\varphi$}, \\
\wsize{P_v} \max_c s(c) \Big( 1 + \epsilon \frac{\max_c s(c)^2}{\pi(\varphi)^2} \Big) + \delta & \text{otherwise,}
\end{cases}
\end{split}\end{equation}
where in the second case the maximizations are over $v$'s inputs in $\varphi$.  Then $s(v) \leq 2 \delta C \pi(v)$.  
\end{claim}

\begin{proof}
For brevity, let $w_v = \wsize{P_v} \geq 1$.  Define a quantity $s'(v)$ recursively by 
\[
s'(v) = w_v \max_c s'(c) + \delta
 \, ,
\]
for an internal node $v$, and $s'$ at a leaf is $2$.  Then by induction, one finds $s'(v) \leq \delta \pi(v) \sigma(v)$.  (For the induction step, use $s'(v)/\delta \leq w_v \max_c \pi(c) \sigma(c) + 1 \leq \pi(v) \max_c \big(\sigma(c) + 1/\pi(v)\big) = \pi(v) \sigma(v)$.)  Moreover, from their definitions, clearly $s(v) \geq s'(v)$ always.  

Let $D = 2 \delta C$ and assume by induction that $s(c) \leq D \pi(c)$ for each input $c$.  
Then we have from Equation~\eqnref{e:recursionsolution} 
\[
s(v) \leq \frac{w_v \max_c s(c) + \delta}{1 - \epsilon D^2 \frac{\max_c \pi(c)^2}{\pi(\varphi)^2}}
\leq \frac{w_v \max_c s(c) \big(1 + \frac{\delta}{w_v \max_c s'(c)}\big)}{1 - \epsilon D^2 \frac{\pi(v)^2}{\pi(\varphi)^2}}
\leq \frac{\max_c \frac{s(c)}{s'(c)} s'(v)}{1 - \epsilon D^2 \frac{\pi(v)^2}{\pi(\varphi)^2}}
 \, .
\]
The above inequality places a recursive bound on the ratio $s(v) / s'(v)$.  Solve it, using $(1-a)(1-b) \geq 1-a-b$ for $a b \geq 0$, to find 
\[
s(v) \leq \frac{s'(v)}{{1 - \epsilon D^2 \frac{\bar\sigma(v)}{\pi(\varphi)^2}}}\,.
\]
Using $\bar\sigma(v) \leq \bar\sigma(\varphi) \leq C \pi(\varphi)^2$ and $\epsilon = 1/(2 D^2 C)$, therefore $s(v) \leq 2 s'(v) \leq 2 \delta C \pi(v)$, as desired.  
\end{proof}

Therefore, provided that $\abs \lambda \leq \sqrt{\epsilon / \max_v \delta_{P_v}} / \pi(\varphi)$ and $\abs \lambda \leq \min_v \epsilon_{P_v} / (2 \delta C \pi(\varphi))$, we obtain that either $a_O = b_O = 0$ or the final output ratio $s_O = a_O / (\lambda b_O)$ satisfies $0 < s_O < 2 \delta C \pi(\varphi)$.  Here $a_O$ and $b_O$ are the output coefficients for the unscaled graph $G(\varphi, x)$; the same solution works in $\tilde G(\varphi, x)$, except with output coefficients $\tilde a_O = a_O / f$ and $\tilde b_O = b_O$.  

We have not yet used the eigenvector equation at the output vertex, $\lambda \tilde a_O = f \tilde b_O$.  Combining this equation with $f \tilde a_O / (\lambda \tilde b_O) < 2 \delta C \pi(\varphi)$ implies $\abs \lambda > f / \sqrt{2 \delta C \pi(\varphi)} = 1/ (\sqrt{2 \delta} C \pi(\varphi))$.  This contradicts the assumption $\abs \lambda \leq 1 / (2 \delta C \pi(\varphi))$.  Therefore, the adjacency matrix of $\tilde G_P(x)$ cannot have an eigenvalue-$\lambda$ eigenvector with either output coefficient $\tilde a_O$ or $\tilde b_O$ nonzero.  
\end{proof}

\begin{proposition} \label{t:formulaspectrumconstants}
Let $\mathcal{P}$ be a finite set of span programs each with witness size greater than one, and let $\varphi$ be a formula using only the associated gates.  Then in the statement of \thmref{t:formulaspectrum}, the parameters $C$ and~$\delta$ can be bounded above by a function only of $\mathcal P$, independent of $\varphi$, and similarly $\epsilon$ and $\min\{ \sqrt{\epsilon/\delta}, \min\{1, \min_v \epsilon_{P_v}\} / (2 \delta C) \}$ can be bounded below by a positive function of $\mathcal P$.  In particular, when $\varphi(x) = 0$, $A_{\tilde G(\varphi, x)}$ has an $\Omega(1/\pi(\varphi))$ spectral gap for eigenvectors with $\tilde a_O$ or~$\tilde b_O$ nonzero.  
\end{proposition}

\begin{proof}
Since $\mathcal{P}$ is finite, $\max_{v \in \varphi} \delta_{P_v} \leq \max_{P \in \mathcal P} \delta_P < \infty$ and $\min_{v \in \varphi} \epsilon_{P_v} \geq \min_{P \in \mathcal P} \epsilon_P > 0$, bounds independent of~$\varphi$.  Since $C = \max\{ \sigma(\varphi), \bar \sigma(\varphi) / \pi(\varphi)^2 \}$, it remains to show that $\sigma(\varphi)$ and $\bar \sigma(\varphi) / \pi(\varphi)^2$ can each be bounded above by a function only of~$\mathcal P$.  

Recall from Equation~\eqnref{e:subformulacomplexitymeasures} that $\sigma(\varphi) = 1 + \max_\xi \sum_{v \in \xi} {1}/{\pi(v)}$, where the maximization is over simple paths $\xi$ from the root to a leaf.  Note that for a node $v \in \varphi$, having a child $c$, $\pi(v) \geq \wsize{P_v} \pi(c)$.  Therefore, for any fixed path~$\xi$, the sum $\sum_{w \in \xi} {1}/{\pi(w)}$ is term-wise dominated by the geometric series $\sum_{j=0}^{\infty} 1 / (\min_{P \in \mathcal P} \wsize P)^j < \infty$.  

{}From Equation~\eqnref{e:subformulacomplexitymeasures2}, $\bar\sigma(\varphi) / \pi(\varphi)^2 = \max_\xi \sum_{w \in \xi} \pi(w)^2 / \pi(\varphi)^2$.  The first term in the series, for the root of~$\varphi$, is $\pi(\varphi)^2 / \pi(\varphi)^2 = 1$, and the ratio between the term for a node $v$ and for its child $c$ is bounded by $\pi(v)^2 / \pi(c)^2 \leq 1/ \wsize{P_v}^2$.  Therefore $\bar\sigma(\varphi) / \pi(\varphi)^2 < \sum_{j=0}^{\infty} 1 / (\min_{P \in \mathcal P} \wsize P)^{2j} < \infty$.  
\end{proof}

In the following section, we will use this spectral gap, together with the completeness condition in \thmref{t:formulaspectrum}, to develop an $O(\pi(\varphi))$-query quantum algorithm for evaluating $\varphi$.  


\section{Quantum formula-evaluation algorithm} \label{s:algorithm}

Our quantum algorithm for evaluating $\varphi$ will run a quantum walk starting at the output vertex of the graph~$\tilde G(\varphi, x)$ from \thmref{t:formulaspectrum}.  In brief, Szegedy~\cite{Szegedy04walkfocs} has determined a correspondence between random walks and quantum walks, that can be reformulated as a correspondence between continuous-time, Hamiltonian-based quantum walks and discrete-time quantum walks.  This correspondence relates the eigenvectors of the adjacency matrix $A_{\tilde G(\varphi, x)}$ to those of a discrete-time quantum walk, and relates the eigenvalues according to $\lambda \leftrightarrow e^{\pm i \arccos \lambda}$.  If $\varphi(x) = 1$, then the initial state will have large overlap with walk eigenvectors with eigenvalues $e^{\pm i \pi/2} = \pm i$, whereas if $\varphi(x) = 0$, then the walk will have a spectral gap around phases $\pm \pi/2$.  These two cases can therefore be distinguished by phase estimation~\cite{Kitaev95phaseestimation, NagajWocjanZhang09qma}.  

Our original algorithm from earlier versions of this paper~\cite{ReichardtSpalek08spanprogram} has since been generalized.  We therefore only state the main theorem here, and refer the reader to~\cite{Reichardt09spanprogram-arxivandfocs} for a proof.  

\begin{theorem}[{\cite[Theorem~9.1]{Reichardt09spanprogram-arxivandfocs}}] \label{t:phaseestimationalgorithm}
Let $G = (V,E)$ be a complex-weighted graph with Hermitian weighted adjacency matrix $A_G \in \cL(\C^V)$ satisfying $\bra v A_G \ket v \geq 0$ for all $v \in V$.  Let $V_{\text{input}}$ be a subset of degree-one vertices of $G$ whose incident edges have weight one, and partition $V_{\text{input}}$ as $V_{\text{input}} = \bigsqcup_{j \in \{1,\ldots,n\}, b \in \B} V_{j,b}$.  For $x \in \B^n$, define $G(x)$ from $G$ by deleting all edges to vertices in $\cup_{j=1}^{n} V_{j, x_j}$.  Let $A_{G(x)} \in \cL(\C^V)$ be the weighted adjacency of matrix of $G(x)$.  For any $\Lambda \geq 0$, let $\Pi_\Lambda(x)$ be the orthogonal projection onto the span of those eigenvectors of $A_{G(x)}$ with eigenvalues at most $\Lambda$ in magnitude.

Let $f : \cD \rightarrow \B$, with $\cD \subseteq \B^n$.  Let $\mu \in V \smallsetminus V_{\text{input}}$, $\epsilon = \Omega(1)$ and $\Lambda > 0$.  Assume that for all inputs~$x$ with $f(x) = 1$, $\norm{\Pi_0(x) \ket \mu}^2 \geq \epsilon$, and that for all $x$ with $f(x) = 0$, $\norm{\Pi_\Lambda(x) \ket \mu}^2 \leq \epsilon/2$.  Then $f$ can be evaluated by a quantum algorithm with error probability at most $1/3$ using at most $Q = O({\norm{\abst(A_G)}}/{\Lambda})$ input queries, where $\abst(A_G)$ is the entry-wise absolute value of $A_G$.  Moreover, if the maximum degree of a vertex in $G_P$ is $d$, then the time complexity of the algorithm for evaluating $f_P$ is at most a factor of $(\log d) \big(\log (Q \log d) \big)^{O(1)}$ worse, after classical preprocessing and assuming constant-time coherent access to the preprocessed string.  
\end{theorem}

Note that \thmref{t:formulaspectrum} shows a spectral gap in the case $\varphi(x) = 0$, whereas the soundness condition in \thmref{t:phaseestimationalgorithm} requires only the weaker assumption that the initial state have small overlap on the span of the small-eigenvalue eigenvectors, or an ``effective spectral gap.''  

\smallskip

Our formula-evaluation algorithm follows from Theorems~\ref{t:formulaspectrum} and~\ref{t:phaseestimationalgorithm}: 

\begin{theorem} \label{t:result}
Let $\gateset$ be the set of all three-bit Boolean functions.  There exists a quantum algorithm that evaluates an adversary-balanced formula $\varphi(x)$ over~$\gateset$ using $O(\ADVpm(\varphi))$ input queries.  After efficient classical preprocessing independent of the input $x$, and assuming $O(1)$-time coherent access to the preprocessed classical string, the running time of the algorithm is $\ADVpm(\varphi) (\log \ADVpm(\varphi))^{O(1)}$.
\end{theorem}

\begin{proof}
By \thmref{t:formulaspectrum} and \propref{t:formulaspectrumconstants}, the algorithm of \thmref{t:phaseestimationalgorithm} has query complexity $O(\pi(\varphi))$.  By Equation~\eqnref{e:subformulacomplexitymeasures}, $\pi(\varphi)$ equals the maximum product of the span program witness sizes along a simple path from the root to a leaf.  By \thmref{t:wsizegates}, for optimal span programs this equals the product of the general adversary bounds of the gates along the path.  By \thmref{t:weakadversarycomposition}, the general adversary bound $\ADVpm(\varphi)$ is at least the same product, so $\pi(\varphi) = O(\ADVpm(\varphi))$.  

During preprocessing, %
look up the optimal span programs to determine the input-independent weighted edges of $G(\varphi, x)$.  Then factor the graph as required for implementing a discrete-time quantum walk.  In general, for each vertex, store the unitary for one step of the quantum walk from that vertex.  However, structured formulas may allow closed-form solutions, \eg, no preprocessing is needed for the balanced $\MAJ$ formula of \thmref{t:balancedmajority}.  The maximum degree $d$ is a constant, since the span programs all have constant size.  
\end{proof}


\section{Extensions and open problems} \label{s:extensions}

Our formula-evaluation algorithm implies that the general adversary bound lower bounds the least span program witness size: 

\begin{corollary} \label{t:adversarywsize}
The general adversary bound lower bounds the least span program witness size for any total Boolean function~$f$: 
\begin{equation} \label{e:adversarywsize}
\inf_{P : f_P = f} \wsize P \geq \ADVpm(f)
 \, .
\end{equation}
\end{corollary}

\begin{proof}
Fix $f$ and let~$f^d$ be the depth~$d$ balanced formula in which every gate is~$f$.  Let $P$ be any span program with $f_P = f$.  Then by Theorems~\ref{t:adversaryquerybound} and~\ref{t:weakadversarycomposition}, the quantum query complexity of evaluating~$f^d$ satisfies $Q(f^d) \geq \ADVpm(f^d) \geq \ADVpm(f)^d$, whereas by Theorems~\ref{t:formulaspectrum} and~\ref{t:phaseestimationalgorithm}, $Q(f^d) = O(\wsize P^d)$, where the hidden constant may depend on~$f$ but not on~$d$.  Equation~\eqnref{e:adversarywsize} follows by letting~$d$ tend to infinity.  
\end{proof}

Subsequent work has shown that this inequality is tight; the least span program witness size equals the general adversary bound for any Boolean functions, total or partial~\cite{Reichardt09spanprogram-arxivandfocs}.  Furthermore, by giving an algorithm for evaluating arbitrary span programs, and not only the repeatedly composed span programs that arise in formula evaluation, it has been shown that the general adversary bound equals the bounded-error quantum query complexity, up to constant factors~\cite{Reichardt09spanprogram-arxivandfocs, Reichardt10advtight, LeeMittalReichardtSpalekSzegedy11stateconversion}.  

Although the relationship between span programs, the general adversary bound and quantum query complexity has been resolved, there remain numerous open problems, including most of the problems from our earlier work~\cite{AmbainisChildsReichardtSpalekZhang07andor}.  Specifically, for evaluating formulas, the optimal quantum query algorithm may or may not also have a time-efficient implementation.  Time-efficient and query-optimal or nearly query-optimal algorithms for formula evaluation have been studied further in~\cite{Reichardt09unbalancedformula, Reichardt09andorfaster}.  In~\cite{Reichardt09unbalancedformula}, it is shown that our exact balance condition can be relaxed to allow a constant-factor imbalance in the adversary bounds of the inputs to any gate, and the optimal quantum query algorithm can still be implemented time efficiently.  In~\cite{Reichardt09andorfaster}, it is shown using a new span program composition technique that for arbitrary AND-OR formulas, without any balance condition, there exists a time-efficient evaluation algorithm that uses only $O(\log n)$ times as many queries as the query-optimal algorithm.  Is this tradeoff between query-optimality and time-efficiency a general phenomenon?  Can classical formula rebalancing results~\cite{bb:size-depth, bce:size-depth} allow further relaxed balanced conditions?  Finally, when can the preprocessing step of our algorithm be eliminated?  

Span programs are also a promising tool for designing new quantum algorithms for problems beyond evaluating formulas.  


\subsection*{Acknowledgements}

We thank Troy Lee for pointing out that our \defref{t:spanprogramdef} corresponds to span programs.  We thank Andrew Childs, Sean Hallgren, Cris Moore, David Yonge-Mallo and Shengyu Zhang for helpful conversations.  

B.R.\ received support from NSF Grants CCF-0524828 and PHY-0456720, and from ARO Grant W911NF-05-1-0294.  R.{\v S}.\ received support from NSF Grant CCF-0524837 and ARO Grant DAAD 19-03-1-0082.  


\bibliographystyle{tocplain}   %
%
%
%
%
\bibliography{v008a013}

%
%
%
%
\begin{tocauthors}
\begin{tocinfo}[ben]
 Ben Reichardt\\
 Department of Electrical Engineering\\
 University of Southern California, Los Angeles, CA\\
 ben.reichardt\tocat{}usc\tocdot{}edu \\
 \url{http://www-bcf.usc.edu/~breichar}
\end{tocinfo}
\begin{tocinfo}[robert]
 Robert {\v S}palek\\
 %
  Google, Mountain View, CA  \\
  spalek\tocat{}google\tocdot{}com \\
  \url{http://www.ucw.cz/~robert}
\end{tocinfo}
\end{tocauthors}

%
%
%
%
%
%
%
%
%
%
%
%
%
\begin{tocaboutauthors}
\begin{tocabout}[ben]
  \textsc{Ben Reichardt} graduated from 
  \href{http://www.cs.berkeley.edu/}{UC Berkeley} in 2006,
  advised by 
  \href{http://www.cs.berkeley.edu/~vazirani}{Umesh Vazirani}.  
  He studies algorithms and
  fault-tolerance schemes for quantum computers, and quantum
  cryptography.
\end{tocabout}
\begin{tocabout}[robert]

  \textsc{Robert {\v S}palek} obtained his \phd\ in Theoretical
  Computer Science from 
  \href{http://www.cwi.nl/}{CWI, Amsterdam} in 2006, under the
  supervision of 
  \href{http://www.cwi.nl/people/552}{Harry Buhrman}.  
His thesis focused on quantum
  algorithms and quantum query lower bounds, and these are his main
  research interests till today.  He spent one year as a postdoc at
  UC Berkeley.  Since 2007, he has  %
  been working 
  as a software engineer in the 
  \href{http://googleblog.blogspot.ca/2008/05/introduction-to-google-search-quality.html#!/2008/05/introduction-to-google-search-quality.html}{search quality team at Google}.  
  He grew up in the Czech
  Republic, and now lives in the San Francisco Bay Area with his
  wife Raina and two little sons who take most of his time.  His
  hobbies include reading, photography, and hiking.
\end{tocabout}
\end{tocaboutauthors}

\end{document}
