††thanks: SJ completed parts of this work while at the Institute for Quantum
Information and Matter (IQIM), Caltech††thanks: SK completed parts of this
work while at the Joint Center for Quantum Information and Computer Science
(QuICS), University of Maryland

# Quantum Algorithms for Graph Connectivity
and Formula Evaluation

Stacey Jeffery<EMAIL_ADDRESS>QuSoft and CWI, Amsterdam, the Netherlands
Shelby Kimmel<EMAIL_ADDRESS>Middlebury College, Middlebury, VT, USA

###### Abstract

We give a new upper bound on the quantum query complexity of deciding
$st$-connectivity on certain classes of planar graphs, and show the bound is
sometimes exponentially better than previous results. We then show Boolean
formula evaluation reduces to deciding connectivity on just such a class of
graphs. Applying the algorithm for $st$-connectivity to Boolean formula
evaluation problems, we match the $O(\sqrt{N})$ bound on the quantum query
complexity of evaluating formulas on $N$ variables, give a quadratic speed-up
over the classical query complexity of a certain class of promise Boolean
formulas, and show this approach can yield superpolynomial quantum/classical
separations. These results indicate that this $st$-connectivity-based approach
may be the “right” way of looking at quantum algorithms for formula
evaluation.

##  1 Introduction

Deciding whether two points are connected in a network is a problem of
significant practical importance. In this work, we argue that this problem,
$st$-connectivity, is also important as a quantum algorithmic primitive.

Dürr, Heiligman, Høyer, and Mhalla designed a quantum algorithm for deciding
$st$-connectivity that requires $O(|V|^{3/2})$ queries to the adjacency matrix
of a graph on vertex set $V$ [13]. Belovs and Reichardt later discovered an
especially elegant span-program-based quantum algorithm for this problem,
which is time-efficient and requires only logarithmic space [4]. Belovs and
Reichardt’s algorithm improves on the query complexity of Dürr et al.’s
algorithm when the connecting path is promised to be short (if it exists).

Belovs and Reichardt’s $st$-connectivity algorithm has already been adapted or
been used as a subroutine for deciding other graph problems, such as detecting
certain subgraphs [4], deciding whether a graph is a forest [8], and deciding
whether a graph is bipartite [8].

In this work, we modify the span program algorithm used in [4], inheriting its
space and time efficiency, and we restrict to deciding $st$-connectivity on a
class of planar graphs. If the effective resistances of the set of graphs in
question (and their planar duals) are small, then we find the quantum
algorithm requires far fewer queries than suggested by the analysis in [4]. In
fact, we obtain a polynomial to constant improvement in query complexity for
some classes of graphs.

In addition to improving our understanding of the quantum query complexity of
$st$-connectivity problems, we show that Boolean formula evaluation reduces
(extremely naturally) to $st$-connectivity problems of the kind for which our
improved analysis holds. Therefore, finding good algorithms for
$st$-connectivity can lead to good algorithms for Boolean formula evaluation.
While one might not expect that such a reduction would produce good
algorithms, we find the reduction gives optimal performance for certain
classes of Boolean formulas.

Boolean formula evaluation is a fundamental class of problems with wide-
reaching implications in algorithms and complexity theory. Quantum speed-ups
for evaluating formulas like or [15] and the nand-tree [14] spurred interest
in better understanding the performance of quantum algorithms for Boolean
formulas. This research culminated in the development of span program
algorithms [24, 23], which can have optimal quantum query complexity for any
problem [20]. Using span program algorithms, it was shown that $O(\sqrt{N})$
queries are sufficient for any read-once formula with $N$ inputs [22, 20].
Classically, the query complexity of evaluating nand-trees is
$\Theta(N^{.753})$ [25] and the query complexity of evaluating arbitrary read-
once formulas is $\Omega(N^{.51})$ [16].

While there are simple bounds on the quantum query complexity of total formula
evaluation problems, promise versions are still not fully understood. Kimmel
[19] showed that for a certain promise version of nand-trees, called _$k$
-fault trees_, the quantum query complexity is $O(2^{k})$, while Zhan, Kimmel,
and Hassidim [27] showed the classical query complexity is
$\Omega((\log\frac{\log N}{k})^{k})$, giving a _superpolynomial_ quantum
speed-up for a range of values of $k$. More general treatment of when promises
on the inputs give superpolynomial query speed-ups can be found in [1].

Since our analysis of $st$-connectivity shows that graphs with small effective
resistance can be decided efficiently, this in turn means that Boolean formula
evaluation problems with the promise that their inputs correspond to low
resistance graphs can also be evaluated efficiently. This result gives us new
insight into the structure of quantum speed-ups for promise Boolean formulas.

Contributions. We summarize the main results in this paper as follows:

  * •

Improved quantum query algorithm for deciding $st$-connectivity when the input
is a subgraph of some graph $G$ such that $G\cup\\{\\{s,t\\}\\}$ — $G$ with an
additional $st$-edge — is planar.

    * –

The analysis involves the effective resistance of the original graph and its
planar dual.

    * –

We find families of graphs for which this analysis gives exponential and
polynomial improvements, respectively, over the previous quantum analysis in
[4].

  * •

Algorithm for Boolean formula evaluation via reduction to $st$-connectivity.

    * –

Using this reduction, we provide a simple proof of the fact that read-once
Boolean formulas with $N$ input variables can be evaluated using $O(\sqrt{N})$
queries.

    * –

We show both a quadratic and a superpolynomial quantum-to-classical speed-up
using this reduction, for certain classes of promise Boolean formula
evaluation problems.

Open Problems. We would like to have better bounds on the classical query
complexity of evaluating $st$-connectivity problems, as this would provide a
new approach to finding separations between classical and quantum query
complexity. Additionally, our reduction from Boolean formula evaluation to
$st$-connectivity could be helpful in the design of new classical algorithms
for formulas.

Another open problem concerns span programs in general: when can we view span
programs as solving $st$-connectivity problems? This could be useful for
understanding when span programs are time-efficient, since the time-complexity
analysis of $st$-connectivity span programs is straightforward (see Appendix
A.1, [4, Section 5.3], [17, Appendix B]).

An important class of $st$-connectivity-related span programs are those
arising from the learning graph framework, which provides a means of designing
quantum algorithms that is much simpler and more intuitive than designing a
general span program [3]. A limitation of this framework is its one-sidedness
with respect to 1-certificates: whereas a learning graph algorithm is designed
to detect 1-certificates, a framework capable of giving optimal quantum query
algorithms for any decision problem would likely treat 0- and 1-inputs
symmetrically. In our analysis of $st$-connectivity, 1-inputs and 0-inputs are
on equal footing. This duality between 1- and 0-inputs in $st$-connectivity
problems could give insights into how to extend the learning graph framework
to a more powerful framework, without losing its intuition and relative
simplicity.

Organization: Section 2 provides background information. In Section 3, we
describe our improved analysis of the span program algorithm for
$st$-connectivity for subgraphs of graphs $G$ such that $G\cup\\{\\{s,t\\}\\}$
is planar. In Section 4, we show that every formula evaluation problem is
equivalent to an $st$-connectivity problem. In Section 5, we apply these
results to promise nand-trees, for which we are able to prove the most
significant classical/quantum separation using our approach. Also in Section
5, we use these ideas to create an improved algorithm for playing the two-
player game associated with a nand-tree.

##  2 Preliminaries

###  2.1 Graph Theory

For an undirected weighted multigraph $G$, let $V(G)$ and $E(G)$ denote the
vertices and edges of $G$ respectively. In this work, we will only consider
undirected multigraphs, which we will henceforth often refer to as graphs. To
refer to an edge in a multigraph, we will specify the endpoints, as well as a
label $\lambda$, so that an edge is written $(\\{u,v\\},\lambda)$. Although
the label $\lambda$ will be assumed to uniquely specify the edge, we include
the endpoints for convenience. Let
$\overrightarrow{E}(G)=\\{(u,v,\lambda):(\\{u,v\\},\lambda)\in E(G)\\}$ denote
the set of directed edges of $G$. For a planar graph $G$ (with an implicit
planar embedding) let $F(G)$ denote the faces of $G$. We call the infinite
face of a planar graph the _external face_.

For any graph $G$ with connected vertices $s$ and $t$, we can imagine a fluid
flowing into $G$ at $s$, and traveling through the graph along its edges,
until it all finally exits at $t$. The fluid will spread out along some number
of the possible $st$-paths in $G$. Such a linear combination of $st$-paths is
called an _$st$ -flow_. More precisely:

######  Definition 1 (Unit $st$-flow).

Let $G$ be an undirected weighted graph with $s,t\in V(G)$, and $s$ and $t$
connected. Then a _unit $st$-flow_ on $G$ is a function
$\theta:\overrightarrow{E}(G)\rightarrow\mathbb{R}$ such that:

  1. 1.

For all $(u,v,\lambda)\in\overrightarrow{E}(G)$,
$\theta(u,v,\lambda)=-\theta(v,u,\lambda)$;

  2. 2.

$\sum_{v,\lambda:(s,v,\lambda)\in\overrightarrow{E}}\theta(s,v,\lambda)=\sum_{v,\lambda:(v,t,\lambda)\in\overrightarrow{E}}\theta(v,t,\lambda)=1$;
and

  3. 3.

for all $u\in V(G)\setminus\\{s,t\\}$,
$\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}}\theta(u,v,\lambda)=0$.

######  Definition 2 (Unit Flow Energy).

Given a unit $st$-flow $\theta$ on a graph $G$, the _unit flow energy_ is

$\displaystyle
J(\theta)=\sum_{(\\{u,v\\},\lambda)\in{E(G)}}{\theta(u,v,\lambda)^{2}}.$ (1)

######  Definition 3 (Effective resistance).

Let $G$ be a graph with $s,t\in V(G)$. If $s$ and $t$ are connected in $G$,
the _effective resistance_ is $R_{s,t}(G)=\min_{\theta}J(\theta)$, where
$\theta$ runs over all unit $st$-flows. If $s$ and $t$ are not connected,
$R_{s,t}(G)=\infty.$

Intuitively, $R_{s,t}(G)$ characterizes “how connected” the vertices $s$ and
$t$ are. The more, shorter paths connecting $s$ and $t$, the smaller the
effective resistance.

The effective resistance has many applications. In a random walk on $G$,
$R_{s,t}(G)|E(G)|$ is equal to the _commute time_ between $s$ and $t$, or the
expected time a random walker starting from $s$ takes to reach $t$ and then
return to $s$ [9, 2]. If $G$ models an electrical network in which each edge
$e$ of $G$ is a unit resistor and a potential difference is applied between
$s$ and $t$, then $R_{s,t}(G)$ corresponds to the resistance of the network,
which determines the ratio of current to voltage in the circuit (see [11]). We
can extend these connections further by considering weighted edges. A
_network_ consists of a graph $G$ combined with a positive real-valued
_weight_ function $c:E(G)\rightarrow\mathbb{R}^{+}$.

######  Definition 4 (Effective Resistance with weights).

Let ${\cal N}=(G,c)$ be a network with $s,t\in V(G)$. The _effective
resistance of $\cal N$_ is $R_{s,t}({\cal
N})=\min_{\theta}\sum_{(\\{u,v\\},\lambda)\in
E(G)}\frac{\theta(u,v,\lambda)^{2}}{c(\\{u,v\\},\lambda)}$, where $\theta$
runs over all unit $st$-flows.

In a random walk on a network, which models any reversible Markov chain, a
walker at vertex $u$ traverses edge $(\\{u,v\\},\lambda)$ with probability
proportional to $c(\\{u,v\\},\lambda)$. Then the commute time between $s$ and
$t$ is $R_{s,t}({\cal N})\sum_{e\in E(G)}c(e)$. When $\cal N$ models an
electrical network in which each edge $e$ represents a resistor with
resistance $1/c(e)$, then $R_{s,t}({\cal N})$ corresponds to the resistance of
the network.

When $G$ is a single edge $e=(\\{s,t\\},\lambda)$ with weight $c(e)$, then the
resistance $R_{s,t}(G)=1/c(e)$. When calculating effective resistance,
$R_{s,t}$, we use the rule that for edges in series (i.e., a path), or more
generally, graphs connected in series, resistances add. Edges in parallel, or
more generally, graphs connected in parallel, follow the rule that
conductances in parallel add, where the _conductance_ of a graph is given by
one over the resistance. (The conductance of an edge $e$ is equal to $c(e),$
the weight of the edge.) More precisely, it is easy to verify the following:

######  Claim 5.

Let two networks ${\cal N}_{1}=(G_{1},c_{1})$ and ${\cal N}_{2}=(G_{2},c_{2})$
each have nodes $s$ and $t$. If we create a new graph $G$ by identifying the
$s$ nodes and the $t$ nodes (i.e. connecting the graphs in parallel) and
define $c:E(G)\rightarrow\mathbb{R}^{+}$ by $c(e)=c_{1}(e)$ if $e\in E(G_{1})$
and $c(e)=c_{1}(e)$ if $e\in E(G_{2})$, then

$\displaystyle
R_{s,t}(G,c)=\left(\frac{1}{R_{s,t}(G_{1},c_{1})}+\frac{1}{R_{s,t}(G_{2},c_{2})}\right)^{-1}.$
(2)

However, if we create a new graph $G$ by identifying the $t$ node of $G_{1}$
with the $s$ node of $G_{2}$, relabeling this node $v\not\in\\{s,t\\}$ (i.e.
connecting the graphs in series) and define $c$ as before, then

$\displaystyle R_{s,t}(G,c)=R_{s,t}(G_{1},c_{1})+R_{s,t}(G_{2},c_{2}).$ (3)

As a bit of foreshadowing, if we let $R_{s,t}(G_{1},c_{1})$ and
$R_{s,t}(G_{2},c_{2})$ take values $0$, representing false, or $\infty$,
representing true, then clearly (3) computes the function or, since $0+0=0$,
and $0+\infty=\infty+0=\infty+\infty=\infty$. We also have that (2) computes
the and function, if we use $\frac{1}{0}=\infty$ and $\frac{1}{\infty}=0$.

######  Definition 6 ($st$-cut).

Given a graph $G$ with $s,t\in V(G)$, if $s$ and $t$ are not connected, an
_$st$ -cut_ is a function $\kappa:V(G)\rightarrow\\{0,1\\}$ such that
$\kappa(s)=1$, $\kappa(t)=0$, and $\kappa(v)-\kappa(u)=0$ whenever
$\\{u,v\\}\in E(G)$.

In other words, $\kappa$ defines a subset $S\subset V(G)$ such that $s\in S$,
$t\not\in S$, and there is no edge of $G$ with one endpoint in $S$, and one
endpoint in $\overline{S}$. An $st$-cut is a witness that $s$ and $t$ are in
different components of $G$, so no path exists between $s$ and $t.$

Finally, we consider dual graphs:

######  Definition 7 (Dual Graph).

Let $G$ be a planar graph (with an implicit embedding). The _dual_ graph,
$G^{\dagger}$, is defined as follows. For every face $f\in F(G)$,
$G^{\dagger}$ has a vertex $v_{f}$, and any two vertices are adjacent if their
corresponding faces share an edge, $e$. We call the edge between two such
vertices the _dual edge_ to $e$, $e^{\dagger}$. By convention, $e$ and
$e^{\dagger}$ will always have the same label, so that if
$e=(\\{u,v\\},\lambda)$, then
$e^{\dagger}=(\\{v_{f},v_{f^{\prime}}\\},\lambda)$ for $f$ and $f^{\prime}$
the faces of $G$ on either side of the edge $e$.

###  2.2 Span Programs and Quantum Query Algorithms

Span programs [18] were first introduced to the study of quantum algorithms by
Reichardt and Špalek [24]. They have since proven to be immensely important
for designing quantum algorithms in the query model.

######  Definition 8 (Span Program).

A span program $P=(H,U,\tau,A)$ on $\\{0,1\\}^{N}$ is made up of (I) finite-
dimensional inner product spaces $H=H_{1}\oplus\dots\oplus H_{N}$, and
$\\{H_{j,b}\subseteq H_{j}\\}_{j\in[N],b\in\\{0,1\\}}$ such that
$H_{j,0}+H_{j,1}=H_{j}$, (II) a vector space $U$, (III) a non-zero _target
vector_ $\tau\in U$, and (IV) a linear operator $A:H\rightarrow U$. For every
string $x\in\\{0,1\\}^{N}$, we associate the subspace
$H(x):=H_{1,x_{1}}\oplus\dots\oplus H_{N,x_{N}}$, and an operator
$A(x):=A\Pi_{H(x)}$, where $\Pi_{H(x)}$ is the orthogonal projector onto
$H(x)$.

######  Definition 9 (Positive and Negative Witness).

Let $P$ be a span program on $\\{0,1\\}^{N}$ and let $x$ be a string
$x\in\\{0,1\\}^{N}$. Then we call $|w\rangle$ a _positive witness for $x$ in
$P$_ if $|w\rangle\in H(x)$, and $A|w\rangle=\tau$. We define the _positive
witness size of $x$_ as:

$w_{+}(x,P)=w_{+}(x)=\min\\{\left\||w\rangle\right\|^{2}:|w\rangle\in
H(x),A|w\rangle=\tau\\},$ (4)

if there exists a positive witness for $x$, and $w_{+}(x)=\infty$ otherwise.
Let $\mathcal{L}(U,\mathbb{R})$ denote the set of linear maps from $U$ to
$\mathbb{R}.$ We call a linear map $\omega\in\mathcal{L}(U,\mathbb{R})$ a
_negative witness for $x$ in $P$_ if $\omega A\Pi_{H(x)}=0$ and
$\omega\tau=1$. We define the _negative witness size of $x$_ as:

$w_{-}(x,P)=w_{-}(x)=\min\\{\left\|\omega
A\right\|^{2}:{\omega\in\mathcal{L}(U,\mathbb{R}),\omega
A\Pi_{H(x)}=0,\omega\tau=1}\\},$ (5)

if there exists a negative witness, and $w_{-}(x)=\infty$ otherwise. If
$w_{+}(x)$ is finite, we say that $x$ is _positive_ (wrt. $P$), and if
$w_{-}(x)$ is finite, we say that $x$ is _negative_. We let $P_{1}$ denote the
set of positive inputs, and $P_{0}$ the set of negative inputs for $P$. In
this way, the span program defines a partition $(P_{0},P_{1})$ of $[N]$.

For a function $f:X\rightarrow\\{0,1\\}$, with $X\subseteq\\{0,1\\}^{N}$, we
say $P$ _decides_ $f$ if $f^{-1}(0)\subseteq P_{0}$ and $f^{-1}(1)\subseteq
P_{1}$. We can use $P$ to design a quantum query algorithm that decides $f$,
given access to the input $x\in X$ via queries of the form
$\mathcal{O}_{x}:|i,b\rangle\mapsto|i,b\oplus x_{i}\rangle$.

######  Theorem 10 ([21]).

Fix $X\subseteq\\{0,1\\}^{N}$ and $f:X\rightarrow\\{0,1\\}$, and let $P$ be a
span program on $\\{0,1\\}^{N}$ that decides $f$. Let $W_{+}(f,P)=\max_{x\in
f^{-1}(1)}w_{+}(x,P)$ and $W_{-}(f,P)=\max_{x\in f^{-1}(0)}w_{-}(x,P)$. Then
there is a bounded error quantum algorithm that decides $f$ with quantum query
complexity $O(\sqrt{W_{+}(f,P)W_{-}(f,P)})$.

###  2.3 Boolean Formulas

A read-once Boolean formula can be expressed as a rooted tree in which the
leaves are uniquely labeled by variables, $x_{1},\dots,x_{N}$, and the
internal nodes are labeled by gates from the set $\\{\wedge,\vee,\neg\\}$.
Specifically, a node of degree 2 must be labeled by $\neg$ (not), whereas
higher degree nodes are labeled by $\wedge$ (and) or $\vee$ (or), with the
_fan-in_ of the gate being defined as the number of children. The _depth_ of a
Boolean formula is the largest distance from the root to a leaf. We define an
and-or _formula_ (also called a _monotone formula_) as a read-once Boolean
formula for which every internal node is labeled by $\wedge$ or $\vee$.
Restricting to and-or formulas does not lose much generality, since for any
formula, there is an equivalent formula in which all not-gates are at distance
one from a leaf, and such not gates do not affect the query complexity of the
formula. Moreover, although we only consider read-once formulas here, our
techniques can be applied to more general formulas in which a single variable
may label multiple leaves, since this is equivalent to a larger read-once
formula with a promise on the input. Hereafter, when we refer to a _formula_ ,
we will mean an _and -or read-once formula_.

In a slight abuse of notation, at times $x_{i}$ will denote a Boolean
variable, and at times, it will denote a bit instantiating that variable. If
$x\in\\{0,1\\}^{N}$ is an instantiation of all variables labeling the leaves
of a formula $\phi$, then $\phi(x)$ is the value of $\phi$ on that input,
defined as follows. If $\phi=x_{i}$ has depth 0, then $\phi(x)=x_{i}$. If
$\phi$ has depth greater than 0, we can express $\phi$ recursively in terms of
subformulas $\phi_{1},\dots,\phi_{l}$, as
$\phi=\phi_{1}\wedge\dots\wedge\phi_{l}$, if the root is labeled by $\wedge$,
or $\phi=\phi_{1}\vee\dots\vee\phi_{l}$, if the root is labeled by $\vee$. In
the former case, we define $\phi(x)=\phi_{1}(x)\wedge\dots\wedge\phi_{l}(x)$,
and in the latter case, we define
$\phi(x)=\phi_{1}(x)\vee\dots\vee\phi_{l}(x)$. A family of formulas
$\phi=\phi_{N}$ on $N$ variables gives rise to an evaluation problem,
$\textsc{Eval}_{\phi}$, in which the input is a string $x\in\\{0,1\\}^{N}$,
and the output is $\phi_{N}(x)$. If $\phi(x)=0$, we say $x$ is a $0$-instance,
and if $\phi(x)=1$, $x$ is a 1-instance. By $\phi_{1}\circ\phi_{2}$, we mean
$\phi_{1}$ composed with $\phi_{2}$. That is, if
$\phi_{1}:\\{0,1\\}^{N_{1}}\rightarrow\\{0,1\\}$ and
$\phi_{2}:\\{0,1\\}^{N_{2}}\rightarrow\\{0,1\\}$, then
$\phi_{1}\circ\phi_{2}:\\{0,1\\}^{N_{1}N_{2}}\rightarrow\\{0,1\\}$ evaluates
as
$\phi_{1}\circ\phi_{2}(x)=\phi_{1}(\phi_{2}(x^{1}),\dots,\phi_{2}(x^{N_{1}}))$,
where $x=(x^{1},\dots,x^{N_{1}})$ for $x^{i}\in\\{0,1\\}^{N_{2}}$.

An important formula evaluation problem is nand-tree evaluation. A nand-tree
is a full binary tree of arbitrary depth $0pt$ — that is, every internal node
has two children, and every leaf node is at distance $0pt$ from the root — in
which an internal node is labeled by $\vee$ if it is at even distance from the
leaves, or $\wedge$ if it is at odd distance from the leaves. We use
$\textsc{nand}_{0}pt$ to denote a nand-tree of depth $0pt$. While
$\textsc{nand}_{0}pt$ is sometimes defined as a Boolean formula of nand-gates
composed to depth $0pt$, we will instead think of the formula as alternating
and-gates and or-gates — when $0pt$ is even, these two characterizations are
identical. An instance of nandd is a binary string $x\in\\{0,1\\}^{N}$, where
$N=2^{0pt}$. For example, the formula
$\textsc{nand}_{2}(x_{1},x_{2},x_{3},x_{4})=(x_{1}\wedge
x_{2})\vee(x_{3}\wedge x_{4})$ is a nand-tree of depth $2$.
$\textsc{nand}_{0}$ denotes the single-bit identity function.

A nandd instance $x\in\\{0,1\\}^{2^{d}}$ can be associated with a two-player
game on the rooted binary tree that represents nandd, where the leaves take
the values $x_{i}$, as in Figure 5. The game starts at the root node, which we
call the current node. In each round of the game, as long as the current node
is not a leaf, if the current node is at even (respectively odd) distance from
the leaves, Player $A$ (resp. Player $B$) chooses one of the current node’s
children to become the current node. When the current node is a leaf, if the
leaf has value $1$, then Player $A$ wins, and if the leaf has value $0$, then
Player $B$ wins. The sequence of moves by the two players determines a path
from the root to a leaf.

A simple inductive argument shows that if $x$ is a 1-instance of nand-tree,
then there exists a strategy by which Player $A$ can always win, no matter
what strategy $B$ employs; and if $x$ is a $0$-instance, there exists a
strategy by which Player $B$ can always win. We say an input $x$ is
$A$-winnable if it has value 1 and $B$-winnable if it has value $0$.

##  3 Improved Analysis of st-connectivity Algorithm

In this section, we give an improved bound on the runtime of a quantum
algorithm for $st$-connectivity on subgraphs of $G$, where
$G\cup\\{\\{s,t\\}\\}$ is planar.

Let $st$-connG,D be a problem parameterized by a family of multigraphs $G$,
which takes as input a string $x\in D$ where $D\subseteq\\{0,1\\}^{E(G)}$. An
input $x$ defines a subgraph $G(x)$ of $G$ by including the edge $e$ if and
only if $x_{e}=1$. For all $x\in D$, $st$-conn${}_{G,D}(x)=1$ if and only if
there exists a path connecting $s$ and $t$ in $G(x)$. We write $st$-connG when
$D=\\{0,1\\}^{E(G)}$. A quantum algorithm for $st$-connG,D accesses the input
via queries to a standard quantum oracle $O_{x}$, defined
$O_{x}|e\rangle|b\rangle=|e\rangle|b\oplus x_{e}\rangle$.

The authors of [4] present a quantum query algorithm for $st$-connG when $G$
is a complete graph, which is easily extended to any multigraph $G$. We
further generalize their algorithm to depend on some weight function
$c:E(G)\rightarrow\mathbb{R}^{+}$ (a similar construction is also implicit in
[3]). We call the following span program $P_{G,c}$:

$\displaystyle\forall e\in\overrightarrow{E}(G):\;H_{e,0}=\\{0\\},\quad
H_{e,1}=\mathrm{span}\\{|e\rangle\\},\qquad\qquad\qquad
H=\mathrm{span}\\{|e\rangle:e\in\overrightarrow{E}(G)\\}\qquad$ $\displaystyle
U=\mathrm{span}\\{|u\rangle:u\in
V(G)\\},\;\tau=|s\rangle-|t\rangle,\;A=\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\sqrt{c(\\{u,v\\},\lambda)}(|u\rangle-|v\rangle)\langle
u,v,\lambda|.$ (6)

For any choice of weight function $c$, this span program decides $st$-connG,
but as we will soon see, the choice of $c$ may impact the complexity of the
resulting algorithm.

Using $P_{G,c}$ with $c(\\{u,v\\},\lambda)=1$ for all $(\\{u,v\\},\lambda)\in
E(G)$, the authors of Ref. [4] show that the query complexity of evaluating
$st$-connG,D is

$\displaystyle O\left(\sqrt{\max_{x\in D:s,t\textrm{ are
connected}}R_{s,t}(G(x))\times|E(G)|}\right).$ (7)

Their analysis was for the case where $G$ is a complete graph, but it is
easily seen to apply to more general multigraphs $G$. In fact, it is
straightforward to show that this bound can be improved to

$\displaystyle O\left(\sqrt{\max_{x\in D:s,t\textrm{ are
connected}}R_{s,t}(G(x))\times\max_{x\in D:s,t\textrm{ are not
connected}}\left(C_{s,t}(G(x))\right)}\right).$ (8)

where

$\displaystyle
C_{s,t}(G(x))=\begin{cases}\displaystyle\min_{\kappa:\kappa\textrm{ is an
}st\textrm{-cut of }G(x)}\sum_{(\\{u,v\\},\lambda)\in
E(G)}|\kappa(u)-\kappa(v)|&\textrm{ if $s$ and $t$ not connected}\\\
\infty&\textrm{ otherwise. }\end{cases}$ (9)

In particular, when $G$ is a complete graph on vertex set $V$, with the
promise that if an $st$-path exists, it is of length at most $k$, Eq. (7)
gives a bound of $O\left(\sqrt{k}|V|\right).$ In the worst case, when $k=|V|$,
the analysis of [4] does not improve on the previous quantum algorithm of
[13], which gives a bound of $O(|V|^{3/2}$).

In this paper, we consider in particular multigraphs that are planar even when
an additional $st$-edge is added (equivalently, there exists a planar
embedding in which $s$ and $t$ are on the same face), as in graph $G$ in
Figure 1. (In the case of Figure 1, $s$ and $t$ are both on the external
face.) Given such a graph $G$, we define three other related graphs, which we
denote by $\overline{G}$, $\overline{G}^{\dagger}$, and $G^{\prime}$.

We first define the graph $\overline{G}$, which is the same as $G$, but with
an extra edge labeled by $\emptyset$ connecting $s$ and $t.$ We then denote by
$\overline{G}^{\dagger}$ the planar dual of $\overline{G}$. Because every
planar dual has one edge crossing each edge of the original graph, there
exists an edge that is dual to $(\\{s,t\\},\emptyset)$, also labeled by
$\emptyset$. We denote by $s^{\prime}$ and $t^{\prime}$ the two vertices at
the endpoints of
$(\\{s,t\\},\emptyset)^{\dagger}=(\\{s^{\prime},t^{\prime}\\},\emptyset)$.
Finally, we denote by $G^{\prime}$ the graph $\overline{G}^{\dagger}$ except
with the edge $(\\{s^{\prime},t^{\prime}\\},\emptyset)$ removed.

$s$$t$$1$$2$$3$$4$$G$$s$$t$$1$$2$$3$$4$$\emptyset$$\overline{G}$$s$$s^{\prime}$$t^{\prime}$$\emptyset$$\emptyset$$\overline{G}^{\dagger}$$s$$s^{\prime}$$t^{\prime}$$1$$2$$3$$4$${G}^{\prime}$
Figure 1: Example of how to derive $\overline{G},$ $\overline{G}^{\dagger},$
and $G^{\prime}$ from a planar graph $G$ where $s$ and $t$ are on the same
face. $\overline{G}$ is obtained from $G$ by adding an edge
$(\\{s,t\\},\emptyset)$. $\overline{G}^{\dagger}$ is the planar dual of
$\overline{G}$. (In the diagram labeled by $\overline{G}^{\dagger}$,
$\overline{G}$ is the gray graph, while $\overline{G}^{\dagger}$ is black).
$G^{\prime}$ is obtained from $\overline{G}^{\dagger}$ by removing the edge
$(\\{s,t\\},\emptyset)^{\dagger}$. Note that dual edges inherit their labels
(in this case $1,2,3,4,\emptyset$) from the primal edge.

By construction, $G^{\prime}$ will always have the same number of edges as
$G$. Then as $x$ defines a subgraph $G(x)$ of $G$ by including the edge $e$ if
and only if $x_{e}=1$, we let $G^{\prime}(x)$ be the subgraph of $G^{\prime}$
where we include the edge $e^{\dagger}$ if and only if $x_{e}=0$.

If there is no path from $s$ to $t$ in $G(x)$, there must be a cut between $s$
and $t.$ Note that for any $e\in E(G)$, $e\in E(G(x))$ if and only if
$e^{\dagger}\not\in E(G^{\prime}(x))$. Looking at Figure 1, one can convince
oneself that any $s^{\prime}t^{\prime}$-path in $G^{\prime}(x)$ defines an
$st$-cut in $G(x)$: simply define $\kappa(v)=1$ for vertices _above_ the path,
and $\kappa(v)=0$ for vertices _below_ the path.

Let $c$ be a weight function on $E(G)$. Then we define a weight function
$c^{\prime}$ on $E(G^{\prime})$ as $c^{\prime}(e^{\dagger})=1/c(e).$ Then for
every $x$ there will be a path either from $s$ to $t$ in $G(x)$ (and hence
$R_{s,t}(G(x),c)$) will be finite), or a path from $s^{\prime}$ to
$t^{\prime}$ in $G^{\prime}(x)$ (in which case
$R_{s^{\prime},t^{\prime}}(G^{\prime}(x),c^{\prime})$ will be finite).

We can now state our main lemma:

######  Lemma 11.

Let $G$ be a planar multigraph with $s,t\in V(G)$ such that
$G\cup\\{\\{s,t\\}\\}$ is also planar, and let $c$ be a weight function on
$E(G)$. Let $x\in\\{0,1\\}^{E(G)}$. Then
$w_{+}(x,P_{G,c})=\frac{1}{2}R_{s,t}(G(x),c)$ and
$w_{-}(x,P_{G,c})={2}R_{s^{\prime},t^{\prime}}(G^{\prime}(x),c^{\prime})$.

Using Lemma 11 and Theorem 10, we immediately have the following:

######  Theorem 12.

Let $G$ be a planar multigraph with $s,t\in V(G)$ such that
$G\cup\\{\\{s,t\\}\\}$ is also planar. Then the bounded error quantum query
complexity of evaluating $st$-connG,D is

$\displaystyle O\left(\min_{c}\sqrt{\max_{x\in
D:st\textsc{-conn}_{G}(x)=1}R_{s,t}(G(x),c)\times\max_{x\in
D:st\textsc{-conn}_{G}(x)=0}R_{s^{\prime},t^{\prime}}(G^{\prime}(x),c^{\prime})}\right)$
(10)

where the minimization is over all positive real-valued functions $c$ on
$E(G)$.

While it might be difficult in general to find the optimal edge weighting $c$,
any choice of $c$ will at least give an upper bound on the query complexity.
However, as we will see, sometimes the structure of the graph will allow us to
efficiently find good weight functions.

The proof of Lemma 11 is in Appendix A. The positive witness result follows
from generalizing the proof in [4] to weighted multigraphs. The idea is that
an $st$-path witnesses that $s$ and $t$ are connected, as does any linear
combination of such paths — i.e. an $st$-flow. The effective resistance
$R_{s,t}(G(x),c)$ characterizes the size of the smallest possible $st$-flow.

Just as a positive witness is some linear combination of $st$-paths,
similarly, a negative witness turns out to be a linear combination of
$st$-cuts in $G(x)$. But as we’ve argued, every $st$-cut corresponds to an
$s^{\prime}t^{\prime}$-path in $G^{\prime}(x)$. Using the correspondence
between cuts and paths, we have that a negative witness is a linear
combination of $s^{\prime}t^{\prime}$-paths in $G^{\prime}(x)$. This allows us
to show a correspondence between complexity-optimal negative witnesses and
minimal $s^{\prime}t^{\prime}$-flows, connecting $w_{-}(x,P_{G,c})$ to
$R_{s^{\prime},t^{\prime}}(G^{\prime}(x),c^{\prime})$.

In Appendix A.1, we show that if a quantum walk step on the network $(G,c)$
can be implemented time efficiently, then this algorithm is not only query
efficient, but also time efficient. Let

$\displaystyle
U_{G,c}:|u\rangle|0\rangle\mapsto\frac{1}{\sqrt{\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}c(\\{u,v\\},\lambda)}}\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}\sqrt{c(\\{u,v\\},\lambda)}|u\rangle|u,v,\lambda\rangle.$
(11)

Then we show the following.

######  Theorem 13.

Let $P_{G,c}=(H,U,A,\tau)$ be defined as in (3). Let $S_{G,c}$ be an upper
bound on the time complexity of implementing $U_{G,c}$. If $G$ has the
property that $G\cup\\{\\{s,t\\}\\}$ is planar, then the time complexity of
deciding $st$-connG,D is at most

$\displaystyle O\left(\min_{c}S_{G,c}\sqrt{\max_{x\in D:s,t\textrm{ are
connected}}R_{s,t}(G(x),c)\times\max_{x\in D:s,t\textrm{ are not
connected}}R_{s^{\prime},t^{\prime}}(G^{\prime}(x),c^{\prime})}\right).$ (12)

In Appendix A.1, we also show that if the space complexity of implementing
$U_{G,c}$ in time $S_{G,c}$ is $S_{G,c}^{\prime}$, the algorithm referred to
in Theorem 13 has space complexity at most
$O(\max\\{\log|E(G)|,\log|V(G)|\\}+S_{G,c}^{\prime})$.

###  3.1 Comparison to Previous Quantum Algorithm

When $G\cup\\{\\{s,t\\}\\}$ is planar, our algorithm always matches or
improves on the algorithm in [4]. To see this, we compare Eqs. (10) and (8),
and choose $c$ to have value $1$ on all edges of $G$. Then the first terms are
the same in both bounds, so we only need to analyze the second term. However,
using the duality between paths and cuts, we have

$\displaystyle C_{s,t}(G(x))=\left(\textrm{shortest path length from
$s^{\prime}$ to $t^{\prime}$ in }G^{\prime}(x)\right)\geq
R_{s^{\prime}t^{\prime}}(G^{\prime}(x)).$ (13)

To obtain the inequality in Eq. (13), we create an $s^{\prime}t^{\prime}$-flow
on $G^{\prime}(x)$ that has value one on edges on the shortest path from
$s^{\prime}$ to $t^{\prime}$ and zero on all other edges. Such a flow has unit
flow energy equal to the shortest path. However, the true effective resistance
can only be smaller than this, because it is the minimum energy over all
possible $s^{\prime}t^{\prime}$-flows.

We now present two simple examples where our algorithm and analysis do better
than that of [4]. In the first example, we highlight how the change from
$C_{s,t}(G(x))$ to $R_{s^{\prime},t^{\prime}}(G(x))$ in the complexity gives
us an advantage for some graphs. In the second example, we show that being
able to choose a non-trivial weight function $c$ can give us an advantage for
some graphs.

Let $G$ be an $st$-path of length $N$: i.e., $N+1$ vertices arranged in a line
so that each vertex is connected to its neighbors to the left and right by a
single edge, and $s$ and $t$ are the vertices on either end of the line, as in
Figure 2. For some $h\in\\{1,\dots,N\\}$, let
$D=\\{1^{N}\\}\cup\\{x\in\\{0,1\\}^{N}:|{x}|\leq N-h\\}$, where $1^{N}$ is the
all-one string of length $N$, and $|x|$ is the hamming weight of the string
$x$.

$\dots$$G$$s$$t$$\dots$$G^{\prime}$$s^{\prime}$$t^{\prime}$ Figure 2: Example
of graph for which our analysis does better than the analysis of [4], even
with $c=1$ for all edges, under the promise that $G^{\prime}(x)$ always
contains at least $h$ edges, if $s^{\prime}$ and $t^{\prime}$ are connected.

Then, choosing $c$ to have value $1$ on all edges of $G$, we have

$\displaystyle\max_{x\in D:st\textsc{-conn}_{G}(x)=1}R_{s,t}(G(x))=N$ (14)

because the only $x\in D$ such that $s$ and $t$ are connected in $G(x)$ is
$x=1^{N}$, in which case the only unit flow has value $1$ on each edge. This
flow has energy $N$. However

$\displaystyle\max_{x\in
D:st\textsc{-conn}_{G}(x)=0}R_{s^{\prime},t^{\prime}}(G^{\prime}(x))\leq 1/h,$
(15)

because when $s$ and $t$ are not connected in $G(x)$, $G(x)$ has at most $N-h$
edges, so $G^{\prime}(x)$ has at least $h$ edges. Thus we can define a unit
flow with value $1/h$ on each of $h$ parallel edges in $G^{\prime}(x)$, giving
an energy of $1/h.$ On the other hand

$\displaystyle\max_{x\in D:st\textsc{-conn}_{G}(x)=0}C_{s,t}(G(x))=1.$ (16)

In fact, since $C_{s,t}(G(x))$ counts the minimum number of edges
$(\\{u,v\\},\lambda)$ across any cut (i.e. such that $\kappa(u)=1$ and
$\kappa(v)=0$), it is always at least 1, for _any_ $G(x)$ in which an $st$-cut
exists, whereas $R_{s^{\prime},t^{\prime}}(G^{\prime}(x))$ can be as small as
$1/N$ for some $G$.

Choosing $h=\sqrt{N}$ in our example, and applying Eqs. (8) and (10), the
analysis in [4] gives a query complexity of $O(N^{1/2})$ while our analysis
gives a query complexity of $O(N^{1/4})$. In Section 4 we will show that this
bound is tight.

Now consider the graph $G$ in Figure 3. It consists of $N$ edges in a line,
connecting vertices $s,u_{1},\dots,u_{N}$, and then $N$ multi-edges between
$u_{N}$ and $t$. We assign weights $c(e)=1$ for edges $e$ on the path from $s$
to $u_{N}$, and $c(e)=N^{-1}$ for all other edges.

$\dots$$\bm{N^{-1}}$$\bm{N^{-1}}$$\bm{N^{-1}}$$\bm{N^{-1}}$$\bm{N^{-1}}$$\bf{1}$$\bf{1}$$\bf{1}$$\bf{1}$$\bf{1}$$G$$u_{N}$$s$$u_{1}$$u_{2}$$t$$\dots$$G^{\prime}$$s^{\prime}$$t^{\prime}$1111NNNNN
Figure 3: Example of graph for which our analysis does quadratically better
than the analysis of [4] by taking advantage of a non-trivial weight function
$c$. The values of $c$ for each edge of $G$, and of $c^{\prime}$ for each edge
of $G^{\prime},$ are shown in boldface.

Then,

$\displaystyle\max_{x\in D:st\textsc{-conn}_{G}(x)=1}R_{s,t}(G(x),c)=2N,$ (17)

which occurs when only one of the multi-edges between $u_{N}$ and $t$ is
present. In that case, the $N$ edges
$\\{s,u_{1}\\},\\{u_{1},u_{2}\\},\dots,\\{u_{N-1},u_{N}\\}$ each contribute 1
to the effective resistance, and the final edge between $u_{N}$ and $t$
contributes $\frac{1}{c(e)}=N$. Also

$\displaystyle\max_{x\in
D:st\textsc{-conn}_{G}(x)=0}R_{s^{\prime},t^{\prime}}(G^{\prime}(x),c^{\prime})\leq
1,$ (18)

where the maximum occurs when there is only one path from $s^{\prime}$ to
$t^{\prime}$. (If it is the path with $N$ edges, each edge has weight $N$, and
so contributes $1/N$ to the flow energy.) However

$\displaystyle\max_{x\in D:st\textsc{-conn}_{G}(x)=0}C_{s,t}(G(x))=N$ (19)

for a cut across the multi-edges between $u_{N}$ and $t$, and

$\displaystyle\max_{x\in D:st\textsc{-conn}_{G}(x)=1}R_{s,t}(G(x))=N+1,$ (20)

which occurs when only one of the multi-edges between $u_{N}$ and $t$ is
present.

Thus, the analysis in [4] gives a query complexity of $O(N)$ while our
analysis gives a query complexity of $O(N^{1/2})$.

In Section 5 we will give an example where our analysis provides an
exponential improvement over the analysis in [4].

##  4 AND-OR Formulas and st-Connectivity

In this section, we present a useful relationship between and-or formula
evaluation problems and $st$-connectivity problems on certain graphs. As
mentioned in Section 2, for simplicity we will restrict our analysis to read-
once formulas, but the algorithm extends simply to “read-many” formulas. In
this case, we will primarily be concerned with the query complexity: the input
$x=(x_{1},\dots,x_{N})$ to a formula will be given via a standard quantum
oracle $O_{x}$, defined $O_{x}|i\rangle|b\rangle=|i\rangle|b\oplus
x_{i}\rangle$.

Given an and-or formula $\phi$ with $N$ variables, we will recursively
construct a planar multigraph $G_{\phi}$, such that $G_{\phi}$ has two
distinguished vertices labeled by $s$ and $t$ respectively, and every edge of
$G_{\phi}$ is uniquely labeled by a variable $\\{x_{i}\\}_{i\in[N]}$. If
$\phi=x_{i}$ is just a single variable, then $G_{\phi}$ is just a single edge
with vertices labeled by $s$ and $t$, and edge label $x_{i}$. That is
$E(G_{\phi})=\\{(\\{s,t\\},x_{i})\\}$ and $V(G_{\phi})=\\{s,t\\}.$

Otherwise, suppose $\phi=\phi_{1}\wedge\dots\wedge\phi_{l}$. Then $G_{\phi}$
is the graph obtained from the graphs $G_{\phi_{1}},\dots,G_{\phi_{l}}$ by
identifying the vertex labeled $t$ in $G_{\phi_{i}}$ with the vertex labeled
$s$ in $G_{\phi_{i+1}}$, for all $i=1,\dots,l-1$, and labeling the vertex
labeled $s$ in $G_{\phi_{1}}$ by $s$, and the vertex labeled $t$ in
$G_{\phi_{l}}$ by $t$. That is, we connect the graphs
$G_{\phi_{1}},\dots,G_{\phi_{l}}$ _in series_ , as in Figure 4. (For a formal
definition of $G_{\phi}$, see Appendix B).

The only other possibility is that $\phi=\phi_{1}\vee\dots\vee\phi_{l}$. In
that case, we construct $G_{\phi}$ by starting with
$G_{\phi_{1}},\dots,G_{\phi_{l}}$ and identifying all vertices labeled by $s$,
and labeling the resulting vertex with $s$, and identifying all vertices
labeled by $t$, and labeling the resulting vertex by $t$. That is, we connect
$G_{\phi_{1}},\dots,G_{\phi_{l}}$ _in parallel_ (see Figure 4). We note that
graphs constructed in this way are exactly the set of _series-parallel_ graphs
with two terminals (see e.g. [26, Def. 3]), and are equivalent to graphs
without a $K_{4}$ minor [10, 12].

$s$$t$$G_{\phi_{2}}$$s$$t$$G_{\phi_{1}}$$s$$t$$G_{\phi_{3}}$$s$$t$$G_{\phi_{1}\vee\phi_{2}\vee\phi_{3}}$$s$$t$$G_{\phi_{1}\wedge\phi_{2}\wedge\phi_{3}}$
Figure 4: Let $\phi_{1}=x_{1}\wedge x_{2}$, $\phi_{2}=x_{3}\vee(x_{4}\wedge
x_{5})$, and $\phi_{3}=x_{6}$. Then we obtain
$G_{\phi_{1}\wedge\phi_{2}\wedge\phi_{3}}$ by connecting $G_{\phi_{1}}$,
$G_{\phi_{2}}$, and $G_{\phi_{3}}$ in series, and
$G_{\phi_{1}\vee\phi_{2}\vee\phi_{3}}$ by connecting them in parallel.

Note that for any $\phi$, $G_{\phi}$ is planar, and furthermore, both $s$ and
$t$ are always on the same face. Thus, we can define $G_{\phi}^{\prime}$,
$G_{\phi}(x)$ and $G_{\phi}^{\prime}(x)$ as in Section 3. Then we can show the
following:

######  Lemma 14.

Let $\phi$ be any and-or formula on $N$ variables. For every
$x\in\\{0,1\\}^{N}$, there exists a path from $s$ to $t$ in $G_{\phi}(x)$ if
and only if $\phi(x)=1$. Furthermore, for every $x\in\\{0,1\\}^{N}$, there
exists a path from $s^{\prime}$ to $t^{\prime}$ in $G^{\prime}_{\phi}(x)$ if
and only if $\phi(x)=0$.

We give a formal proof of Lemma 14 in Appendix B, but the intuition is that an
or of subformulas, $\phi_{1}\vee\dots\vee\phi_{l}$ evaluates to true if any of
the subformulas evaluates to true, and likewise, if two vertices are connected
by multiple subgraphs in parallel, the vertices are connected if there is a
path in any of the subgraphs. An and of subformulas
$\phi_{1}\wedge\dots\wedge\phi_{l}$ evaluates to true only if every subformula
evaluates to true, and likewise, if two vertices are connected by multiple
subgraphs in series, the vertices are only connected if there is a path
through every subgraph. Thus, we can show by induction that $s$ and $t$ are
connected in $G_{\phi}(x)$ if and only if $\phi(x)=1$. To see that
$s^{\prime}$ and $t^{\prime}$ are connected in $G_{\phi}^{\prime}(x)$ if and
only if $\phi(x)=0$, we can use a similar argument, and make use of the fact
that an $s^{\prime}t^{\prime}$-path in $G_{\phi}^{\prime}(x)$ is an $st$-cut
in $G_{\phi}(x)$.

Lemma 14 implies that we can solve a formula evaluation problem
$\textsc{Eval}_{\phi}$ by solving the associated $st$-connectivity problem, in
which the input is a subgraph of $G_{\phi}$. By our construction, $G_{\phi}$
will always be a planar graph with $s$ and $t$ on the external face, so
moreover, we can apply Theorem 12 to obtain the following.

######  Theorem 15.

For any family $\phi$ of and-or formulas, the bounded error quantum query
complexity of $\textsc{Eval}_{\phi}$ when the input is promised to come from a
set $D$ is

$\displaystyle O\left(\min_{c}\sqrt{\max_{x\in
D:\phi(x)=1}R_{s,t}(G_{\phi}(x),c)\times\max_{x\in
D:\phi(x)=0}R_{s^{\prime},t^{\prime}}(G_{\phi}^{\prime}(x),c^{\prime})}\right),$
(21)

where the minimization is over all positive real-valued functions $c$ on
$E(G_{\phi})$.

###### Proof.

By Lemma 14, the query complexity of Evalϕ on $D$ is at most the query
complexity of $st$-conn${}_{G_{\phi},D}$. Since $G_{\phi}$ is planar, and has
$s$ and $t$ on the same face, we can apply Theorem 12, which immediately
implies the result. ∎

###  4.1 Comparison to Existing Boolean Formula Algorithms

Reichardt proved that the quantum query complexity of evaluating any formula
on $N$ variables is $O(\sqrt{N})$ [22, Corollary 1.6]. Our algorithm recovers
this result:

######  Theorem 16.

Let $\phi$ be a read-once formula on $N$ variables. Then there exists a choice
of $c$ on $E(G_{\phi})$ such that the quantum algorithm obtained from the span
program $P_{G_{\phi},c}$ computes Evalϕ with bounded error in $O(\sqrt{N})$
queries.

We need the following claim, which we prove in Appendix B:

######  Claim 17.

If $\phi=\phi_{1}\vee\phi_{2}\vee\cdots\vee\phi_{l}$, then
$G^{\prime}_{\phi}(x)$ is formed by composing
$\\{G^{\prime}_{\phi_{i}}(x)\\}_{i}$ in series, and if
$\phi=\phi_{1}\wedge\phi_{2}\wedge\cdots\wedge\phi_{l}$, then
$G^{\prime}_{\phi}(x)$ is formed by composing
$\\{G^{\prime}_{\phi_{i}}(x)\\}_{i}$ in parallel.

The intuition behind Claim 17 is the following. Although $G_{\phi}^{\prime}$
is defined via the dual of $G_{\phi}$, which is constructed through a sequence
of series and parallel compositions, $G_{\phi}^{\prime}$ itself can also be
built up through a sequence of series and parallel compositions. For any and-
or formula $\phi$ on $N$ variables, we can define a formula $\phi^{\prime}$ on
$N$ variables by replacing all $\vee$-nodes in $\phi$ with $\wedge$-nodes, and
all $\wedge$-nodes in $\phi$ with $\vee$-nodes. By de Morgan’s law, for all
$x\in\\{0,1\\}^{N}$, $\phi(x)=\neg\phi^{\prime}(\bar{x})$, where $\bar{x}$ is
the entrywise negation of $x$. A simple inductive proof shows that
$G_{\phi^{\prime}}=G_{\phi}^{\prime}$, and for all $x$,
$G_{\phi^{\prime}}(\bar{x})=G_{\phi}^{\prime}(x)$ (see Lemma 35 in Appendix
B).

###### Proof of Theorem 16.

We will make use of the following fact: for any network $(G,c)$, and any
positive real number $W$:

$R_{s,t}(G,c/W)=\min_{\theta}\sum_{e\in
E(G)}\frac{\theta(e)^{2}}{c(e)/W}=W\min_{\theta}\sum_{e\in
E(G)}\frac{\theta(e)^{2}}{c(e)}=WR_{s,t}(G,c).$ (22)

We now proceed with the proof. For any formula $\phi$ in
$\\{\wedge,\vee,\neg\\}$, by repeated applications of de Morgan’s law, we can
push all not-gates to distance-1 from a leaf. Since $x_{i}$ and $\neg x_{i}$
can both be learned in one query, we can restrict our attention to and-or
formulas.

If $\phi$ has only $N=1$ variable, it’s easy to see that
$W_{+}(P_{G_{\phi},c})W_{-}(P_{G_{\phi},c})\leq N$ for $c$ taking value $1$ on
the single edge in $G_{\phi}$. We will prove by induction that this is true
for any $\phi$, for some choice of $c$, completing the proof, since the
complexity of our algorithm obtained from $P_{G_{\phi},c}$ is
$O\left(\sqrt{W_{+}(P_{G_{\phi},c})W_{-}(P_{G_{\phi},c})}\right)$.

Suppose $\phi=\phi_{1}\wedge\dots\wedge\phi_{l}$ for formulas $\phi_{i}$ on
$N_{i}$ variables, so $\phi$ has $N=\sum_{i}N_{i}$ variables. For
$x\in\\{0,1\\}^{N}$, we will let $x^{i}\in\\{0,1\\}^{N_{i}}$ denote the
$(N_{1}+\dots+N_{i-1}+1)$-th to $(N_{1}+\dots+N_{i})$-th bits of $x$. For each
$G_{\phi_{i}}$, by the induction hypothesis, there is some weight function
$c_{i}$ on $E(G_{\phi_{i}})$ such that
$W_{+}(P_{G_{\phi_{i}},c_{i}})W_{-}(P_{G_{\phi_{i}},c_{i}})\leq N_{i}$.

Using our construction, $G_{\phi}$ is formed by composing
$\\{G_{\phi_{i}}\\}_{i}$ in series. Thus every edge $(\\{u,v\\},\lambda)\in
E(G_{\phi})$ corresponds to an edge $(\\{u,v\\},\lambda)\in E(G_{\phi_{i}})$
for some $i$. We create a weight function
$c:E(G_{\phi})\rightarrow\mathbb{R}^{+}$ such that
$c(\\{u,v\\},\lambda)=\frac{c_{i}(\\{u,v\\},\lambda)}{W_{-}(P_{G_{\phi_{i}},c_{i}})}$
if $(\\{u,v\\},\lambda)$ is an edge originating from the graph $G_{\phi_{i}}$.
That is, our new weight function is the same as combining all of the old
weight functions, up to scaling factors
$\\{W_{-}(P_{G_{\phi_{i}},c_{i}})\\}_{i}$.

Using Lemma 11, Claim 5, and Eq. (22), for any 1-instance $x$,

$\displaystyle w_{+}(x,P_{G_{p}hi,c})$
$\displaystyle=\frac{1}{2}R_{s,t}(G_{\phi}(x),c)=\frac{1}{2}\sum_{i=1}^{l}R_{s,t}\left(G_{\phi_{i}}(x),\frac{c_{i}}{W_{-}(P_{G_{\phi_{i}},c_{i}})}\right)$
$\displaystyle=\frac{1}{2}\sum_{i=1}^{l}W_{-}(P_{G_{\phi_{i}},c_{i}})R_{s,t}\left(G_{\phi_{i}}(x),{c_{i}}{}\right)\leq\sum_{i=1}^{l}W_{-}(\phi_{i},P_{G_{\phi_{i}},c_{i}})W_{+}(P_{G_{\phi_{i}},c_{i}}).$
(23)

Thus

$W_{+}(P_{G_{\phi},c})\leq\sum_{i=1}^{l}W_{-}(P_{G_{\phi_{i}},c_{i}})W_{+}(P_{G_{\phi_{i}},c_{i}})\leq\sum_{i=1}^{l}N_{i}=N.$
(24)

Recall that for a weight function $c$ on $G_{\phi}$, we define a weight
function $c^{\prime}$ on $G^{\prime}_{\phi}$ by
$c^{\prime}(e^{\dagger})=1/c(e)$. Then for an edge $e\in
E(G_{\phi_{i}}(x^{i}))$, we have
$c^{\prime}(e^{\dagger})={W_{-}(P_{G_{\phi_{i}},c_{i}})}/{c_{i}(e)}=W_{-}(P_{G_{\phi_{i}},c_{i}})c_{i}^{\prime}(e^{\dagger})$.
By Claim 17, $G^{\prime}_{\phi}$ is formed by composing
$\\{G^{\prime}_{\phi_{i}}\\}_{i}$ in parallel, so by Lemma 11, Claim 5, and
Eq. (22):

$\displaystyle w_{-}(x,P_{G_{\phi},c})$
$\displaystyle=2R_{s^{\prime},t^{\prime}}(G_{\phi}^{\prime}(x),c^{\prime})=2\left(\sum_{i=1}^{l}\frac{1}{R_{s^{\prime},t^{\prime}}(G_{\phi_{i}}^{\prime}(x^{i}),c^{\prime})}\right)^{-1}$
$\displaystyle=2\left(\sum_{i=1}^{l}\frac{1}{R_{s^{\prime},t^{\prime}}(G_{\phi_{i}}^{\prime}(x^{i}),W_{-}(P_{G_{\phi_{i}},c_{i}})c^{\prime}_{i})}\right)^{-1}=2\left(\sum_{i=1}^{l}\frac{W_{-}(P_{G_{\phi_{i}},c_{i}})}{R_{s^{\prime},t^{\prime}}(G_{\phi_{i}}^{\prime}(x^{i}),c^{\prime}_{i})}\right)^{-1}$
$\displaystyle=2\left(\sum_{i=1}^{l}\frac{W_{-}(P_{G_{\phi_{i}},c_{i}})}{w_{-}(x^{i},P_{G_{\phi_{i}},c_{i}})}\right)^{-1}.$
(25)

Whenever $x$ is a 0-instance of $\phi$, the set $S\subseteq[l]$ of $i$ such
that $x^{i}$ is a 0-instance of $\phi_{i}$ is non-empty. This is exactly the
set of $i$ such that $w_{-}(x^{i},P_{G_{\phi_{i}},c_{i}})<\infty$. Continuing
from above, we have:

$w_{-}(x,P_{G_{\phi},c})=\left(\sum_{i\in
S}\frac{W_{-}(P_{G_{\phi_{i}},c_{i}})}{w_{-}(x^{i},P_{G_{\phi_{i}},c_{i}})}\right)^{-1}\leq\left(\sum_{i\in
S}\frac{W_{-}(P_{G_{\phi_{i}},c_{i}})}{W_{-}(P_{G_{\phi_{i}},c_{i}})}\right)^{-1}=\frac{1}{|S|}\leq
1.$ (26)

Thus $W_{-}(P_{G_{\phi_{i}},c_{i}})\leq 1$. Combining this with Eq. (24) we
have $W_{+}(P_{G_{\phi},c})W_{-}(P_{G_{\phi},c})\leq N$, as desired.

The proof for the case $\phi=\phi_{1}\vee\dots\vee\phi_{l}$ is similar. ∎

An immediate corollary of Theorem 16 is the following.

######  Corollary 18.

Deciding $st$-connectivity on subgraphs of two-terminal series-parallel graphs
of $N$ edges can be accomplished using $O(\sqrt{N})$ queries, if $s$ and $t$
are chosen to be the two terminal nodes.

As with many results in this field, characterizing classical complexity seems
to be more difficult than quantum complexity. However, we show we can lower
bound the classical query complexity of a class of Boolean formulas in terms
of the effective resistance of their corresponding graphs, achieving a
quadratic quantum/classical speed-up in query complexity.

We consider and-or formulas on restricted domains. For $N,h\in\mathbb{Z}^{+}$,
let $D_{N,h}=\\{x\in\\{0,1\\}^{N}:|x|=N\textrm{ or }|x|\leq N-h\\}$ and let
$D_{N,h}^{\prime}=\\{x\in\\{0,1\\}^{N}:|x|=0\textrm{ or }|x|\geq h\\}$. We
will analyze and-or formulas such that the input to every gate in the formula
comes from $D_{N,h}$ (in the case of and), which we denote
$\textsc{and}|_{D_{N,h}}$ and $D_{N,h}^{\prime}$ (in the case of or), which we
denote $\textsc{or}|_{D_{N,h}^{\prime}}$. These promises on the domains make
it easier to evaluate both functions. For example, if or evaluates to 1, we
are promised that there will not be just one input with value $1,$ but at
least $h.$

Then using sabotage complexity [5] to bound the classical query complexity, we
have the following theorem, whose (somewhat long, but not technical) proof can
be found in Appendix C:

######  Theorem 19.

Let $\phi=\phi_{1}\circ\phi_{2}\circ\cdots\circ\phi_{l}$, where for each
$i\in[l]$, $\phi_{i}=\textsc{or}|_{D_{N_{i},h_{i}}^{\prime}}$ or
$\phi_{i}=\textsc{and}|_{D_{N_{i},h_{i}}}$. Then the randomized bounded-error
query complexity of evaluating $\phi$ is
$\Omega\left(\prod_{i=1}^{l}N_{i}/h_{i}\right)$, and the bounded-error quantum
query complexity of evaluating $\phi$ is
$O\left(\prod_{i=1}^{l}\sqrt{N_{i}/h_{i}}\right)$.

Note that in the above theorem, when we compose formulas with promises on the
input, we implicitly assume a promise on the input to the composed formula.
More precisely, for $\phi_{1}$ on $D_{1}\subseteq\\{0,1\\}^{N_{1}}$ and
$\phi_{2}$ on $D_{2}\subseteq\\{0,1\\}^{N_{2}}$, $\phi=\phi_{1}\circ\phi_{2}$
is defined on all $x=(x^{1},\dots,x^{N_{1}})\in\\{0,1\\}^{N_{1}N_{2}}$ such
that $x^{i}\in D_{2}$ for all $i\in[N_{1}]$, and
$(\phi_{2}(x^{1}),\dots,\phi_{2}(x^{N_{1}}))\in D_{1}$.

Theorem 19 is proven by showing that

$\displaystyle\frac{\prod_{i=1}^{l}N_{i}}{\prod_{i=1}^{l}h_{i}}=\left(\max_{x\in
D:\phi(x)=1}R_{s,t}(G_{\phi}(x))\right)\left(\max_{x\in
D:\phi(x)=0}R_{s,t}(G^{\prime}_{\phi}(x))\right),$ (27)

and using sabotage complexity to show that this is a lower bound on the
randomized query complexity of $\phi$. This gives us a quadratic separation
between the randomized and quantum query complexities of this class of
formulas. For details, see Appendix C.

Using the composition lower bound for promise Boolean functions of [19], and
the lower bound for Grover’s search with multiple marked items [6], we have
that the quantum query complexity of Theorem 19 is tight. Additionally, in
light of our reduction from Boolean formula evaluation to $st$-connectivity,
we see that our example from Figure 2 in Section 3 is equivalent to the
problem of $\textsc{and}|_{D_{N,h}}$, so our query bound in that example is
also tight.

Based on Theorem 19, one might guess that when evaluating formulas using the
$st$-connectivity reduction, one can obtain at most a quadratic speed-up over
classical randomized query complexity. However, it is in fact possible to
obtain a superpolynomial speed-up for certain promise problems using this
approach, as we will discuss in Section 5.1.

##  5 NAND-tree Results

###  5.1 Query Separations

In this section, we prove two query separations that are stronger than our
previous results. These query separations rely on the nand-tree formula with a
promise on the inputs. This restriction, the $k$-fault promise, will be
defined shortly. Let $F^{d}_{k}$ be the set of inputs to $\textsc{nand}_{d}$
that satisfy the $k$-fault condition. Then the two results are the following:

######  Theorem 20.

Using the $st$-connectivity approach to formula evaluation (Theorem 15), one
can solve $\textsc{Eval}_{\textsc{nand}_{d}}$ when the input is promised to be
from $F^{d}_{\log d}$ with $O(d)$ queries, while any classical algorithm
requires $\Omega(d^{\log\log(d)})$ queries.

For a different choice of $k$, this example demonstrates the dramatic
improvement our $st$-connectivity algorithm can give over the analysis of [4]
— in this case, an exponential (or more precisely, a polynomial to constant)
improvement:

######  Theorem 21.

Consider the problem $st$-$\textsc{conn}_{G_{\textsc{nand}_{d}},F^{d}_{1}}$.
The analysis of [4] gives a bound of $O(N^{1/4})$ quantum queries to decide
this problem (where $N=2^{d}$ is the number of edges in
$G_{\textsc{nand}_{d}}$), while our analysis shows this problem can be decided
with $O(1)$ quantum queries.

We now define what we mean by $k$-fault nand-trees. In [27], Zhan et al. find
a relationship between the difficulty of playing the two-player game
associated with a nand-tree, and the witness size of a particular span program
for $\textsc{nand}_{d}$. They find that trees with fewer _faults_ , or
critical decisions for a player playing the associated two-player game, are
easier to evaluate on a quantum computer. We show that our algorithm does at
least as well as the algorithm of Zhan et al. for evaluating $k$-fault trees.
To see this, we relate fault complexity to effective resistances of
$G_{\textsc{nand}_{d}}(x)$ or $G_{\textsc{nand}_{d}}^{\prime}(x)$.

Consider a nandd instance $x\in\\{0,1\\}^{2^{d}}$, and recall the relationship
between a nand-tree instance and the two-player nand-tree game described in
Section 2.3. We call the sequence of nodes that Player $A$ and Player $B$
choose during the course of a game a path $p$ — this is just a path from the
root of the nand-tree to a leaf node. If $x$ is $Z$-winnable, we call ${\cal
P}_{Z}(x)$ the set of paths where Player $Z$ wins, and Player $Z$ never makes
a move that would allow her opponent to win. That is, a path in ${\cal
P}_{A}(x)$ (resp. ${\cal P}_{B}(x)$) only encounters nodes that are themselves
the roots of $A$-winnable (resp. $B$-winnable) subtrees and never passes
through a node where Player $B$ (resp. Player $A$) could make a decision to
move to a $B$-winnable (resp. $A$-winnable) subtree. Whether a node in the
tree is the root of an $A$-winnable or $B$-winnable subtree can be determined
by evaluating the subformula corresponding to that subtree. See Figure 5 for
an example of ${\cal P}_{A}$. Let $\nu_{Z}(p)$ be the set of nodes along a
path $p$ at which it is Player $Z$’s turn. Thus, $\nu_{A}(p)$ (resp.
$\nu_{B}(p))$ contains those nodes in $p$ at even (resp. odd) distance $>0$
from the leaves.

Zhan et al. call a node $v$ a _fault_ if one child is the root of an
$A$-winnable tree, while the other child is the root of a $B$-winnable tree.
Such a node constitutes a critical decision point. If we let ${f}_{Z}(p)$
denote the number of faults in $\nu_{Z}(p)$, we can define the fault
complexity ${\cal F}(x)$ of input $x$ as111We have actually used the more
refined definition of $k$-fault from [19]. ${\cal F}(x)=\min\\{{\cal
F}_{A}(x),{\cal F}_{B}(x)\\}$, where:

$\displaystyle{\cal F}_{Z}(x)=\begin{cases}2^{\max_{p\in{\cal
P}_{Z}(x)}f_{Z}(p)}&\textrm{ if $x$ is $Z$-winnable}\\\ \infty&\textrm{
otherwise}.\end{cases}$ (28)

For $k=0,\dots,d/2$, the set of $k$-fault trees, $F^{d}_{k}$, are those
instances $x\in\\{0,1\\}^{2^{d}}$ with $\log{\cal F}(x)\leq k$. In these
trees, the winning player will encounter at most $k$ fault nodes on their path
to a leaf. Kimmel [19] shows there exists a span program for evaluating nand-
trees whose witness size for an instance $x$ is at most the fault complexity
${\cal F}(x).$

$1$$p_{1}$$1$$p_{2}$$1$$0$$0$$0$$1$$p_{3}$$1$$p_{4}$$0$$0$$0$$1$$1$$1$$0$$1$$\wedge$$\wedge$$\wedge$$\wedge$$\wedge$$\wedge$$\wedge$$\wedge$$\vee$$\vee$$\vee$$\vee$$\wedge$$\wedge$$\vee$Player
$A$’s First TurnPlayer $B$’s First TurnPlayer $A$’s Second TurnPlayer $B$’s
Second Turn Figure 5: Depiction of a depth-4 nand-tree as a two-player game.
Let $x$ be the input to $\textsc{nand}_{4}$ shown in the figure. This instance
is $A$-winnable, and ${\cal P}_{A}(x)$ consists of the paths
$\\{p_{1},p_{2},p_{3},p_{4}\\}$, shown using solid lines. Fault nodes are
those with double circles. Each path in ${\cal P}_{A}(x)$ encounters two
faults at nodes where Player $A$ makes decisions. Therefore, ${\cal
F}_{A}(x)=4$.

We first show a relationship between effective resistance of
$G_{\textsc{nand}_{d}}(x)$ or $G_{\textsc{nand}_{d}}^{\prime}(x)$ and ${\cal
F}(x)$:

######  Lemma 22.

For any $x\in\\{0,1\\}^{2^{d}}$, if $d$ is even, then we have
$R_{s,t}(G_{\textsc{nand}_{d}}(x))\leq{\cal F}_{A}(x)$ and
$R_{s^{\prime},t^{\prime}}(G^{\prime}_{\textsc{nand}_{d}}(x))\leq{\cal
F}_{B}(x)$, while if $d$ is odd, we have
$R_{s,t}(G_{\textsc{nand}_{d}}(x))\leq 2{\cal F}_{A}(x)$ and
$R_{s^{\prime},t^{\prime}}(G^{\prime}_{\textsc{nand}_{d}}(x))\leq 2{\cal
F}_{B}(x)$.

The proof of Lemma 22 can be found in Appendix D. An immediate corollary of
Lemma 22 and Theorem 15 is the following.

######  Corollary 23.

The span program $P_{G_{\phi}}$ for $\phi=\textsc{nand}_{d}$ decides
$\textsc{Eval}_{\textsc{nand}_{d}}$ restricted to the domain $X$ in
$O(\max_{x\in X}{\cal F}(x))$ queries. In particular, it decides $k$-fault
trees (on domain $F^{d}_{k}$) in $O(2^{k})$ queries.

###### Proof of Theorem 20.

Theorem 20 is now an immediate consequence of Corollary 23, with $k$ set to
$\log(d)$, along with the fact from [27] that the classical query complexity
of evaluating such formulas is $\Omega(d^{\log\log(d)})$. ∎

We will use Corollary 23, along with the following claim, to prove Theorem 21:

######  Claim 24.

Let two graphs $G_{1}$ and $G_{2}$ each have nodes $s$ and $t$ and let
$x^{1}\in\\{0,1\\}^{E(G_{1})}$ and $x^{2}\in\\{0,1\\}^{E(G_{2})}$. Suppose we
create a new graph $G$ by identifying the $s$ nodes and the $t$ nodes (i.e.
connecting the graphs in parallel), then

$\displaystyle
C_{s,t}(G(x^{1},x^{2}))=C_{s,t}(G_{1}(x^{1}))+C_{s,t}(G_{2}(x^{2}))$ (29)

If we create a new graph $G$ by identifying the $t$ node of $G_{1}$ with the
$s$ node of $G_{2}$ and relabeling this node $v\not\in\\{s,t\\}$ (i.e.
connecting the graphs in series), then

$\displaystyle
C_{s,t}(G(x^{1},x^{2}))=\min\\{C_{s,t}(G_{1}(x^{1})),C_{s,t}(G_{2}(x^{2}))\\}.$
(30)

###### Proof of Theorem 21.

Using Corollary 23, our analysis shows that
$st$-$\textsc{conn}_{G_{\textsc{nand}_{d}},F^{d}_{1}}$ can be decided in
$O(1)$ queries.

We apply Eq. (8) to compare to the analysis of [4]. We must characterize the
quantity $\max\\{C_{s,t}(G_{\textsc{nand}_{d}}(x)):x\in F_{1}^{d},\textrm{and
}s,t\textrm{ are not connected}\\}$, since we already have

$\displaystyle\max_{x\in F_{1}^{d}:s,t\textrm{ are
connected}}R_{s,t}(G(x))=O(1).$ (31)

We now prove that for _every_ $x\in\\{0,1\\}^{2^{d}}$ such that
$\textsc{nand}_{d}(x)=0$, $C_{s,t}(G_{\textsc{nand}_{d}}(x))=2^{\lfloor
d/2\rfloor}$. Thus, for any promise $D$ on the input, as long as there exists
some $x\in D$ such that $\textsc{nand}_{d}(x)=0$, we have $\max_{x\in
D:\textsc{nand}_{d}(x)=0}C_{s,t}(G_{\textsc{nand}_{d}}(x))=2^{\lfloor{d/2}\rfloor}$.
Intuitively, this is because every $st$-cut on any subgraph of
$G_{\textsc{nand}_{d}}$ cuts across $2^{\lfloor d/2\rfloor}$ edges of
$G_{\textsc{nand}_{d}}$.

The proof is by induction on $d$. For the base even case, $d=0$ and
$G_{\textsc{nand}_{0}}$ is a single edge connecting $s$ and $t$. The only
input $x\in\\{0,1\\}^{2^{0}}$ such that $\textsc{nand}_{d}(x)=0$ is $x=0$, in
which case, the $st$-cut is $\kappa(s)=1$ and $\kappa(t)=0$, so the cut is
across the unique edge in $G_{\textsc{nand}_{0}}$, so
$C_{s,t}(G_{\textsc{nand}_{0}}(x))=1$.

For the induction step, we treat even and odd separately. Suppose $d>0$ is
odd. Then
$\textsc{nand}_{d}(x)=\textsc{nand}_{d-1}(x^{0})\wedge\textsc{nand}_{d-1}(x^{1})$,
where $x^{0}=(x_{1},\dots,x_{2^{d-1}})$ and
$x^{1}=(x_{2^{d-1}+1},\dots,x_{2^{d}})$. Thus $G_{\textsc{nand}_{d}}(x)$
involves composing two graphs $G_{\textsc{nand}_{d-1}}(x^{0})$ and
$G_{\textsc{nand}_{d-1}}(x^{1})$ in series. Since we are assuming $s$ and $t$
are not connected in $G_{\textsc{nand}_{d}}(x)$, at least one of
$G_{\textsc{nand}_{d-1}}(x^{0})$ and $G_{\textsc{nand}_{d-1}}(x^{1})$ must not
be connected. Without loss of generality, suppose
$G_{\textsc{nand}_{d-1}}(x^{0})$ is not connected and
$C_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))\leq
C_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1}))$. By induction,
$C_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))=2^{(d-1)/2}$. Thus using Eq. (30) in
Claim 24,

$\displaystyle C_{s,t}(G_{\textsc{nand}_{d}}(x))=2^{(d-1)/2}=2^{\lfloor
d/2\rfloor}.$ (32)

Now suppose $d>0$ is even. Then
$\textsc{nand}_{d}(x)=\textsc{nand}_{d-1}(x^{0})\vee\textsc{nand}_{d-1}(x^{1})$.
Thus $G_{\textsc{nand}_{d}}(x)$ involves composing two graphs
$G_{\textsc{nand}_{d-1}}(x^{0})$ and $G_{\textsc{nand}_{d-1}}(x^{1})$ in
parallel. Since we are assuming $s$ and $t$ are not connected in
$G_{\textsc{nand}_{d}}(x)$, both of $G_{\textsc{nand}_{d-1}}(x^{0})$ and
$G_{\textsc{nand}_{d-1}}(x^{1})$ must not be connected, and so by induction,
we have
$C_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))=C_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1}))=2^{\lfloor(d-1)/2\rfloor}=2^{d/2-1}$,
since $d$ is even. Thus using Eq. (29) in Claim 24,

$\displaystyle
C_{s,t}(G_{\textsc{nand}_{d}}(x))=2^{d/2-1}+2^{d/2-1}=2^{d/2}=2^{\lfloor
d/2\rfloor}.$ (33)

Therefore, using Eq. (8), we have that the analysis of [4] for $d$-depth nand-
trees with inputs in $F_{1}^{d}$ gives a query complexity of
$O(\sqrt{2^{\lfloor d/2\rfloor}})=O(N^{1/4})$, where $N=2^{d}$ is the number
of input variables. Comparing with our analysis, which gives a query
complexity of $O(1),$ we see there is a polynomial to constant improvement. ∎

###  5.2 Winning the NAND-tree Game

In this section, we describe a quantum algorithm that can be used to help a
player make decisions while playing the nand-tree game. In particular, we
consider the number of queries to $x$ needed by Player $A$ to make decisions
throughout the course of the game in order to win with probability $\geq 2/3$.
(In this section, we focus on $A$-winnable trees, but the case of $B$-winnable
trees is similar.)

We first describe a naive strategy, which uses a quantum algorithm [21, 23]
that decides if a depth-$0pt$ tree is winnable with bounded error in
$O(2^{d/2}\log d)$ queries. If Player $A$ must decide to move to node $v_{0}$
or $v_{1}$, she evaluates each subtree rooted at $v_{0}$ and $v_{1}$,
amplifying the success probability to $\Omega(1/d)$ by using $O(\log d)$
repetitions, and moves to one that evaluates to 1. Since Player $A$ has $O(d)$
decisions to make, this strategy succeeds with bounded error, and since
evaluating a nand-tree of depth $r$ costs $O(2^{r/2})$ quantum queries, the
total query complexity is:

$O\left(\textstyle 2\sum_{i=0}^{\frac{d}{2}}2^{\frac{d-2i}{2}}\log
d\right)=O\left(2\sum_{i=0}^{\frac{d}{2}}2^{i}\log
d\right)=O\left(2^{\frac{d}{2}}\log d\right)=O\left(\sqrt{N}\log\log
N\right).$ (34)

This strategy does not use the fact that some subtrees may be easier to win
than others. For example, if one choice leads to a subtree with all leaves
labeled by 1, whereas the other subtree has all leaves labeled by 0, the
player just needs to distinguish these two disparate cases. More generally,
one of the subtrees might have a small positive witness size — i.e., it is
very winnable — whereas the other has a large positive witness size — i.e., is
not very winnable.

Our strategy will be to move to the subtree whose formula corresponds to a
graph with smaller effective resistance, unless the two subtrees are very
close in effective resistance, in which case it doesn’t matter which one we
choose. For a depth $d$ game on instance $x$, we show if
$R_{s,t}(G_{\textsc{nand}_{d}}(x))$ is small and Player $B$ plays randomly,
this strategy does better than the naive strategy, on average.

We estimate the effective resistance of both subtrees of the current node
using the witness size estimation algorithm of [17]. In particular, in
Appendix D.2 we prove:

######  Lemma 25 ($\mathtt{Est}$ Algorithm).

Let $\phi$ be an and-or formula with constant fan-in $l$, $\vee$-depth
$d_{\vee}$ and $\wedge$-depth $d_{\wedge}$. Then the quantum query complexity
of estimating $R_{s,t}(G_{\phi}(x))$ (resp. $R_{s,t}(G_{\phi}^{\prime}(x))$)
to relative accuracy $\epsilon$ is
$\widetilde{\mathrm{O}}\left(\frac{1}{\varepsilon^{3/2}}\sqrt{R_{s,t}(G_{\phi}(x))l^{d_{\vee}}}\right)$
(resp.
$\widetilde{\mathrm{O}}\left(\frac{1}{\varepsilon^{3/2}}\sqrt{R_{s,t}(G^{\prime}_{\phi}(x))l^{d_{\wedge}}}\right)$).

Let $\mathtt{Est}(x)$ be the algorithm from Lemma 25 with
$\varepsilon=\frac{1}{3}$, and $\phi=\textsc{nand}_{d}$, so $l=2$, and both
$d_{\vee}$ and $d_{\wedge}$ are at most $\lceil d/2\rceil$. While estimating
the effective resistance of two subtrees, we only care about which of the
subtrees has the smaller effective resistance, so we do not want to wait for
both iterations of Est to terminate. Let $p(d)$ be some polynomial function in
$d$ such that Est$(x)$ always terminates after at most
$p(d)\sqrt{R_{s,t}(G_{\phi}(x))}2^{d/4}$ queries, for all
$x\in\\{0,1\\}^{2^{d}}$. We define a subroutine,
$\texttt{Select}(x^{0},x^{1})$, that takes two instances,
$x^{0},x^{1}\in\\{0,1\\}^{2^{d-1}}$, and outputs a bit $b$ such that
$R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))\leq
2R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{\bar{b}}))$, where $\bar{b}=b\oplus 1$.
Select works as follows. It runs Est$(x^{0})$ and $\texttt{Est}(x^{1})$ in
parallel. If one of these programs, say $\texttt{Est}(x^{b})$, outputs some
estimate $w_{b}$, then it terminates the other program after
$p(d)\sqrt{w_{b}}2^{d/4}$ steps. If only the algorithm running on $x^{b}$ has
terminated after this time, it outputs $b$. If both programs have terminated,
it outputs a bit $b$ such that $w_{b}\leq w_{\bar{b}}$. In Appendix D.3, we
prove the following lemma.

######  Lemma 26.

Let $x^{0},x^{1}\in\\{0,1\\}^{2^{d}}$ be instances of nandd with at least one
of them a 1-instance. Let $N=2^{d}$, and
$w_{\min}=\min\\{R_{s,t}(G_{\textsc{nand}_{d}}(x^{0})),R_{s,t}(G_{\textsc{nand}_{d}}(x^{1}))\\}$.
Then $\mathtt{Select}(x^{0},x^{1})$ terminates after
$\widetilde{O}\left(N^{1/4}\sqrt{w_{\min}}\right)$ queries to $(x^{0},x^{1})$
and outputs $b$ such that
$R_{s,t}(G_{\textsc{nand}_{d}}(x^{b}))\leq{2}R_{s,t}(G_{\textsc{nand}_{d}}(x^{\bar{b}}))$
with bounded error.

Using Lemma 26, we can prove the following (the inductive proof is in Appendix
D.3):

######  Theorem 27.

Let $x\in\\{0,1\\}^{N}$ for $N=2^{d}$ be an $A$-winnable input to
$\textsc{nand}_{d}$. At every node $v$ where Player $A$ makes a decision, let
Player $A$ use the $\mathtt{Select}$ algorithm in the following way. Let
$v_{0}$ and $v_{1}$ be the two children of $v$, with inputs to the respective
subtrees of $v_{0}$ and $v_{1}$ given by $x^{0}$ and $x^{1}$ respectively.
Then Player $A$ moves to $v_{b}$ where $b$ is the outcome that occurs a
majority of times when $\mathtt{Select}(x^{0},x^{1})$ is run $O(\log d)$
times. Then if Player $B$, at his decision nodes, chooses left and right with
equal probability, Player $A$ will win the game with probability at least
$2/3$, and will use
$\widetilde{O}\left(N^{1/4}\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x))}\right)$
queries on average, where the average is taken over the randomness of Player
$B$’s choices.

##  6 Acknowledgments

SK is funded by the US Department of Defense. SJ acknowledges funding provided
by the Institute for Quantum Information and Matter, an NSF Physics Frontiers
Center (NFS Grant PHY-1125565) with support of the Gordon and Betty Moore
Foundation (GBMF-12500028); and an NWO WISE Fellowship.

## References

  * Aaronson and Ben-David [2016] S. Aaronson and S. Ben-David.  Sculpting quantum speedups.  In _Proceedings of the 31st Conference on Computational Complexity_ , CCC ’16, pages 26:1–26:28, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  ISBN 978-3-95977-008-8.  doi: 10.4230/LIPIcs.CCC.2016.26.  URL http://dl.acm.org/citation.cfm?id=2982445.2982471.
  * Aldous and Fill [2002] D. Aldous and J. Fill.  Reversible Markov chains and random walks on graphs, 2002.  Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  * Belovs [2012] A. Belovs.  Span programs for functions with constant-sized 1-certificates.  In _Proceedings of the 44th Symposium on Theory of Computing (STOC 2012)_ , pages 77–84, 2012.  doi: 10.1145/2213977.2213985.
  * Belovs and Reichardt [2012] A. Belovs and B. W. Reichardt.  Span programs and quantum algorithms for $st$-connectivity and claw detection.  In _Proceedings of the 20th European Symposium on Algorithms (ESA 2012)_ , pages 193–204, 2012.  doi: 10.1007/978-3-642-33090-2_18.
  * Ben-David and Kothari [2016] S. Ben-David and R. Kothari.  Randomized query complexity of sabotaged and composed functions.  In _Proceedings of the 43th International Colloquium on Automata, Languages and Programming (ICALP 2016)_ , volume 55, pages 60:1–60:14, 2016.  doi: 10.4230/LIPIcs.ICALP.2016.60.
  * Boyer et al. [1998] M. Boyer, G. Brassard, P. Høyer, and A. Tapp.  Tight bounds on quantum searching.  _Fortschritte der Physik_ , 46(4-5):493–505, 1998\.  ISSN 1521-3978.  doi: 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P.  URL http://dx.doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P.
  * Brassard et al. [2002] G. Brassard, P. Høyer, M. Mosca, and A. Tapp.  Quantum amplitude amplification and estimation.  _Contemporary Mathematics_ , 305:53–74, 2002.
  * Cade et al. [2016] C. Cade, A. Montanaro, and A. Belovs.  Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness, 2016.  arXiv:1610.00581.
  * Chandra et al. [1996] A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari.  The electrical resistance of a graph captures its commute and cover times.  _Computational Complexity_ , 6(4):312–340, 1996\.  doi: 10.1007/BF01270385.
  * Dirac [1952] G. A. Dirac.  A property of 4-chromatic graphs and some remarks on critical graphs.  _Journal of the London Mathematical Society_ , 1(1):85–92, 1952.  doi: 10.1112/jlms/s1-27.1.85.
  * Doyle and Snell [1984] P. G. Doyle and J. L. Snell.  _Random Walks and Electrical Networks_ , volume 22 of _The Carus Mathematical Monographs_.  The Mathematical Association of America, 1984.
  * Duffin [1965] R. J. Duffin.  Topology of series-parallel networks.  _Journal of Mathematical Analysis and Applications_ , 10(2):303–318, 1965.  ISSN 0022-247X.  doi: http://dx.doi.org/10.1016/0022-247X(65)90125-3.  URL http://www.sciencedirect.com/science/article/pii/0022247X65901253.
  * Dürr et al. [2006] C. Dürr, M. Heiligman, P. Høyer, and M. Mhalla.  Quantum query complexity of some graph problems.  _SIAM Journal on Computing_ , 35(6):1310–1328, 2006.  doi: 10.1137/050644719.
  * Farhi et al. [2008] E. Farhi, J. Goldstone, and S. Gutmann.  A quantum algorithm for the Hamiltonian NAND tree.  _Theory of Computing_ , 4(8):169–190, 2008.  doi: 10.4086/toc.2008.v004a008.  arXiv:quant-ph/0702144.
  * Grover [1996] L. K. Grover.  A fast quantum mechanical algorithm for database search.  In _Proceedings of the 28th annual ACM Symposium on Theory of computing (STOC 1996)_ , pages 212–219. ACM, 1996.  doi: 10.1145/237814.237866.
  * Heiman and Wigderson [1991] R. Heiman and A. Wigderson.  Randomized vs. deterministic decision tree complexity for read-once Boolean functions.  _Computational Complexity_ , 1(4):311–329, 1991\.  doi: 10.1007/BF01212962.
  * Ito and Jeffery [2016] T. Ito and S. Jeffery.  Approximate span programs.  In _Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)_ , pages 12:1–12:14, 2016.  doi: 10.4230/LIPIcs.ICALP.2016.12.  arXiv:1507.00432.
  * Karchmer and Wigderson [1993] M. Karchmer and A. Wigderson.  On span programs.  In _Proceedings of the IEEE 8th Annual Conference on Structure in Complexity Theory_ , pages 102–111, 1993.  doi: 10.1109/SCT.1993.336536.
  * Kimmel [2011] S. Kimmel.  Quantum adversary (upper) bound.  _Chicago Journal of Theoretical Computer Science_ , 2013(4), 2011.  doi: 10.4086/cjtcs.2013.004.
  * Lee et al. [2011] T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy.  Quantum query complexity of state conversion.  In _Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011)_ , pages 344–353, 2011.  doi: 10.1109/FOCS.2011.75.
  * Reichardt [2009] B. W. Reichardt.  Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function.  In _Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS 2009)_ , pages 544–551, 2009.  doi: 10.1109/FOCS.2009.55.  arXiv:quant-ph/0904.2759.
  * Reichardt [2010] B. W. Reichardt.  Span programs and quantum query algorithms.  _Electronic Colloquium on Computational Complexity (ECCC)_ , 17:110, 2010.
  * Reichardt [2011] B. W. Reichardt.  Reflections for quantum query algorithms.  In _Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)_ , pages 560–569. SIAM, 2011.
  * Reichardt and Špalek [2012] B. W. Reichardt and R. Špalek.  Span-program-based quantum algorithm for evaluating formulas.  _Theory of Computing_ , 8(13):291–319, 2012.  doi: 10.4086/toc.2012.v008a013.
  * Saks and Wigderson [1986] M. Saks and A. Wigderson.  Probabilistic Boolean decision trees and the complexity of evaluating game trees.  In _Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS 1986)_ , pages 29–38. IEEE, 1986.  doi: 10.1109/SFCS.1986.44.
  * Valdes et al. [1979] J. Valdes, R. E. Tarjan, and E. L. Lawler.  The recognition of series parallel digraphs.  In _Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC 1979)_ , pages 1–12. ACM, 1979.  doi: 10.1145/800135.804393.  URL http://doi.acm.org/10.1145/800135.804393.
  * Zhan et al. [2012] B. Zhan, S. Kimmel, and A. Hassidim.  Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure.  In _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS 2012)_ , pages 249–265, New York, NY, USA, 2012. ACM.  ISBN 978-1-4503-1115-1.  doi: 10.1145/2090236.2090258.  URL http://doi.acm.org/10.1145/2090236.2090258.

##  Appendix A Analysis of the Span Program for st-Connectivity

In this section, we analyze the complexity of our span-program-based
algorithms, proving Lemma 11, first stated in Section 3, which relates witness
sizes of the span program $P_{G,c}$ to the effective resistance of graphs
related to $G$.

We need the concept of a circulation, which is like a flow but with no source
and no sink.

######  Definition 28 (Circulation).

A _circulation_ on a graph $G$ is a function
$\theta:\overrightarrow{E}(G)\rightarrow\mathbb{R}$ such that:

  1. 1.

For all $(u,v,\lambda)\in\overrightarrow{E}(G)$,
$\theta(u,v,\lambda)=-\theta(v,u,\lambda)$;

  2. 2.

for all $u\in V(G)$,
$\sum_{v,\lambda:(u,v\lambda)\in\overrightarrow{E}(G)}\theta(u,v,\lambda)=0$.

The following easily verified observations will be useful in several of the
remaining proofs in this section.

######  Claim 29.

Let $\theta$ be a unit $st$-flow in some multigraph $G$. We can consider the
corresponding vector
$|\theta\rangle=\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\theta(u,v,\lambda)|u,v,\lambda\rangle$.
Then $|\theta\rangle$ can be written as a linear combination of vectors
corresponding to self-avoiding $st$-paths and cycles that are edge-disjoint
from these paths.

Let $\sigma$ be a circulation on $G$. Then $|\sigma\rangle$ can be written as
a linear combination of cycles in $G$. Furthermore, $|\sigma\rangle$ can be
written as a linear combination of cycles such that each cycle goes around a
face of $G$.

The next claim shows a direct correspondence between positive witnesses, and
$st$-flows.

######  Claim 30.

Fix a span program $P_{G,c}$ as in (3). Call $|w\rangle\in H$ a positive
witness in $P_{G,c}$ if $A|w\rangle=\tau$ (note that such a $|w\rangle$ is not
necessarily a positive witness for any particular input $x$). Then if $\theta$
is a unit $st$-flow in $G$,
$\frac{1}{2}\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\frac{\theta(u,v,\lambda)}{\sqrt{c(\\{u,v\\},\lambda)}}|u,v,\lambda\rangle$
is a positive witness in $P_{G,c}$, and furthermore, if $|w\rangle$ is a
positive witness in $P_{G,c}$, then
$\theta(u,v,\lambda)=\sqrt{c(\\{u,v\\},\lambda)}(\langle{w}|{u,v,\lambda}\rangle-\langle{w}|{v,u,\lambda}\rangle)$
is a unit $st$-flow in $G$.

###### Proof.

The proof is a straightforward calculation. Let $\theta$ be a unit $st$-flow
on $G$. Then

$\displaystyle
A\left(\frac{1}{2}\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\frac{\theta(u,v,\lambda)}{\sqrt{c(\\{u,v\\},\lambda)}}|u,v,\lambda\rangle\right)$
(35) $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\theta(u,v,\lambda)(|u\rangle-|v\rangle)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\sum_{u\in
V(G)}\left(\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}\theta(u,v,\lambda)\right)|u\rangle+\frac{1}{2}\sum_{v\in
V(G)}\left(\sum_{u,\lambda:(v,u,\lambda)\in\overrightarrow{E}(G)}\theta(v,u,\lambda)\right)|v\rangle$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left(|s\rangle-|t\rangle\right)+\frac{1}{2}\left(|s\rangle-|t\rangle\right)=\tau.$

Above we have used that $\theta(u,v,\lambda)=-\theta(v,u,\lambda)$, and
$\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}\theta(u,v,\lambda)=0$
when $u\not\in\\{s,t\\}$, 1 when $u=s$, and $-1$ when $u=t$.

To prove the second half of the claim, let $|w\rangle$ be such that
$A|w\rangle=\tau$, and define
$\theta(u,v,\lambda)=\sqrt{c(\\{u,v\\},\lambda)}(\langle{w}|{u,v,\lambda}\rangle-\langle{w}|{v,u,\lambda}\rangle)$.
We immediately see that $\theta(u,v,\lambda)=-\theta(v,u,\lambda)$ for all
$(u,v,\lambda)$. Furthermore, we have:

$\displaystyle|s\rangle-|t\rangle=A|w\rangle$ $\displaystyle=\sum_{u\in
V(G)}\left(\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\sqrt{c(\\{u,v\\},\lambda)}\langle{u,v,\lambda}|{w}\rangle\right)|u\rangle$
$\displaystyle\qquad\qquad-\sum_{v\in
V(G)}\left(\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\sqrt{c(\\{u,v\\},\lambda)}\langle{u,v,\lambda}|{w}\rangle\right)|v\rangle$
$\displaystyle=\sum_{u\in
V(G)}\left(\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\sqrt{c(\\{u,v\\},\lambda)}(\langle{u,v,\lambda}|{w}\rangle-\langle{v,u,\lambda}|{w}\rangle)\right)|u\rangle$
$\displaystyle=\sum_{u\in
V(G)}\left(\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\theta(u,v,\lambda)\right)|u\rangle.$
(36)

Thus, for all $u\in V(G(x))\setminus\\{s,t\\}$,
$\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\theta(u,v,\lambda)=0$, and
$\sum_{(s,v,\lambda)\in\overrightarrow{E}(G)}\theta(s,v,\lambda)=\sum_{(v,t,\lambda)\in\overrightarrow{E}(G)}\theta(v,t,\lambda)=1$.
Thus, $\theta$ is a unit $st$-flow on $G$. ∎

The next claim shows a direct correspondence between negative witnesses, and
$s^{\prime}t^{\prime}$-flows.

######  Claim 31.

For a planar graph $G$, fix a span program $P_{G,c}$ as in (3). Call a linear
function $\omega:V(G)\rightarrow\mathbb{R}$ a negative witness if
$\omega\tau=1$. Then $\theta((u,v,\lambda)^{\dagger})=\omega(u)-\omega(v)$ is
a unit $s^{\prime}t^{\prime}$-flow on $G^{\prime}$, and furthermore, for every
$s^{\prime}t^{\prime}$-flow $\theta$ on $G^{\prime}$ there is a negative
witness $\omega$ such that
$\theta((u,v,\lambda)^{\dagger})=\omega(u)-\omega(v)$ for all
$(u,v,\lambda)\in\overrightarrow{E}(G)$.

###### Proof.

$v^{\prime}$$u^{\prime}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$ Figure 6:
The duality between a cycle and a star.

When we consider the edges of $G$ as directed edges, we assign edge directions
to the dual by orienting each dual edge $\pi/2$ radians counter-clockwise from
the primal edge.

Note that without loss of generality, if $\omega$ is a negative witness, we
can assume $\omega(s)=1$ and $\omega(t)=0$. This is because $\left\|\omega
A\right\|$ and $\left\|\omega A\Pi_{H(x)}\right\|$ are invariant under affine
transformations of $\omega$.

We first show that if $\omega$ is a negative witness in $P_{G,c}$, then
$\theta:\overrightarrow{E}(G^{\prime})\rightarrow\mathbb{R}$ defined
$\theta((u,v,\lambda)^{\dagger})=\omega(u)-\omega(v)$ is a unit
$s^{\prime}t^{\prime}$-flow on $G^{\prime}$. To begin with, we will define
$\theta^{\prime}((u,v,\lambda)^{\dagger})=\omega(u)-\omega(v)$ on
$\overrightarrow{E}(\overline{G}^{\dagger})$, so $\theta^{\prime}$ agrees with
$\theta$ everywhere $\theta$ is defined, and in addition,
$\theta^{\prime}(s^{\prime},t^{\prime},\emptyset)=\theta^{\prime}((s,t,\emptyset)^{\dagger})=\omega(s)-\omega(t)=1$,
and $\theta^{\prime}(t^{\prime},s^{\prime},\emptyset)=-1$. Then clearly we
have
$\theta^{\prime}(u^{\prime},v^{\prime},\lambda)=-\theta^{\prime}(v^{\prime},u^{\prime},\lambda)$
for all $(\\{u^{\prime},v^{\prime}\\},\lambda)\in E(\overline{G}^{\dagger})$.

Next, every $v^{\prime}\in V(\overline{G}^{\dagger})$ corresponds to a face
$f_{v^{\prime}}$ of $\overline{G}$, and the edges coming out of $v^{\prime}$
are dual to edges going clockwise around the face $f_{v^{\prime}}$ (see Figure
6). If $(w_{1},w_{2},\lambda_{1}),\dots,(w_{k},w_{k+1},\lambda_{k})$, for
$w_{k+1}=w_{1}$, are the directed edges going clockwise around
$f_{v^{\prime}}$, then we have:

$\displaystyle
0=\sum_{i=1}^{k}(\omega(w_{i})-\omega(w_{i+1}))=\sum_{i=1}^{k}\theta^{\prime}((w_{i},w_{i+1},\lambda_{i})^{\dagger})=\\!\\!\\!\\!\sum_{\begin{subarray}{c}u^{\prime},\lambda:\\\
(\\{v^{\prime},u^{\prime}\\},\lambda)\in
E(\overline{G}^{\prime})\end{subarray}}\theta^{\prime}(v^{\prime},u^{\prime},\lambda).$
(37)

Thus, $\theta^{\prime}$ is a circulation. Then, since
$\theta^{\prime}(s^{\prime},t^{\prime},\emptyset)=1$, if we remove the flow on
this edge, which recovers $\theta$, we get a unit $s^{\prime}t^{\prime}$-flow
on $G^{\prime}$.

Next we will show that if $\theta$ is a unit $s^{\prime}t^{\prime}$-flow on
$G^{\prime}$, then there exists a negative witness $\omega$ in $P_{G,c}$ such
that for all $(u,v,\lambda)\in\overrightarrow{E}(G)$,
$\theta((u,v,\lambda)^{\dagger})=\omega(u)-\omega(v)$.

Define $\theta^{\prime}$ to be the circulation on $\overline{G}^{\dagger}$
obtained from defining
$\theta^{\prime}(u^{\prime},v^{\prime},\lambda)=\theta(u^{\prime},v^{\prime},\lambda)$
for all $(u^{\prime},v^{\prime},\lambda)\in\overrightarrow{E}(G^{\prime})$,
and
$\theta^{\prime}(s^{\prime},t^{\prime},\emptyset)=-\theta^{\prime}(t^{\prime},s^{\prime},\emptyset)=1$.
Then if we define
$|\theta^{\prime}\rangle=\sum_{(u,v,\lambda)\in\overrightarrow{E}(\overline{G}^{\dagger})}\theta^{\prime}(u,v,\lambda)|u,v,\lambda\rangle$,
we can express $|\theta^{\prime}\rangle$ as a linear combination of cycles
around the faces of $\overline{G}^{\dagger}$,
$|\theta^{\prime}\rangle=\sum_{f\in
F(\overline{G}^{\dagger})}\alpha_{f}|\overrightarrow{C}_{f}\rangle+\sum_{f\in
F(\overline{G}^{\dagger})}\alpha_{f}^{\prime}|\overleftarrow{C}_{f}\rangle$,
where if $w_{k+1}=w_{1}$ and
$(w_{1},w_{2},\lambda_{1}),\dots,(w_{k},w_{k+1},\lambda_{k})$ is a clockwise
cycle around $f$,
$|\overrightarrow{C}_{f}\rangle=\sum_{i=1}^{k}|w_{i},w_{i+1},\lambda_{i}\rangle$
is the clockwise cycle around the face $f$, and
$|\overleftarrow{C}_{f}\rangle=\sum_{i=1}^{k}|w_{i+1},w_{i},\lambda_{i}\rangle$
is the counter-clockwise cycle around $f$. There is a one-to-one
correspondance between vertices in $V(\overline{G})=V(G)$ and faces in
$F(\overline{G}^{\dagger})$, so we can define
$\omega:V({G})\rightarrow\mathbb{R}$ by
$\omega(v_{f})=\frac{1}{2}(\alpha_{f}-\alpha_{f}^{\prime})$.

We claim that for all $(u,v,\lambda)\in\overrightarrow{E}(\overline{G})$,
$\omega(u)-\omega(v)=\theta^{\prime}((u,v,\lambda)^{\dagger})$. Let
$(u^{\prime},v^{\prime},\lambda)$ be any edge in
$\overrightarrow{E}(\overline{G}^{\dagger})$. This edge is part of a clockwise
cycle around one face in $\overline{G}^{\dagger}$, call it $f$, and a counter
clockwise cycle around one face in $\overline{G}^{\dagger}$, call it $g$.
Since these are the only two faces containing the edge
$(u^{\prime},v^{\prime},\lambda)$, we must have
$\theta^{\prime}(u^{\prime},v^{\prime},\lambda)=\langle{u^{\prime},v^{\prime},\lambda}|{\theta^{\prime}}\rangle=\alpha_{f}+\alpha_{g}^{\prime}$.
Since
$\theta^{\prime}(u^{\prime},v^{\prime},\lambda)=-\theta^{\prime}(v^{\prime},u^{\prime},\lambda)$,
we have $\alpha_{f}+\alpha_{g}^{\prime}=-\alpha_{f}^{\prime}-\alpha_{g}$.
Thus:

$\displaystyle\omega(v_{f})-\omega(v_{g})=\frac{1}{2}\left(\alpha_{f}-\alpha_{f}^{\prime}-\alpha_{g}+\alpha_{g}^{\prime}\right)=\frac{1}{2}\left(\theta^{\prime}(u^{\prime},v^{\prime},\lambda)-\theta^{\prime}(v^{\prime},u^{\prime},\lambda)\right)=\theta^{\prime}((v_{f},v_{g},0pt)^{\dagger}).$
(38)

In particular, this means that
$\omega(s)-\omega(t)=\theta^{\prime}((s,t,\emptyset)^{\dagger})=\theta^{\prime}(s^{\prime},t^{\prime},\emptyset)=1$,
so $\omega$ is a negative witness, and for all
$(u,v,\lambda)\in\overrightarrow{E}(G)$,
$\omega(u)-\omega(v)=\theta((u,v,\lambda)^{\dagger})$. ∎

Now we can prove the main result of this section, Lemma 11: See 11

###### Proof.

If $x$ is a 1-instance, $s$ and $t$ are connected in $G(x)$, so there exists a
unit $st$-flow on $G(x)$, which is a unit $st$-flow on $G$ that is supported
only on $\overrightarrow{E}(G(x))$. Let $\theta$ be the flow on $G(x)$ such
that $R_{s,t}(G(x),c)=\sum_{(\\{u,v\\},\lambda)\in
E(G(x))}\frac{\theta(u,v,\lambda)^{2}}{c(\\{u,v\\},\lambda)}$. By Claim 30,
$|w\rangle=\frac{1}{2}\sum_{(u,v,\lambda)}\frac{\theta(u,v,\lambda)}{\sqrt{c(\\{u,v\\},\lambda)}}|u,v,\lambda\rangle$
is a positive witness in $P_{G,c}$, and since $\theta$ is supported on
$\overrightarrow{E}(G(x))$, $|w\rangle\in H(x)$, and so $|w\rangle$ is a
positive witness for $x$ in $P_{G,c}$. Thus

$\displaystyle
w_{+}(x,P_{G,c})\leq\left\||w\rangle\right\|^{2}=\frac{1}{4}\sum_{(u,v,\lambda)\in\overrightarrow{E}(G(x))}c(\\{u,v\\},\lambda)\theta(u,v,\lambda)^{2}=\frac{1}{2}R_{s,t}(G(x),c).$
(39)

On the other hand, let $|w\rangle$ be an optimal positive witness for $x$. By
Claim 30,
$\theta(u,v,\lambda)=\sqrt{c(\\{u,v\\},\lambda)}(\langle{u,v,\lambda}|{w}\rangle-\langle{v,u,\lambda}|{w}\rangle)$
is a unit $st$-flow on $G$, and since $|w\rangle\in H(x)$,
$\theta(u,v,\lambda)$ is only non-zero on $\overrightarrow{E}(G(x))$, so
$\theta$ is a unit $st$-flow on $G(x)$. Thus,

$\displaystyle R_{s,t}(G(x),c)$ $\displaystyle\leq$
$\displaystyle\sum_{(\\{u,v\\},\lambda)\in
E(G(x))}\frac{\theta(u,v,\lambda)^{2}}{c(\\{u,v\\},\lambda)}=\frac{1}{2}\sum_{(u,v,\lambda)\in\overrightarrow{E}(G(x))}\left(\langle{u,v,\lambda}|{w}\rangle-\langle{v,u,\lambda}|{w}\rangle\right)^{2}$
(40) $\displaystyle=$
$\displaystyle\\!\\!\sum_{(u,v,\lambda)\in\overrightarrow{E}(G(x))}\\!\\!\langle{u,v,\lambda}|{w}\rangle^{2}-\\!\\!\\!\\!\sum_{(u,v,\lambda)\in\overrightarrow{E}(G(x))}\\!\\!\\!\\!\langle{u,v,\lambda}|{w}\rangle\langle{v,u,\lambda}|{w}\rangle\leq
2\left\||w\rangle\right\|^{2}$

where the last inequality is by Cauchy-Schwarz. Thus,
$w_{+}(x,P_{G,c})=\frac{1}{2}R_{s,t}(G(x))$.

Now we prove that
$w_{-}(x,P_{G,c})=2R_{s^{\prime},t^{\prime}}(G^{\prime}(x),c^{\prime})$. Let
$x\in\\{0,1\\}^{E(G)}$ be such that $s$ and $t$ are not connected in $G(x)$.
Fix an optimal negative witness $\omega$ for $x$. By Claim 31 the linear
function $\theta:\overrightarrow{E}(G^{\prime})\rightarrow\mathbb{R}$ defined
by $\theta((u,v,\lambda)^{\dagger})=\omega(u)-\omega(v)$ is a unit
$s^{\prime}t^{\prime}$ -flow on $G^{\prime}$. Since $\omega$ is a negative
witness for $x$, we also have:

$\displaystyle 0=\left\|\omega A\Pi_{H(x)}\right\|^{2}$
$\displaystyle=\sum_{{(u,v,\lambda)\in\overrightarrow{E}(G(x))}}c(\\{u,v\\},\lambda)(\omega(u)-\omega(v))^{2}$
$\displaystyle=\sum_{{(u,v,\lambda)\in\overrightarrow{E}(G(x))}}c(\\{u,v\\},\lambda)\theta((u,v,\lambda)^{\dagger})^{2}$
$\displaystyle=\sum_{{(u^{\prime},v^{\prime},\lambda)\in\overrightarrow{E}(G^{\prime})\setminus\overrightarrow{E}(G^{\prime}(x))}}\frac{\theta(u^{\prime},v^{\prime},\lambda)^{2}}{c^{\prime}(\\{u^{\prime},v^{\prime}\\},\lambda)},$
(41)

since $(u,v,\lambda)\in\overrightarrow{E}(G(x))$ exactly when
$(u,v,\lambda)^{\dagger}\not\in\overrightarrow{E}(G^{\prime}(x))$. So $\theta$
is only supported on $\overrightarrow{E}(G^{\prime}(x))$, and so it is a unit
$s^{\prime}t^{\prime}$-flow on $G^{\prime}(x)$. Thus

$\displaystyle w_{-}(x,P_{G,c})=\left\|\omega A\right\|^{2}$
$\displaystyle=\sum_{{(u,v,\lambda)\in\overrightarrow{E}(G)}}c(\\{u,v\\},\lambda)(\omega(u)-\omega(v))^{2}$
$\displaystyle=\sum_{{(u^{\prime},v^{\prime},\lambda)\in\overrightarrow{E}(G^{\prime}(x))}}\frac{\theta(u^{\prime},v^{\prime},\lambda)^{2}}{c^{\prime}(\\{u^{\prime},v^{\prime}\\},\lambda)}\geq
2R_{s^{\prime},t^{\prime}}(G^{\prime}(x),c^{\prime}).$ (42)

For the other direction, let $\theta$ be an $s^{\prime}t^{\prime}$-flow in
$G^{\prime}(x)$ with minimal energy. By Claim 31, there is a negative witness
$\omega$ such that $\theta((u,v,\lambda)^{\dagger})=\omega(u)-\omega(v)$.
Since $\theta$ is supported on edges
$(u^{\prime},v^{\prime},\lambda)\in\overrightarrow{E}(G^{\prime}(x))$, which
are exactly those edges such that
$(u^{\prime},v^{\prime},\lambda)^{\dagger}\not\in\overrightarrow{E}(G(x))$, we
have

$\displaystyle 0$ $\displaystyle=\sum_{\begin{subarray}{c}(u,v,\lambda)\\\
\in\overrightarrow{E}(G(x))\end{subarray}}c(\\{u,v\\},\lambda)\theta((u,v,\lambda)^{\dagger})^{2}=\sum_{\begin{subarray}{c}(u,v,\lambda)\\\
\in\overrightarrow{E}(G(x))\end{subarray}}c(\\{u,v\\},\lambda)(\omega(u)-\omega(v))^{2}=\left\|\omega
A\Pi_{H(x)}\right\|^{2},$ (43)

so $\omega$ is a negative witness for $x$ in $P_{G,c}$. Thus:

$\displaystyle w_{-}(x,P_{G,c})\leq\left\|\omega A\right\|^{2}$
$\displaystyle=\sum_{\begin{subarray}{c}(u,v,\lambda)\in\overrightarrow{E}(G)\end{subarray}}c(\\{u,v\\},\lambda)(\omega(u)-\omega(v))^{2}$
$\displaystyle=\sum_{\begin{subarray}{c}(u^{\prime},v^{\prime},\lambda)\in\overrightarrow{E}(G^{\prime}(x))\end{subarray}}\frac{\theta(u^{\prime},v^{\prime},\lambda)^{2}}{c^{\prime}(\\{u^{\prime},v^{\prime}\\},\lambda)}=2R_{s^{\prime},t^{\prime}}(G^{\prime}(x),c^{\prime}),$
(44)

completing the proof. ∎

###  A.1 Time and Space Analysis of the Span Program Algorithm for st-
Connectivity

In this section, we will give an upper bound on the time complexity of
$st$-connG in terms of the time complexity of implementing a step of a
discrete-time quantum walk on $G$. The analysis follows relatively
straightforwardly from [4, Section 5.3], but we include it here for
completeness. At the end of this section, we show the space complexity of the
algorithm is $O(\max\\{\log|E(G)|,\log|V(G)|\\})$.

We first describe the algorithm that can be derived from a span program,
following the conventions of [17]. Throughout this section, we will let
$\Pi_{S}$ denote the orthogonal projector onto an inner product space $S$. For
a span program $P=(H,U,A,\tau)$, the corresponding algorithm performs phase
estimation on the unitary $(2\Pi_{H(x)}-I)(2\Pi_{\ker A}-I)$ applied to
initial state $|w_{0}\rangle=A^{+}\tau$, where $\Pi_{H(x)}$ denotes the
orthogonal projector onto $H(x)$, and $\Pi_{\ker A}$ denotes the orthogonal
projector onto the kernel of $A$, and $A^{+}$ denotes the pseudo-inverse of
$A$. To decide a function $f$ on domain $D$, it is sufficient to perform phase
estimation to precision $O\left(\sqrt{\max_{x\in
D:f(x)=1}w_{+}(x)\times\max_{x\in D:f(x)=0}w_{-}(x)}\right)$.

In case of the $st$-connectivity span program $P_{G,c}$ in (3), it is a simple
exercise to see that $2\Pi_{H(x)}-I$ can be implemented in $O(1)$ quantum
operations, including 2 queries to $x$. The reflection $2\Pi_{\ker A}-I$ is
independent of $x$, and so requires 0 queries to implement, however, it could
still require a number of gates that grows quickly with the size of $G$. We
will show that implementing $2\Pi_{\ker A}-I$ can be reduced to implementing a
discrete-time quantum walk on $G$, a task which could be quite easy, depending
on the structure of $G$ (for example, in the case that $G$ is a complete graph
on $n$ vertices, this can be done in $O(\log n)$ gates [4]).

For a multigraph $G$ and weight function $c$, we define a _quantum walk step
on $G$_ to be a unitary $U_{G,c}$ that acts as follows for any $u\in V(G)$:

$\displaystyle
U_{G,c}:|u\rangle|0\rangle\mapsto\frac{1}{\sqrt{\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}c(\\{u,v\\},\lambda)}}\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}\sqrt{c(\\{u,v\\},\lambda)}|u\rangle|u,v,\lambda\rangle.$
(45)

See 13 This theorem follows from Lemma 32, stated below, and Lemma 33, which
deals with the construction of the algorithm’s initial state.

######  Lemma 32.

Let $A$ be defined as in (3). Let $S_{G,c}$ be an upper bound on the time
complexity of implementing $U_{G,c}$. Then $2\Pi_{\ker A}-I$ can be
implemented in time complexity $O(S_{G,c})$.

###### Proof.

This analysis follows [4] (see also [17]). Let

$\displaystyle
d(u)=\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}c(\\{u,v\\},\lambda).$
(46)

Define spaces $Z$ and $Y$ as follows.

$Z=\mathrm{span}\left\\{|z_{u}\rangle:=\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}\frac{\sqrt{c(\\{u,v\\},\lambda)}}{\sqrt{2d(u)}}\left(|0,u,u,v,\lambda\rangle+|1,u,v,u,\lambda\rangle\right):u\in
V(G)\right\\}$ (47)

$Y=\mathrm{span}\left\\{|y_{u,v,\lambda}\rangle:=\frac{|0,u,u,v,\lambda\rangle-|1,v,u,v,\lambda\rangle}{\sqrt{2}}:(u,v,\lambda)\in\overrightarrow{E}(G)\right\\}$
(48)

Define isometries whose column-spaces are $Z$ and $Y$ respectively:

$\displaystyle M_{Z}=\sum_{u\in V(G)}|z_{u}\rangle\langle
u|\quad\mbox{and}\quad
M_{Y}=\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}|y_{u,v,\lambda}\rangle\langle
u,v,\lambda|.$ (49)

Now we note that for any $(\\{u,v\\},\lambda)\in E(G)$, we have the following:

$\langle{z_{u}}|{y_{u,v,\lambda}}\rangle=\frac{\sqrt{c(\\{u,v\\},\lambda)}}{2\sqrt{d(u)}},\quad\mbox{and}\quad\langle{z_{v}}|{y_{u,v,\lambda}}\rangle=-\frac{\sqrt{c(\\{u,v\\},\lambda)}}{2\sqrt{d(v)}}.$
(50)

Thus, we can calculate:

$\displaystyle M_{Z}^{\dagger}M_{Y}$ $\displaystyle=$
$\displaystyle\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\left(\frac{|u\rangle}{2\sqrt{d(u)}}-\frac{|v\rangle}{2\sqrt{d(v)}}\right)\sqrt{c(\\{u,v\\},\lambda)}\langle
u,v,\lambda|$ (51) $\displaystyle=$ $\displaystyle\sum_{u^{\prime}\in
V(G)}\frac{|{u^{\prime}}\rangle\\!\langle{u^{\prime}}|}{2\sqrt{d(u^{\prime})}}\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\sqrt{c(\\{u,v\\},\lambda)}(|u\rangle-|v\rangle)\langle
u,v,\lambda|$ $\displaystyle=$ $\displaystyle\sum_{u^{\prime}\in
V(G)}\frac{|{u^{\prime}}\rangle\\!\langle{u^{\prime}}|}{2\sqrt{d(u^{\prime})}}A.$

Note that the rows of $M_{Z}^{\dagger}M_{Y}$ are non-zero multiples of the
rows of $A$, so $\mathrm{row}(M_{Z}^{\dagger}M_{Y})=\mathrm{row}(A)$, and thus
$\ker(M_{Z}^{\dagger}M_{Y})=\ker A$.

Define $W=(2\Pi_{Z}-I)(2\Pi_{Y}-I)$. We now claim that $M_{Y}$ maps $\ker A$
to the $(-1)$-eigenspace of $W$, and $(\ker A)^{\bot}$ to the 1-eigenspace of
$W$, so that $2\Pi_{\ker A}-I=M_{Y}^{\dagger}WM_{Y}$. To see this, note that
if $|\psi\rangle\in\ker A$, then $|\psi\rangle\in\ker(M_{Z}^{\dagger}M_{Y})$
so $M_{Y}|\psi\rangle\in\ker M_{Z}^{\dagger}=Z^{\bot}$. Thus
$M_{Y}|\psi\rangle\in Y\cap Z^{\bot}$, which is in the $(-1)$-eigenspace of
$W$.

Next, suppose $|\psi\rangle\in(\ker
A)^{\bot}=(\ker(M_{Z}^{\dagger}M_{Y}))^{\bot}$, so since $M_{Y}$ is an
isometry, $M_{Y}|\psi\rangle\in(\ker M_{Z})^{\bot}=\mathrm{row}M_{Z}=Z$. Thus
$M_{Y}|\psi\rangle\in Y\cap Z$, which is in the 1-eigenspace of $W$.

Thus, we can implement $2\Pi_{\ker A}-I$ by $M_{Y}^{\dagger}WM_{Y}$. It only
remains to argue that each of $M_{Y}$, $2\Pi_{Z}-I$ and $2\Pi_{Y}-I$ can be
implemented in time complexity at most $O(S_{G,c})$.

We first show that we can implement the isometry $M_{Y}$, or rather a unitary
$U_{Y}$ that acts as $|0\rangle|0\rangle|u,v,\lambda\rangle\mapsto
M_{Y}|u,v,\lambda\rangle=|y_{u,v,\lambda}\rangle$. First, use $HX$ on the
first qubit to perform the map:

$\displaystyle|0\rangle|0\rangle|u,v,\lambda\rangle\mapsto|-\rangle|0\rangle|u,v,\lambda\rangle.$
(52)

Conditioned on the value of the first register, copy either $u$ or $v$ into
the second register to get:

$\displaystyle\frac{1}{\sqrt{2}}(|0,u,u,v,\lambda\rangle-|1,v,u,v,\lambda\rangle)=|y_{u,v,\lambda}\rangle.$
(53)

Thus, we can implement $U_{Y}$ in the time it takes to write down a vertex of
$G$, $O(\log|V(G)|)$, which is at most $O(S_{G,c})$. Using the ability to
implement $U_{Y}$, we can implement $2\Pi_{Y}-I$ as
$U_{Y}R_{Y}U_{Y}^{\dagger}$, where $R_{Y}$ is the reflection that acts as the
identity on computational basis states of the form
$|0\rangle|0\rangle|u,v,\lambda\rangle$, and reflects computational basis
states without this form.

Next, we implement a unitary $U_{Z}$ that acts as
$|0\rangle|u\rangle|0\rangle\mapsto M_{Z}|u\rangle=|z_{u}\rangle$. First, use
the quantum walk step $U_{G,c}$, which can be implemented in time $S_{G,c}$,
to perform:

$\displaystyle|+\rangle|u\rangle|0\rangle\mapsto\frac{1}{2\sqrt{d(u)}}\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}\sqrt{c(\\{u,v\\},\lambda)}(|0\rangle+|1\rangle)|u\rangle|u,v,\lambda\rangle.$
(54)

Conditioned on the bit in the first register, swap the third and fourth
registers, to get:

$\displaystyle\frac{1}{2\sqrt{d(u)}}\sum_{v,\lambda:(u,v,\lambda)\in\overrightarrow{E}(G)}\sqrt{c(\\{u,v\\},\lambda)}(|0\rangle|u\rangle|u,v,\lambda\rangle+|1\rangle|u\rangle|v,u,\lambda\rangle)=|z_{u}\rangle.$
(55)

The total cost of implementing $U_{Z}$ is $O(S_{G,c}+\log|V(G)|)=O(S_{G,c})$.
Thus, we can implement $2\Pi_{Z}-I$ in $O(S_{G,c})$ quantum gates. ∎

######  Lemma 33.

Let $A$ and $\tau$ be defined as in (3). Let $S_{G,c}$ be an upper bound on
the complexity of implementing $U_{G,c}$. Then the initial state of the
algorithm, $\frac{|w_{0}\rangle}{\left\||w_{0}\rangle\right\|}$ where
$|w_{0}\rangle=A^{+}\tau$, can be approximated in time $O(S_{G,c})$.

###### Proof.

Without loss of generality, we can assume that $G$ includes the edge
$(\\{s,t\\},\emptyset)$ (we can simply not include it in any subgraph).
Furthermore, we set $c(\\{s,t\\},\emptyset)=1/r$, for some positive $r$ to be
specified later, so that $A|s,t,\emptyset\rangle=r^{-1/2}\tau$. This has no
effect on other edges in $G$. Note that

$\displaystyle\Pi_{(\ker
A)^{\bot}}|s,t,\emptyset\rangle=A^{+}A|s,t,\emptyset\rangle=r^{-1/2}A^{+}\tau=r^{-1/2}|w_{0}\rangle,$
(56)

so

$\displaystyle|s,t,\emptyset\rangle=r^{-1/2}|w_{0}\rangle+|w_{0}^{\bot}\rangle$
(57)

for some $|w_{0}^{\bot}\rangle\in\ker A$. Thus, constant precision phase
estimation on $2\Pi_{\ker A}-I$ maps $|s,t,\emptyset\rangle$ to

$\displaystyle r^{-1/2}|0\rangle|w_{0}\rangle+|1\rangle|w_{0}^{\bot}\rangle.$
(58)

Using quantum amplitude amplification [7], we can amplify the amplitude on the
$|0\rangle|w_{0}\rangle$ part of this arbitrarily close to 1 using a number of
calls to $2\Pi_{\ker A}-I$ proportional to
$\left\|r^{-1/2}|w_{0}\rangle\right\|^{-1}$.

In fact, it is straightforward to show that for any
$|\mu\rangle\in\textrm{row}A$, the vector $|\nu\rangle$ with smallest norm
that satisfies $A|\nu\rangle=|\mu\rangle$, is $A^{+}|\mu\rangle$ [17]. Using
this fact along with Claim 30 and Definition 9, we have
$\left\||w_{0}\rangle\right\|^{2}=R_{s,t}(G,c)$.

Let $R=R_{s,t}(G\setminus\\{(\\{s,t\\},\emptyset)\\},c)$ be the effective
resistance of $G$ without the edge $(s,t,\emptyset)$. Now we can think of
$(\\{s,t\\},\emptyset)$ and $G\setminus\\{(\\{s,t\\},\emptyset)\\}$ as two
graphs in parallel, so using Claim 5, we have

$\displaystyle\||w_{0}\rangle\|^{2}=\frac{1}{1/R+1/r}.$ (59)

Setting $r=R$, we have $\||w_{0}\rangle\|^{2}=R/2$ and
$\|r^{-1/2}|w_{0}\rangle\|^{-1}=O(1)$. Thus, using $O(1)$ calls to $2\Pi_{\ker
A}-I$, we can approximate the initial state $|w_{0}\rangle$. ∎

Finally, we note that the space required by the algorithm, in addition to
whatever auxiliary space we need to implement $U_{G,c}$, is
$O(\max\\{\log|E(G)|,\log|V(G)|\\})$. $U_{Y}$ and $U_{G,c}$ each act on a
Hilbert space of dimension less than $4|V(G)|^{2}|E(G)|$, so can in principle
be implemented on $O(\max\\{\log|E(G)|,\log|V(G)|\\})$ qubits, however, a
time-efficient implementation of $U_{G,c}$ may also make use of some number
$S_{G,c}^{\prime}$ of auxiliary qubits. We use these unitaries to perform
phase estimation on $(2\Pi_{H(x)}-I)(2\Pi_{\ker A}-I)$ to precision

$\displaystyle O\left(\min_{c}\sqrt{\max_{x\in
D:\phi(x)=1}R_{s,t}(G_{\phi}(x),c)\times\max_{x\in
D:\phi(x)=0}R_{s^{\prime},t^{\prime}}(G_{\phi}^{\prime}(x),c^{\prime})}\right)=O(|E(G)|).$
(60)

Thus we need $O(\log(|E(G)|)$ qubits to store the output of the phase
estimation. Putting everything together gives the claimed space complexity.

##  Appendix B Formula Evaluation and st-Connectivity

In this section, we prove the correspondence between evaluating the formula
$\phi$, and solving $st$-connectivity on the graph $G_{\phi}$. We first give a
formal definition of $G_{\phi}$.

######  Definition 34 ($G_{\phi}$).

If $\phi=x_{i}$ is a single-variable formula, then $V(G_{\phi})=\\{s,t\\}$ and
$E(G_{\phi})=\\{(\\{s,t\\},x_{i})\\}$.

If $\phi=\phi_{1}\wedge\dots\wedge\phi_{l}$, then define
$V(G_{\phi})=\\{(i,v):i\in[l],v\in
V(G_{\phi_{i}})\setminus\\{s,t\\}\\}\cup\\{s,s_{2},\dots,s_{l},t\\}$ and,
letting $s_{1}=s$ and $s_{l+1}=t$, define:

$\displaystyle E(G_{\phi})=$
$\displaystyle\left\\{\left(\\{(i,u),(i,v)\\},x_{j}\right):i\in[l],u,v\in
V(G_{\phi_{i}})\setminus\\{s,t\\},(\\{u,v\\},x_{j})\in
E(G_{\phi_{i}})\right\\}$
$\displaystyle\cup\\{(\\{(i,u),s_{i}\\},x_{j}):i\in[l],u\in
V(G_{\phi_{i}}),(\\{s,u\\},x_{j})\in E(G_{\phi_{i}})\\}$
$\displaystyle\cup\\{(\\{(i,u),s_{i+1}\\},x_{j}):i\in[l],u\in
V(G_{\phi_{i}}),(\\{t,u\\},x_{j})\in E(G_{\phi_{i}})\\}.$ (61)

If $\phi=\phi_{1}\vee\dots\vee\phi_{l}$ define
$V(G_{\phi})=\\{(i,v):i\in[l],v\in
V(G_{\phi_{i}})\setminus\\{s,t\\}\\}\cup\\{s,t\\}$ and

$\displaystyle E(G_{\phi})=$
$\displaystyle\\{(\\{(i,u),(i,v)\\},x_{j}):i\in[l],u,v\in
V(G_{\phi_{i}})\setminus\\{s,t\\},(\\{u,v\\},x_{j})\in E(G_{\phi_{i}})\\}$
(62) $\displaystyle\cup\\{(\\{(i,u),s\\},x_{j}):i\in[l],u\in
V(G_{\phi_{i}}),(\\{u,s\\},x_{j})\in E(G_{\phi_{i}})\\}$
$\displaystyle\cup\\{(\\{(i,u),t\\},x_{j}):i\in[l],u\in
V(G_{\phi_{i}}),(\\{u,t\\},x_{j})\in E(G_{\phi_{i}})\\}.$

In order to prove Lemma 14, we will first prove Lemma 35:

######  Lemma 35.

For an and-or formula $\phi$ on $\\{0,1\\}^{N}$, define $\phi^{\prime}$ to be
the formula obtained by replacing $\vee$-nodes with $\wedge$-nodes and
$\wedge$-nodes with $\vee$-nodes in $\phi$. Then for all $x\in\\{0,1\\}^{N}$,
if $\bar{x}$ denotes the bitwise complement of $x$, then
$\phi^{\prime}(x)=\neg\phi(\bar{x})$. Furthermore up to an isomorphism that
maps $s$ to $s^{\prime}$, $t$ to $t^{\prime}$, and an edge labeled by any
label $\lambda$ to an edge labeled by $\lambda$, we have
$G_{\phi}^{\prime}=G_{\phi^{\prime}}$ and
$G_{\phi}^{\prime}(x)=G_{\phi^{\prime}}(\bar{x})$.

###### Proof.

The first part of the proof is by induction. Suppose $\phi$ has depth $0$, so
$\phi=x_{i}$ for some variable $x_{i}$. Then
$\phi^{\prime}(x)=\phi(x)=\neg(\phi(\bar{x}))$. So suppose
$\phi=\phi_{1}\wedge\dots\wedge\phi_{l}$. Then
$\phi^{\prime}=\phi_{1}^{\prime}\vee\dots\vee\phi_{l}^{\prime}$. Then by the
induction hypothesis,

$\displaystyle\phi^{\prime}(x)=\phi^{\prime}_{1}(x)\vee\dots\vee\phi_{l}^{\prime}(x)=(\neg\phi_{1}(\bar{x}))\vee\dots\vee(\neg\phi_{l}(\bar{x}))=\neg(\phi_{1}(\bar{x})\wedge\dots\wedge\phi_{l}(\bar{x}))=\neg\phi(\bar{x})$
(63)

where the second to last equality is de Morgan’s law. The case
$\phi=\phi_{1}\vee\dots\vee\phi_{l}$ is similar.

$\vdots$$t$$s$$s^{\prime}$$t^{\prime}$$G_{\phi_{1}}$$G_{\phi_{2}}$$G_{\phi_{l}}$$G^{\prime}_{\phi_{1}}$$G^{\prime}_{\phi_{2}}$$G^{\prime}_{\phi_{l}}$$\vdots$
Figure 7: $\overline{G}_{\phi}$ shown in black, and its dual,
$\overline{G}_{\phi^{\prime}}$, shown in grey. The thick lines represent
graphs. Edges in $G_{\phi_{i}}$ are dual to edges in $G^{\prime}_{\phi_{i}}$,
and the dotted edge $(\\{s,t\\},\emptyset)$ is dual to
$(\\{s^{\prime},t^{\prime}\\},\emptyset)$.

We will now prove that
$\overline{G}_{\phi}^{\dagger}=\overline{G}_{\phi^{\prime}}$, and furthermore,
dual edges have the same label, by induction on the depth of $\phi$, from
which the result follows immediately.

If $\phi=x_{i}$ is a depth-0 formula, then $\phi^{\prime}=x_{i}$. In that
case, $G_{\phi}$ is just an edge from $s$ to $t$, labeled by $x_{i}$, and
$G_{\phi}^{\prime}$ is just an edge from $s^{\prime}$ to $t^{\prime}$ labeled
$x_{i}$, so $G^{\prime}_{\phi}=G_{\phi^{\prime}}$.

For the inductive step, to show that $\overline{G}_{\phi}$ and
$\overline{G}_{\phi^{\prime}}$ are dual, and therefore
$G_{\phi}^{\prime}=G_{\phi^{\prime}}.$ It suffices to exhibit a bijection
$\zeta:V(\overline{G}_{\phi^{\prime}})\rightarrow F(\overline{G}_{\phi})$ such
that $(\\{u,v\\},x_{j})\in E(\overline{G}_{\phi^{\prime}})$ if and only if the
faces $\zeta(u)$ and $\zeta(v)$ are separated by an edge in
$E(\overline{G}_{\phi})$ with the label $x_{j}$. We first consider the case
that $\phi=\phi_{1}\wedge\dots\wedge\phi_{l}$, so
$\phi^{\prime}=\phi_{1}^{\prime}\vee\dots\vee\phi_{l}^{\prime}$. Then,
$\overline{G}_{\phi}$ consists of the graphs
$G_{\phi_{1}},\dots,G_{\phi_{l}}$, chained together in series as in Figure 7,
with an additional edge from $s$ to $t$, so the faces of $\overline{G}_{\phi}$
are exactly all the interior faces of each $G_{\phi_{i}}$, as well as the two
faces on either side of the $st$-edge $(\\{s,t\\},\emptyset)$, which we will
denote by $f^{s^{\prime}}$ and $f^{t^{\prime}}$. That is, adding an $i$ to the
label of each internal face of $G_{\phi_{i}}$:

$\displaystyle F(\overline{G}_{\phi})=\\{(i,f):i\in[l],f\in
F(\overline{G}_{\phi_{i}})\setminus\\{f^{s^{\prime}},f^{t^{\prime}}\\}\\}\cup\\{f^{s^{\prime}},f^{t^{\prime}}\\},$
(64)

since
$F(\overline{G}_{\phi_{i}})\setminus\\{f^{s^{\prime}},f^{t^{\prime}}\\}=F(G_{\phi_{i}})\setminus\\{f^{E}\\}$,
where $f^{E}$ is the external face. Since
$\phi^{\prime}=\phi_{1}^{\prime}\vee\dots\vee\phi_{l}^{\prime}$ we also have

$\displaystyle
V(\overline{G}_{\phi^{\prime}})=V(G_{\phi^{\prime}})=\\{(i,v):i\in[l],v\in
V(G_{\phi_{i}^{\prime}})\setminus\\{s,t\\}\\}\cup\\{s^{\prime},t^{\prime}\\},$
(65)

where we will use the labels $s^{\prime}$ and $t^{\prime}$ in anticipation of
the isometry between $G_{\phi}^{\prime}$ and $G_{\phi^{\prime}}.$

By the induction hypothesis, for each $i\in[l]$, there exists a bijection
$\zeta_{i}:V(\overline{G}_{\phi_{i}^{\prime}})\rightarrow
F(\overline{G}_{\phi_{i}})$ such that for all $u,v\in
V(\overline{G}_{\phi_{i}^{\prime}})=V(G_{\phi_{i}^{\prime}})$,
$(\\{u,v\\},x_{j})\in E(\overline{G}_{\phi_{i}^{\prime}})$ if and only if
$\zeta_{i}(u)$ and $\zeta_{i}(v)$ are faces separated by an edge with the
label $x_{j}$. We define $\zeta$ by $\zeta(i,v)=(i,\zeta_{i}(v))$ for all
$i\in[l]$ and $v\in V(G_{\phi_{i}^{\prime}})\setminus\\{s,t\\}$,
$\zeta(s^{\prime})=f^{s^{\prime}}$, and $\zeta(t^{\prime})=f^{t^{\prime}}$. By
the induction hypothesis, we can see that for any edge $(\\{u,v\\},x_{j})\in
E(\overline{G}_{\phi^{\prime}})\setminus(\\{s^{\prime},t^{\prime}\\},\emptyset)$,
$\zeta(u)$ and $\zeta(v)$ are separated by an edge labeled $x_{j}$. This is
because this edge is in one of the $G_{\phi_{i}^{\prime}}$, and so it has a
dual edge in $G_{\phi_{i}}$, by the induction hypothesis (see Figure 7). The
only other edge in $\overline{G}_{\phi^{\prime}}$ is the edge
$(\\{s^{\prime},t^{\prime}\\},\emptyset)$, and $\zeta(s^{\prime})$ and
$\zeta(t^{\prime})$ are exactly those faces on either side of
$(\\{s,t\\},\emptyset)$ in $\overline{G}_{\phi}$, completing the proof that
$\overline{G}_{\phi}^{\dagger}=\overline{G}_{\phi^{\prime}}$.

If $\phi=\phi_{1}\vee\dots\vee\phi_{l}$, then
$\phi^{\prime}=\phi_{1}^{\prime}\wedge\dots\wedge\phi_{l}^{\prime}$, and a
nearly identical proof shows that
$\overline{G}_{\phi}^{\dagger}=\overline{G}_{\phi^{\prime}}$.

Now that we have shown an isomorphism between $G^{\prime}_{\phi}$ and
$G_{\phi^{\prime}}$, note that $G^{\prime}_{\phi}(x)$ is the subgraph of
$G^{\prime}_{\phi}$ that includes all those edges where $x_{e}=0$. On the
other hand $G_{\phi^{\prime}}(x)$ is the graph that includes all those edges
where $x_{e}=1.$ Taking the bitwise negation of $x$, we find that
$G^{\prime}_{\phi}(x)=G_{\phi^{\prime}}(\bar{x})$. ∎

Lemma 35 allows us to prove Claim 17: See 17

###### Proof.

If $\phi=\phi_{1}\vee\cdots\vee\phi_{l}$, then
$\phi^{\prime}=\phi_{1}^{\prime}\wedge\cdots\wedge\phi_{l}^{\prime}$. From
Lemma 35, $G^{\prime}_{\phi}(x)=G_{\phi^{\prime}}(\bar{x})$, which using
Definition 34 is composed of $\\{G_{\phi_{i}^{\prime}}(\bar{x})\\}_{i=1}^{l}$
in series. But using the isomorphism of Lemma 35 again, this is just
$\\{G^{\prime}_{\phi_{i}}(x)\\}_{i=1}^{l}$ composed in series. The proof for
$\phi=\phi_{1}\wedge\cdots\wedge\phi_{l}$ is similar. ∎

Now we can prove Lemma 14, which relates the existence of a path in
$G_{\phi}(x)$ or $G^{\prime}_{\phi}(x)$ to the value of the function
$\phi(x):$ See 14

###### Proof.

We will prove the statement by induction on the depth of $\phi$. If
$\phi=x_{j}$ has depth 0, then $G_{\phi}$ is just an edge $(\\{s,t\\},x_{j})$,
and $G_{\phi}^{\prime}$ is just an edge $(\\{s^{\prime},t^{\prime}\\},x_{j})$.
Thus $s$ and $t$ are connected in $G_{\phi}(x)$ if and only if $x_{j}=1$, in
which case $\phi$ evaluates to 1, and $s^{\prime}$ and $t^{\prime}$ are
connected in $G_{\phi^{\prime}}$ if and only if $x_{j}=0$, in which case
$\phi$ evaluates to $0$.

If $\phi=\phi_{1}\wedge\dots\wedge\phi_{l}$, then $G_{\phi}$ consists of
$G_{\phi_{1}},\dots,G_{\phi_{l}}$ connected in series from $s$ to $t$, and
moreover, $G_{\phi}(x)$ consists of $G_{\phi_{1}}(x),\dots,G_{\phi_{l}}(x)$
connected in series from $s$ to $t$. Thus an $st$-path in $G_{\phi}(x)$
consists of an $st$-path in $G_{\phi_{1}}(x)$, followed by an $st$-path in
$G_{\phi_{2}}(x)$, etc., up to an $st$-path in $G_{\phi_{l}}(x)$. Thus, $s$
and $t$ are connected in $G_{\phi}(x)$ if and only if $s$ and $t$ are
connected in each $G_{\phi_{1}}(x),\dots,G_{\phi_{l}}(x)$, which happens if
and only if $\phi_{1}(x)\wedge\dots\wedge\phi_{l}(x)=1$.

On the other hand, by Claim 17, $G_{\phi}^{\prime}$ consists of
$G_{\phi_{1}}^{\prime},\dots,G_{\phi_{l}}^{\prime}$ connected in parallel
between $s^{\prime}$ and $t^{\prime}$. So any $s^{\prime}t^{\prime}$-path in
$G_{\phi}^{\prime}(x)$ is an $s^{\prime}t^{\prime}$-path in one of the
$G_{\phi_{i}}^{\prime}(x)$, which is equivalent to an $st$-path in one of
$G_{\phi_{i}^{\prime}}(\bar{x})$. Thus, by Lemma 35 $s^{\prime}$ and
$t^{\prime}$ are connected in $G_{\phi}^{\prime}(x)$ if and only if
$\phi_{1}^{\prime}(\bar{x})\vee\dots\vee\phi_{l}^{\prime}(\bar{x})=\neg\phi_{1}(x)\vee\dots\vee\neg\phi_{l}(x)=1$.
By de Morgan’s law is true if and only if
$\phi(x)=\phi_{1}(x)\wedge\dots\wedge\phi_{l}(x)=0$.

The case when $\phi=\phi_{1}\vee\dots\vee\phi_{l}$ is similar. ∎

##  Appendix C Classical Lower Bound on Class of Promise Boolean Formulas

In this section, we consider the query complexity of classical algorithms for
and-or formulas, proving Theorem 19. To do this, we use a recent tool from
Ben-David and Kothari [5]. They show that the bounded-error classical
randomized query complexity of a function $f$, denoted $R(f)$, satisfies
$R(f)=\Omega(RS(f))$, where $RS(f)$ is the randomized sabotage complexity,
defined presently. Furthermore, they prove that for a composed function
$f\circ g$, $RS(f\circ g)\geq(RS(f)RS(g))$.

If $f:D\rightarrow\\{0,1\\}$, with $D\subseteq\\{0,1\\}^{N}$, let
$f_{\textrm{sab}}:D_{\textrm{sab}}\rightarrow\\{0,1\\}$, where

$\displaystyle
D_{\textrm{sab}}=\\{x\in\\{0,1,*\\}^{N}\cup\\{0,1,\dagger\\}^{N}:x\textrm{ is
consistent with }y,y^{\prime}\in D,\textrm{ s.t. }f(y)\neq f(y^{\prime})\\}.$
(66)

We say $x\in\\{0,1,*,\dagger\\}^{N}$ is consistent with $y\in\\{0,1\\}^{N}$ if
$x_{i}=y_{i}$ for all $i\in[N]$ such that $x_{i}\in\\{0,1\\}$. Then,
$f_{\textrm{sab}}(x)=1$ if $x\in\\{0,1,*\\}^{N}$, and $f_{\textrm{sab}}(x)=0$
if $x\in\\{0,1,\dagger\\}^{N}$. Finally, the randomized sabotage complexity is
given by $RS(f)=R_{0}(f_{\textrm{sab}}),$ where $R_{0}(f)$ is the zero-error
randomized query complexity of $f$. (For further classical query complexity
definitions, see [5].)

We first bound the sabotage complexity of $\textsc{and}|_{D_{N,h}}$ and
$\textsc{or}|_{D_{N,h}^{\prime}}$:

######  Lemma 36.

$RS\left(\textsc{or}|_{D_{N,h}^{\prime}}\right)=RS\left(\textsc{and}|_{D_{N,h}}\right)=\Omega(N/h)$.

###### Proof.

For $x\in[D^{\prime}_{N,h}]_{\textrm{sab}}$ to be consistent with
$y,y^{\prime}\in D^{\prime}_{N,h}$ such that
$\textsc{or}(y)\neq\textsc{or}(y^{\prime}),$ we must have that
$x\in\\{0,*\\}^{N}\cup\\{0,\dagger\\}^{N}$. Furthermore, the number of $*$’s
or $\dagger$’s in $x$ must be at least $h$. Thus the sabotaged problem reduces
to finding at least one marked item out of $n$, promised there are at least
$h$ marked items. The randomized bounded-error query complexity of this task
is $\Omega(N/h)$, and so by Theorem 3 in [5],

$\displaystyle
RS\left(\textsc{or}|_{D^{\prime}_{N,h}}\right)=R_{0}\left((\textsc{or}|_{D^{\prime}_{N,h}})_{\text{sab}}\right)=\Omega\left(R\left((\textsc{or}|_{D^{\prime}_{N,h}})_{\text{sab}}\right)\right)=\Omega(N/h).$
(67)

The proof for and is similar. ∎

The next corollary follows immediately from Lemma 36 and the composition
property of sabotage complexity:

######  Corollary 37.

Let $\phi=\phi_{1}\circ\phi_{2}\circ\cdots\circ\phi_{l}$, where for each
$i\in[l]$, $\phi_{i}=\textsc{or}|_{D_{N_{i},h_{i}}^{\prime}}$ or
$\phi_{i}=\textsc{and}|_{D_{N_{i},h_{i}}}$. Then
$R(\phi)=\Omega\left(\prod_{i=1}^{l}N_{i}/h_{i}\right).$

Now that we understand the query complexity of symmetric composed and-or
formulas, we can look at how this compares to the quantum query complexity of
evaluating such functions. We now prove the following lemma.

######  Lemma 38.

Let $\phi=\phi_{1}\circ\phi_{2}\circ\cdots\circ\phi_{l}$, where for each
$i\in[l]$, $\phi_{i}=\textsc{or}|_{D_{N_{i},h_{i}}^{\prime}}$ or
$\phi_{i}=\textsc{and}|_{D_{N_{i},h_{i}}}$. Let $D$ be the domain of $\phi.$
Then

$\displaystyle\frac{\prod_{i=1}^{l}N_{i}}{\prod_{i=1}^{l}h_{i}}=\left(\max_{x\in
D:\phi(x)=1}R_{s,t}(G_{\phi}(x))\right)\left(\max_{x\in
D:\phi(x)=0}R_{s,t}(G^{\prime}_{\phi}(x))\right).$ (68)

###### Proof.

The proof follows by induction on the number of compositions. First suppose
that $\phi=\textsc{or}|_{D_{N,h}^{\prime}}$. Then $G_{\phi}$ consists of $N$
edges connected in parallel between $s$ and $t$, and $G_{\phi}^{\prime}$
consists of $N$ edges connected in series. The only input $x$ such that
$\phi(x)=0$ is the all zeros input. Therefore $\max_{x\in
D:\phi(x)=0}R_{s,t}(G_{\phi}^{\prime}(x))=N.$ Now notice (using Claim 5) that
$R_{s,t}(G_{\phi}(x))=1/|x|.$ However because of the domain of
$\textsc{or}_{N_{i},h_{i}}$, inputs $x$ have $|x|\geq h$, so $\max_{x\in
D:\phi(x)=1}R_{s,t}(G_{\phi}(x))=1/h.$ Thus

$\displaystyle N/h=\left(\max_{x\in
D:\phi(x)=1}R_{s,t}(G_{\phi}(x))\right)\left(\max_{x\in
D:\phi(x)=0}R_{s,t}(G^{\prime}_{\phi}(x))\right).$ (69)

A similar analysis holds for the base case $\phi=\textsc{and}|_{D_{N,h}}$.

Now for the inductive step, let $\phi=\phi_{1}\circ\xi$ for
$\xi=\phi_{2}\circ\dots\circ\phi_{l}$, where for each $i$, $\phi_{i}$ is
either $\textsc{or}|_{D_{N_{i},h_{i}}^{\prime}}$ or
$\textsc{and}|_{D_{N_{i},h_{i}}}$. Let $D_{\xi}$ be the domain of $\xi$ and
let $x^{j}\in D_{\xi}$ denote the bits of $x$ that are input to the
$j^{\textrm{th}}$ copy of $\xi$. Suppose first that
$\phi_{1}=\textsc{or}|_{D_{N_{1},h_{1}}^{\prime}}$. $G_{\phi}^{\prime}$ is
formed by taking the $N_{1}$ graphs $G_{\xi}^{\prime}$ and connecting them in
series. The only way $\phi(x)=0$ is if the input $x^{j}\in D_{\xi}$ to each of
the $\xi$ functions satisfies $\xi(x^{j})=0$, so by Claim 5

$\displaystyle\max_{x\in
D:\phi(x)=0}R_{s,t}(G_{\phi}^{\prime}(x))=N_{1}\max_{y\in
D_{\xi}:\xi(y)=0}R_{s,t}(G_{\xi}^{\prime}(y)).$ (70)

On the other hand, $G_{\phi}$ is formed by taking $N_{1}$ graphs $G_{\xi}$ and
connecting them in parallel. Using Claim 5, if $x^{j}\in D_{\xi}$ is the input
to $j^{\textrm{th}}$ function $\xi$, we have

$\displaystyle
R_{s,t}(G_{\phi}(x))=\left(\sum_{j=1}^{N}\frac{1}{R_{s,t}(G_{\xi}(x^{j}))}\right)^{-1}.$
(71)

Thus larger values for $R_{s,t}(G_{\phi}(x))$ come from cases where
$R_{s,t}(G_{\xi}(x^{j}))$ are large. Now

$\displaystyle\max_{x\in D_{\xi}}R_{s,t}(G_{\xi}(x))=\infty,$ (72)

which occurs when $\xi(y)=0$. Because of the promise on the domain of
$\phi_{1}$, there must be at least $h_{1}$ of the $N_{1}$ subformulas $\xi$
that evaluate to $1$. On each of those subformulas, we want to have an input
$x^{j}\in D_{\xi}$ that maximizes the effective resistance of that subformula.
Therefore, we have

$\displaystyle\max_{x\in D:\phi(x)=1}R_{s,t}(G_{\phi}(x))=$
$\displaystyle\left(\frac{h_{1}}{\max_{y\in
D_{\xi}:\xi(y)=1}R_{s,t}(G_{\xi_{j}}(y)}\right)^{-1}=\frac{\max_{y\in
D_{\xi}:\xi(y)=1}R_{s,t}(G_{\xi_{j}}(y))}{h_{1}}.$ (73)

Therefore, using the inductive assumption,

$\displaystyle\left(\max_{x\in
D:\phi(x)=1}R_{s,t}(G_{\phi}(x))\right)\left(\max_{x\in
D:\phi(x)=0}R_{s,t}(G_{\phi}^{\prime}(x))\right)$ $\displaystyle=$
$\displaystyle\frac{N_{1}}{h_{1}}\max_{y\in
D_{\xi}:\xi(y)=1}R_{s,t}(G_{\xi_{j}}(y^{j}))\max_{y\in
D_{\xi}:\xi(y)=0}R_{s,t}(G_{\xi}^{\prime}(y))=\frac{\prod_{i=1}^{l}N_{i}}{\prod_{i=1}^{l}h_{i}}.$
(74)

The inductive step for $\phi_{1}=\textsc{and}|_{D_{N,h}}$ is similar. ∎

Corollary 37 and Lemma 38 give Theorem 19.

##  Appendix D NAND-tree Proofs

###  D.1 Relationship Between Faults and Effective Resistance

In this section, we prove Lemma 22: See 22

###### Proof.

We will give a proof for ${\cal F}_{A}(x)$; the case of ${\cal F}_{B}(x)$ is
similar.

First, $R_{s,t}(G_{\textsc{nand}_{d}}(x))=\infty$ if and only if $s$ and $t$
are not connected in $G_{\textsc{nand}_{d}}(x)$, which, by Lemma 14, occurs if
and only if $x$ is a 0-instance. This means exactly that $x$ is not
$A$-winnable, which, by Eq. (28), holds if and only if ${\cal
F}_{A}(x)=\infty$. Thus, suppose this is not the case, so ${\cal
F}_{A}(x)<\infty$.

The rest of the proof is by induction. We need to look at both odd and even
cases. For the case of $d=0$, the only $A$-winnable input in
$\\{0,1\\}^{2^{0}}$ is $x=1$. In that case, using Eq. (28), ${\cal
F}_{A}(x)=1$, since there are no decision nodes for Player $A$, and since
$G_{\textsc{nand}_{0}}(x)$ is just a single edge from $s$ to $t$,
$R_{s,t}(G_{\textsc{nand}_{0}}(x))=1$.

Let $x\in\\{0,1\\}^{2^{d}}$ be any $A$-winnable input with $d>1$. We let
$x^{0}$ be the first $2^{d-1}$ bits of $x$ and $x^{1}$ be the last $2^{d-1}$
bits of $x$, so $x=(x^{0},x^{1})$.

We first consider odd $d>1$. Using the definition of $G_{\phi}$ from Section
4, and the fact that for $d$ odd, the root node is an $\wedge$-node, we see
that $G_{\textsc{nand}_{d}}(x)$ consists of $G_{\textsc{nand}_{d-1}}(x^{0})$
and $G_{\textsc{nand}_{d-1}}(x^{1})$ connected in series, so by Claim 5

$\displaystyle
R_{s,t}(G_{\textsc{nand}_{d}}(x))=R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))+R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1})).$
(75)

Now the root can not be a fault, because it is a decision node for Player $B$,
but we know the tree is $A$-winnable, so no choice Player $B$ makes would
allow her to win the game. Therefore, both subtrees connected to the root node
must be $A$-winnable. Using Eq. (28) we have

$\displaystyle{\cal{F}}_{A}(x^{0})+{\cal{F}}_{A}(x^{1})\leq\max_{b\in\\{0,1\\}}{2\cal{F}}_{A}(x^{b})=2{\cal{F}}_{A}(x).$
(76)

Combining Eqs. (75) and (76) and the inductive assumption for even depth
trees, we have for odd $d$,

$\displaystyle R_{s,t}(G_{\textsc{nand}_{d}}(x))\leq 2{\cal{F}}_{A}(x).$ (77)

Now we consider the case that $d$ is even, so the root is a decision node for
Player $A$. Consequently, the root node is a $\vee$-node, so by Claim 5

$\displaystyle
R_{s,t}(G_{\textsc{nand}_{d}}(x))=\left(\frac{1}{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))}+\frac{1}{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1}))}\right)^{-1}.$
(78)

Suppose the root is a fault. Without loss of generality, let’s assume the
subtree with input $x^{0}$ is not $A$-winnable. Then
$R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))=\infty$ so Eq. (78) becomes

$\displaystyle
R_{s,t}(G_{\textsc{nand}_{d}}(x))=R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1})).$
(79)

Using the inductive assumption for odd depth trees, Eq. (28), and the fact
that the root is a fault, we have

$\displaystyle R_{s,t}(G_{\textsc{nand}_{d}}(x))\leq
2{\cal{F}}(x^{1})={\cal{F}}(x).$ (80)

If the root is not a fault, then both
$R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))$ and
$R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1}))$ are finite, so from (78), and using
the inductive assumption, we have

$\displaystyle R_{s,t}(G_{\textsc{nand}_{d}}(x))$
$\displaystyle\leq\frac{1}{2}\max\\{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0})),R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1}))\\}$
$\displaystyle\leq\max\\{{\cal{F}}(x^{0}),{\cal{F}}(x^{1})\\}={\cal{F}}(x).$
(81)

A similar analysis for ${\cal F}_{B}(x)$ completes the proof. ∎

###  D.2 Estimating Effective Resistances

In this section, we will prove Lemma 25, which bounds the query complexity of
estimating the effective resistance of a graph corresponding to a Boolean
formula. In [17], Ito and Jeffery describe a quantum query algorithm to
estimate the positive or negative witness size of a span program given access
to $\mathcal{O}_{x}$. We will describe how to use this algorithm to estimate
the effective resistance of graphs $G_{\phi}(x)$ or $G^{\prime}_{\phi}(x)$.

Ref. [17] define the _approximate positive and negative witness sizes_ ,
$\tilde{w}_{+}(x,P)$ and $\tilde{w}_{-}(x,P)$. These are similar to the
positive and negative witness sizes, but with the conditions $|w\rangle\in
H(x)$ and $\omega A\Pi_{H(x)}=0$ relaxed.

######  Definition 39 (Approximate Positive Witness).

For any span program $P$ on $\\{0,1\\}^{N}$ and $x\in\\{0,1\\}^{N}$, we define
the _positive error of $x$ in $P$_ as:

$e_{+}(x)=e_{+}(x,P):=\min\left\\{\left\|\Pi_{H(x)^{\bot}}|w\rangle\right\|^{2}:A|w\rangle=\tau\right\\}.$
(82)

We say $|w\rangle$ is an _approximate positive witness_ for $x$ in $P$ if
$\left\|\Pi_{H(x)^{\bot}}|w\rangle\right\|^{2}=e_{+}(x)$ and
$A|w\rangle=\tau.$ We define the _approximate positive witness size_ as

$\tilde{w}_{+}(x)=\tilde{w}_{+}(x,P):=\min\left\\{\left\||w\rangle\right\|^{2}:A|w\rangle=\tau,\left\|\Pi_{H(x)^{\bot}}|w\rangle\right\|^{2}=e_{+}(x)\right\\}.$
(83)

If $x\in P_{1}$, then $e_{+}(x)=0$. In that case, an approximate positive
witness for $x$ is a positive witness, and $\tilde{w}_{+}(x)=w_{+}(x)$. For
negative inputs, the positive error is larger than 0.

We can define a similar notion of approximate negative witnesses:

######  Definition 40 (Approximate Negative Witness).

For any span program $P$ on $\\{0,1\\}^{N}$ and $x\in\\{0,1\\}^{N}$, we define
the _negative error of $x$ in $P$_ as:

$e_{-}(x)=e_{-}(x,P):=\min\left\\{\left\|\omega
A\Pi_{H(x)}\right\|^{2}:\omega\in\mathcal{L}(U,\mathbb{R}),\omega\tau=1\right\\}.$
(84)

Any $\omega$ such that $\left\|\omega A\Pi_{H(x)}\right\|^{2}=e_{-}(x,P)$ is
called an _approximate negative witness_ for $x$ in $P$. We define the
_approximate negative witness size_ as

$\tilde{w}_{-}(x)=\tilde{w}_{-}(x,P):=\min\left\\{\left\|\omega
A\right\|^{2}:\omega\in\mathcal{L}(U,\mathbb{R}),\omega\tau=1,\left\|\omega
A\Pi_{H(x)}\right\|^{2}=e_{-}(x,P)\right\\}.$ (85)

If $x\in P_{0}$, then $e_{-}(x)=0$. In that case, an approximate negative
witness for $x$ is a negative witness, and $\tilde{w}_{-}(x)=w_{-}(x)$. For
positive inputs, the negative error is larger than 0.

Then Ito and Jeffery give the following result:

######  Theorem 41 ([17]).

Fix $X\subseteq\\{0,1\\}^{N}$ and $f:X\rightarrow\mathbb{R}_{\geq 0}$. Let $P$
be a span program such that for all $x\in X$, $f(x)=w_{+}(x,P)$ and define
$\widetilde{W}_{-}=\widetilde{W}_{-}(P,f)=\max_{x\in X}\tilde{w}_{-}(x,P)$.
There exists a quantum algorithm that estimates $f$ to relative error
$\varepsilon$ and that uses
$\widetilde{\mathrm{O}}\left(\frac{1}{\varepsilon^{3/2}}\sqrt{w_{+}(x)\widetilde{W}_{-}}\right)$
queries. Similarly, let $P$ be a span program such that for all $x\in X$,
$f(x)=w_{-}(x,P)$ and define
$\widetilde{W}_{+}=\widetilde{W}_{+}(P,f)=\max_{x\in X}\tilde{w}_{+}(x,P)$.
Then there exists a quantum algorithm that estimates $f$ to accuracy
$\varepsilon$ and that uses
$\widetilde{\mathrm{O}}\left(\frac{1}{\varepsilon^{3/2}}\sqrt{w_{-}(x)\widetilde{W}_{+}}\right)$
queries.

We will apply Theorem 41 to the span program $P_{G,c}$ defined in Eq. (3),
with $G=G_{\phi}$. Throughout this section, we will always set the weight
function $c$ to take value one on all edges of the graph $G$. In this, case,
to simplify notation, we will denote the span program $P_{G,c}$ as $P_{G}.$ To
apply Theorem 41, we need bounds on $\widetilde{W}_{+}(P_{G_{\phi}})$ and
$\widetilde{W}_{-}(P_{G_{\phi}})$. We will prove:

######  Lemma 42.

For any formula $\phi$, its $\wedge$-depth is the largest number of
$\wedge$-labeled nodes on any path from the root to a leaf. Let $\phi$ be any
and-or formula with maximum fan-in $l$, $\wedge$-depth $0pt_{\wedge}$, and
$\vee$-depth $0pt_{\vee}$. Then
$\widetilde{W}_{+}(P_{G_{\phi}})\leq\frac{1}{2}l^{0pt_{\wedge}}$ and
$\widetilde{W}_{-}(P_{G_{\phi}})\leq 2l^{0pt_{\vee}}$.

Then, applying Lemma 42 and Theorem 41, we have the main result of this
section, which was first stated in Section 5.2:

See 25

###### Proof of Lemma 25.

By Theorem 41, since $R_{s,t}(G_{\phi}(x))=\frac{1}{2}w_{+}(x,P_{G_{\phi}})$