# Multidimensional Quantum Walks, Recursion,
and Quantum Divide & Conquer

Stacey Jeffery  CWI, Amsterdam  QuSoft & University of Amsterdam  Galina Pass
QuSoft & University of Amsterdam

###### Abstract

We introduce an object called a _subspace graph_ that formalizes the technique
of multidimensional quantum walks. Composing subspace graphs allows one to
seamlessly combine quantum and classical reasoning, keeping a classical
structure in mind, while abstracting quantum parts into subgraphs with simple
boundaries as need. As an example, we show how to combine a _switching
network_ with arbitrary quantum subroutines, to compute a composed function.
As another application, we give a time-efficient implementation of quantum
Divide & Conquer when the sub-problems are combined via a symmetric Boolean
formula. We use this to quadratically speed up Savitch’s algorithm for
directed $st$-connectivity.

##  1 Introduction

There are a number of graphical ways of reasoning about how the steps or
subroutines of a classical algorithm fit together. For example, it is natural
to think of a (randomized) classical algorithm as a (randomized) decision tree
(or branching program), where different paths are chosen depending on the
input, as well as random choices made by the algorithm. A deterministic
algorithm gives rise to a computation _path_ , a randomized algorithm to a
computation _tree_. The edges of a path or tree, representing steps of
computation, might be implemented by some subroutine that is also realized by
a path (or tree) – we can abstract the subroutine’s details by viewing it as
an edge, or zoom in and see those details, as convenient. More generally, we
often think of a classical randomized algorithm as a random walk on a
(possibly directed) graph, where there may be multiple parallel paths from
point $a$ to point $b$, with the cost of getting from $a$ to $b$ being derived
from the expected length of these paths.

This picture appears to break down for quantum algorithms, at least in the
standard circuit model. A quantum circuit can be thought of as a path, with
edges representing its steps, but it is unclear how to augment this reasoning
with subroutines. Consider calling subroutines with varying time complexities
$\\{T_{i}\\}_{i}$ in superposition. Even if the subroutines are all classical
deterministic, in the standard quantum circuit model, we tend to incur a cost
of $\max_{i}T_{i}$ if we call a superposition of subroutines, since we must
wait for the slowest subroutine to finish before we can apply the next step of
the computation. This problem was addressed in [Jef22], where the technique of
multidimensional quantum walks [JZ23] was used to show how to get an average
in place of a max in several settings where a quantum algorithm calls
subroutines in superposition: a general setting, as well as the setting of
quantum walks. The intuition behind this work is that a quantum walk does keep
the classical intuition of parallel paths representing a superposition of
possible computations, and _any_ quantum algorithm can be viewed as some sort
of a quantum walk on a simple underlying graph (something like a path), but
with some additional structure associated with it.

Multidimensional quantum walks, which we study more formally in this paper as
an object than has been done previously, are valuable as a way of combining
quantum and classical reasoning. A quantum algorithm can be abstracted as a
graph with perhaps complicated internal structure, but a simple _boundary_
with an “in” and an “out” terminal, that can be seamlessly hooked into other
graph-like structures, perhaps representing simple classical reasoning, such
as a quantum random walk, or perhaps with their own complicated very quantum
parts.

##### Subspace Graphs

While [JZ23] and [Jef22] use similar techniques, it is not formally defined
what a multidimensional quantum walk is. We formally define an object called a
_subspace graph_ (Definition 3.1) that abstracts the structures in [JZ23] and
[Jef22]. A subspace graph is simply a graph with some subspaces associated
with each edge and vertex, where the structure of the graph constrains how the
spaces can overlap. Defining what we mean, precisely, by a multidimensional
quantum walk (i.e. subspace graph) is the first step to developing a general
theory of recursive constructions of subspace graphs.

The recursive structure of subspace graphs is useful for composing quantum
algorithms, but as a design tool, it is also convenient to be able to view a
subspace graph in varying levels of abstraction. We can “zoom out” and view a
complicated process as just a special “edge”, or zoom in on that edge and
understand its structure as an involved graph with additional structure.

We cannot hope to be able to understand all quantum algorithms using purely
classical ideas – quantum computing is _not_ classical computing. But perhaps
the next best thing is a way to seamlessly combine classical and quantum
ideas, extending the classical intuition to its limits, and then employing
quantum reasoning when needed, but with the possibility of abstracting out
from it when needed as well, using a fully quantum form of abstraction.

In this work, we consider one specific kind of composition of subspace graphs
called _switch composition_ – another type is implicit in [Jef22] – but we
would like to emphasize the potential for more general types of recursion,
which we leave for future work.

##### Time-Efficient Quantum Divide & Conquer

A particular type of recursive algorithm is _divide & conquer_, in which a
problem is broken into multiple smaller sub-problems, whose solutions,
obtained by recursive calls, are combined into a solution for the original
problem. As a motivating example, consider the recursively defined _nand-tree
function_. Let $f_{k,d}:\\{0,1\\}^{d^{k}}\rightarrow\\{0,1\\}$ be defined
$f_{0,d}(x)=x$, and for $k\geq 1$,

$f_{k,d}(x)=1-f_{k-1,d}(x^{(1)})\dots f_{k-1,d}(x^{(d)}),$

where each $x^{(j)}\in\\{0,1\\}^{d^{k-1}}$, and $x=(x^{(1)},\dots,x^{(d)})$.
There is a natural way to break an instance $x$ of $f_{k,d}$ into $d$ sub-
problems $x^{(1)},\dots,x^{(d)}$ of $f_{k-1,d}$, and combine the solutions by
taking the NAND (negated AND) of the $d$ sub-problem solutions. A quantum
algorithm computes this NAND in $O(\sqrt{d})$ queries, so we might hope for a
speedup by recursive calls to this quantum algorithm. Unfortunately, since we
recurse to depth $k$, the constant in front of $\sqrt{d}$ is raised to the
$k$-th power. This kills the quantum speedup completely when $d$ is constant
(for example, the most common setting of $d=2$), and that is not even touching
on the fact that we would seem to need to amplify the success probability of
the subroutine, turning those constants into log factors. On the other hand,
it is known [Rei11] that $f_{k,d}$ can be evaluated in $O(\sqrt{d^{k}})$
quantum queries, even though our attempt to use classical divide-&-conquer
reasoning combined with the basic Grover speedup failed.

More recently, [CKKD+22] showed how to employ divide-&-conquer reasoning in
the study of quantum query complexity, in which one only counts the number of
queries to the input. Their result were not constructive, in the sense that
they did not fully specify algorithms, and in particular, the time complexity
analysis of their results was unknown. In this work, we use the framework of
subspace graphs to give a time-complexity version of some of the query
complexity results obtained in [CKKD+22]. In particular, we show (see Theorem
4.11 for formal statement):

######  Theorem 1.1 (Informal).

Let $\\{f_{\ell,n}:D_{\ell,n}\rightarrow\\{0,1\\}\\}_{\ell,n}$ be a family of
functions. Let $\varphi$ be a balanced Boolean formula on $a+1$ variables, and
suppose $f_{\ell,n}=\varphi(f_{\ell/b,n},\dots,f_{\ell/b,n},f_{aux,\ell,n})$,
for some $b>1$ and some auxiliary function $f_{aux,\ell,n}$ with quantum time
complexity $T_{\mathrm{aux}}(\ell,n)$. Then the quantum time complexity of
$f_{\ell,n}$ is $\widetilde{O}(T(\ell,n))$ for $T(\ell,n)$ satisfying:

$T(\ell,n)\leq\sqrt{a}T(\ell/b,n)+T_{\mathrm{aux}}(\ell,n).$

We can compare this with the analogous classical statement, which would have
$a$ instead of $\sqrt{a}$. As an application, we get a quadratic speedup of
Savitch’s divide-&-conquer algorithms for directed $st$-connectivity.

To achieve these results, it is essential that we compose subspace graphs,
rather than algorithms. When we convert a subspace graph to a quantum
algorithm, we get constant factors in the complexity, and these seem necessary
without at least specifying what gateset we are working in. By first composing
in the more abstract model of subspace graphs, and then only converting to a
quantum algorithm at the end, we ensure these factors only come into the
complexity once. This is similar to compositions done with other abstract
models, such as span programs, and transducers [BJY23].

##### Switching Networks

A switching network is a graph with Boolean variables associated with the
edges that can switch the edges on or off. Originally used to model certain
hardware systems, including automatic telephone exchanges, and industrial
control equipment [Sha38], a switching network has an associated function $f$
that is 1 if and only if two special vertices, $s$ and $t$, are connected by a
path of “on” edges. Shannon [Sha38, Sha49] showed that series-parallel
switching networks are equivalent to Boolean formulas, and Lee [Lee59] showed
that switching networks can model branching programs. These theoretical
results have given this model a place in classical complexity theory, where
they can be used to study classical space complexity and circuit depth (see
[Pot15]).

Quantum algorithms for evaluating switching networks111Switching networks have
never been directly referred to in prior work on quantum algorithms, as far as
we are aware, but the “$st$-connectivity problems” referred to in [JK17] are,
in fact, switching networks. were given in [JK17], using a span program
construction based heavily on [BR12]. Tight analysis of these span programs
for any switching network was completed in [JJKP18].

From [JK17, JJKP18], we get a quantum algorithm for evaluating any switching
network when we have query access to the edge variables. Let ${\cal
R}_{s,t}(G(x))$ be the effective resistance (see Definition 2.1) in the
subgraph of “on” edges whenever $f(x)=1$, and whenever $f(x)=0$, let
$F_{x}\subseteq E$ be the minimum weight $st$-cut-set (see Definition 2.2)
consisting of only edges that are “off”. Then the time complexity of
evaluating the switching network is

$\sqrt{\max_{x\in f^{-1}(1)}{\cal R}_{s,t}(G(x))\max_{x\in
f^{-1}(0)}\sum_{e\in F_{x}}{\sf w}_{e}},$

assuming we can implement a certain reflection related to the particular
switching network in unit time. From this it follows that if we can query the
variable associated with an edge $e$ in time $T_{e}$, we can evaluate the
switching network in time

$\sqrt{\max_{x\in f^{-1}(1)}{\cal R}_{s,t}(G(x))\max_{x\in
f^{-1}(0)}\sum_{e\in F_{x}}{\sf w}_{e}}.\max_{e\in E}T_{e}.$

Here we improve this to (see Theorem 4.13):

$\sqrt{\max_{x\in f^{-1}(1)}{\cal R}_{s,t}(G(x))\max_{x\in
f^{-1}(0)}\sum_{e\in F_{x}}{\sf w}_{e}T_{e}^{2}}.$

This is analogous to results of [Jef22], which showed a similar statement, but
for quantum walks rather than switching networks. Because switching networks
perfectly model Boolean formulas, without the constant overhead we get when we
convert to a quantum algorithm, they can be used as a building block for our
divide & conquer results.

##### Application to DSTCON

Quantum algorithms for $st$-connectivity on _undirected graphs_ , which are
closely related to evaluating switching networks, are well studied [DHHM06,
BR12, JK17, JJKP18, AJPW22], including quantum algorithms that achieve optimal
time- and space-complexity simultaneously, in both the edge-list access model,
and the adjacency matrix access model.222We do not make a distinction between
various access models, because they can simulate one another in poly$(n)$ time
and $\log(n)$ space, so our result, which includes a $2^{O(\log n)}$ term, is
the same in all models. In contrast, quantum algorithms for _directed_
$st$-connectivity (dstcon) – the problem of deciding if there is a directed
path from $s$ to $t$ in a directed graph – is less well understood. The
algorithm of [DHHM06] also applies to directed graphs, deciding connectivity
in $\widetilde{O}(n)$ time and space333In the edge-list access model.. This
algorithm has optimal time complexity, whereas its space complexity is far
from optimal.

Directed $st$-connectivity, also called _reachability_ , is a fundamental
problem in classical space complexity. In particular, understanding if this
problem can be solved in $\log(n)$ space by a quantum algorithm would resolve
the relationship between quantum logspace complexity and ${\sf NL}$, as dstcon
is ${\sf NL}$-complete.

The best known classical (deterministic) space complexity of dstcon is
$O(\log^{2}(n))$, using Savitch’s algorithm. We apply quantum divide & conquer
(Theorem 1.1) to give a quadratic speedup to Savitch’s algorithm, achieving
$2^{\frac{1}{2}\log^{2}(n)+O(\log(n))}$ time, while still maintaining
$O(\log^{2}(n))$ space (see Theorem 5.3).

##### Model of Computation

We work in the same model as [JZ23], where we allow not only arbitrary quantum
gates, but also assume subroutines are given via access to a unitary that
applies the subroutine’s $t$-th gate controlled on the value $t$ in some time
register. This is possible, for example, with quantum random access gates. See
Section 2.1 for details.

##### Related and Future Work

While writing this manuscript, we became aware of an independent work that
also achieves time-efficient quantum divide & conquer [ABB+23] when either (1)
$\varphi$ is an OR (equivalently, an AND) or (2) $\varphi$ is a minimum or
maximum. Case (1) is a special case of our work, while case (2) is not. In
that sense, our results are incomparable. Ref. [ABB+23] also gives
applications to problems that are distinct from ours.

We also mention that Ref. [CKKD+22] analyzes the query complexity of quantum
divide & conquer where $\varphi$ is an arbitrary Boolean formula, as well as
in settings where the function combining the sub-problems is more general.
While our techniques do apply to composing quantum algorithms for arbitrary
functions (already studied in [Jef22]), an issue is a poor scaling in the
error of subroutines. If we start with a bounded-error quantum algorithm for
some function, we need to amplify the success probability, as it will be
called many times, incurring logarithmic factors. This becomes a serious
problem if the function is called recursively to depth more than constant. We
get around this in the case of Boolean formulas by using a switching network
construction (from which a quantum algorithm could be derived) rather than a
bounded-error quantum algorithm for evaluating the formula. For more general
functions, the solution might lie in a recent framework, _transducers_
[BJY23], that allows for the composition of quantum algorithms without the
need for success probability amplification. We leave further investigation for
future work.

We can compare the model of transducers [BJY23] to the framework of subspace
graphs introduced here. These models are related, in that they are both good
for analyzing the time complexity of composed quantum algorithms. A subspace
graph gives rise to a unitary that is the product of two reflections, and this
is a transducer, as discussed in [BJY23, Section 3.2]. Compared with the model
of subspace graphs, transducers are more general, and cleaner, in particular
how they are implemented as quantum algorithms. As far as we know, subspace
graphs fail to reproduce the composition results of transducers in terms of
error scaling. However, we feel that subspace graphs, with their additional
structure, are still useful for designing and reasoning about quantum
algorithms, especially those in which there is some classical intuition to
hold onto. It seems likely that, once designed in the framework of subspace
graphs, an algorithmic construction could be converted to the transducer
framework to achieve any advantage that is missing for subspace graphs. We
leave concrete exploration of the connection for future work.

Aside from the directions already mentioned, the most interesting future
direction is to study more general compositions of subspace graphs, and see to
what extent we can employ classical reasoning to quantum algorithms, and to
what extent this (hopefully gracefully) breaks down.

##  2 Preliminaries

###  2.1 Model of Computation

We will be talking about combining quantum subroutines, and here we describe
the model of access for the subroutines that we will assume. A quantum
algorithm or subroutine is a sequence of unitaries $U_{1},\dots,U_{T}$ acting
on some common space $H$. Given a set of subroutines
$\\{(U_{1}^{i},\dots,U_{T_{i}}^{i})\\}_{i\in{\cal I}}$, all acting on a space
$H$, but possibly running in different times, $T_{i}\leq T_{\max}$, we will
assume the operator $\sum_{i\in{\cal
I}}{\lvert}i\rangle{\langle}i\rvert\otimes\sum_{t=1}^{{T}_{\max}}{\lvert}t\rangle{\langle}t\rvert\otimes
U_{t}^{i}$ can be implemented in “unit cost”. We use “unit cost” to describe a
cost we are willing to accept as a multiplicative factor on all complexities
(for example, $O(1)$ or polylogarithmic in some natural variable). This
assumption is only reasonable if the unitaries each have unit cost. It does
not hold for strict gate complexity when $U_{1}^{i},\dots,U_{{T}_{\max}}^{i}$
are arbitrary gates, but it does hold in the _fully quantum_ QRAM model if
$U_{1}^{i},\dots,U_{{T}_{\max}}^{i}$ are stored as a list of gates in
classical memory to which a quantum computer has read-only superposition
access (sometimes referred to as “QRAM” in previous literature), or if they
satisfy certain uniformity conditions (see [JZ23, Section 2.2]).

###  2.2 Graph Theory

In this paper, a _graph_ will be an undirected graph, and we will only
consider directed graphs in Section 5. A graph $G=(V,E)$ has vertex set
$V=V(G)$ and edge set $E=E(G)$. For $u\in V$, we let $E(u)$ be the subset of
edges of $E$ that are incident to $u$. We assume for convenience that each
edge has an orientation, and $E^{\rightarrow}(u)\subseteq E(u)$ are the edges
oriented outwards from $u$, and $E^{\leftarrow}(u)=E(u)\setminus
E^{\rightarrow}(u)$ those oriented inwards. Then for any $e\in E$, there is a
unique $u\in V$ such that $e\in E^{\rightarrow}(u)$, and a unique $v\in V$
such that $e\in E^{\leftarrow}(v)$, and we can write $e=(u,v)$. We can
associate non-negative _weights_ $\\{{\sf w}_{e}\\}_{e\in E}$ to the edges of
$G$.

######  Definition 2.1.

A _flow_ on a weighted graph $G$ is a real-valued function $\theta$ on $E$.
Define

$\theta(u)\colonequals\sum_{e\in E^{\rightarrow}(u)}\theta(e)-\sum_{e\in
E^{\leftarrow}(u)}\theta(e).$

We call $\theta$ a _unit $st$-flow_ if $\theta(s)=-\theta(t)=1$, and for all
$u\in V\setminus\\{s,t\\}$, $\theta(u)=0$. The _effective resistance_ is
defined

${\cal R}_{s,t}(G)\colonequals\min_{\mbox{unit flows }\theta}\sum_{e\in
E}\frac{\theta(e)^{2}}{{\sf w}_{e}}.$

######  Definition 2.2.

An _$st$ -cut-set_ is a set $F\subseteq E$ whose removal from $G$ would leave
$s$ and $t$ in different connected components.

###  2.3 Function Composition and Boolean Formulas

A Boolean formula, $\varphi$, on $N$ variables is a rooted tree with $N$
leaves, where each internal vertex is labelled by either $\vee$ (OR) or
$\wedge$ (AND), and each leaf is labelled by a unique variable or its
negation. The depth of a formula is the length of the longest path from the
root to a leaf. We assume that for each internal vertex with $d$ children, the
outgoing edges are labelled by some $d$-element set, without loss of
generality, $[d]$, so that every vertex can be labelled by a string of the
labels of its path from the root. That is: the root is labelled by the empty
string, denoted $\emptyset$, and any other vertex is labelled by the label of
its parent, concatenated with the label of the edge from its parent to it. We
call the set of all strings labelling leaves $\Sigma$, so $|\Sigma|=N$. We let
$\Sigma_{i}$ denote the set of strings in $\Sigma$ whose first letter is $i$.
We let $\overline{\Sigma}$ denote the set of labels of all vertices, so it is
the set of prefixes of strings in $\Sigma$.

We label the variable associated with a leaf $\sigma\in\Sigma$ by $\sigma$ as
well. A fixed setting of the variables $x\in\\{0,1\\}^{\Sigma}$ induces a
value at each vertex of $\varphi$, as follows. If a leaf $\sigma$ is labelled
by an unnegated variable, then its value is $x_{\sigma}$, and otherwise its
value is $\neg x_{\sigma}$. If a vertex is not a leaf, if it is labelled by
$\vee$, then its value is the OR of all the values of its children, whereas if
it is labelled by $\wedge$, its value is the AND of all the values of its
children. We let $\varphi(x)$ denote the value of the root of the tree.

######  Definition 2.3.

We say a formula is _symmetric_ if for every internal node, the sub-trees of
its children are identical aside from their leaves.

For any $f:\\{0,1\\}^{\Sigma}\rightarrow\\{0,1\\}$ and
$\\{f_{\sigma}:\\{0,1\\}^{m_{\sigma}}\rightarrow\\{0,1\\}\\}_{\sigma\in\Sigma}$,
we define the composed function
$f\circ(f_{\sigma})_{\sigma\in\Sigma}:\\{0,1\\}^{\sum_{\sigma\in\Sigma}m_{\sigma}}\rightarrow\\{0,1\\}$
by

$f\circ(f_{\sigma})_{\sigma\in\Sigma}(x)=f(f_{\sigma}(x^{\sigma}))_{\sigma\in\Sigma}$

where $x=(x^{\sigma})_{\sigma\in\Sigma}$ is the $\sum_{\sigma}m_{\sigma}$-bit
string obtained by concatenating the strings $\\{x^{\sigma}\\}_{\sigma}$, and
$(f_{\sigma}(x^{\sigma}))_{\sigma\in\Sigma}$ is the $|\Sigma|$-bit string
whose $\sigma$-th bit is $f_{\sigma}(x^{\sigma})$. We can also write
$f\circ(f_{\sigma})_{\sigma\in F}$ for some $F\subset\Sigma$, in which case,
we implicitly assume that $f_{\sigma}$ is the identity on $\\{0,1\\}$ for all
$\sigma\in\Sigma\setminus F$. For a Boolean formula $\varphi$ on $\Sigma$, we
will also write $\varphi\circ(f_{\sigma})_{\sigma\in\Sigma}$ as a short-hand
for $f_{\varphi}\circ(f_{\sigma})_{\sigma\in\Sigma}$, where $f_{\varphi}$ is
the function computed by the formula.

###  2.4 Phase Estimation Algorithms

The technique of phase estimation dates back to [Kit96], but we will use a
specific application of this technique precisely defined in [JZ23], following
a blueprint that had already been used many times in the quantum algorithms
literature.

######  Definition 2.4 (Parameters of a Phase Estimation Algorithm).

For an implicit input $x\in\\{0,1\\}^{*}$, fix a finite-dimensional complex
inner product space $H$, a unit vector ${\lvert}\psi_{0}\rangle\in H$, and
sets of vectors $\Psi^{\cal A},\Psi^{\cal B}\subset H$. We further assume that
${\lvert}\psi_{0}\rangle$ is orthogonal to every vector in $\Psi^{\cal B}$.
Let $\Pi_{\cal A}$ be the orthogonal projector onto ${\cal
A}=\mathrm{span}\\{\Psi^{\cal A}\\}$, and similarly for $\Pi_{\cal B}$.

Let $U_{\cal AB}=(2\Pi_{\cal A}-I)(2\Pi_{\cal B}-I)$. The algorithm defined by
$(H,{\lvert}\psi_{0}\rangle,\Psi^{\cal A},\Psi^{\cal B})$ performs phase
estimation of $U_{\cal AB}$ on initial state ${\lvert}\psi_{0}\rangle$, to
sufficient precision that by measuring the phase register and checking if the
output is 0, we can distinguish between a _negative case_ and a _positive
case_.

######  Definition 2.5 (Negative Witness).

A _negative witness_ for $(H,{\lvert}\psi_{0}\rangle,\Psi^{\cal A},\Psi^{\cal
B})$ is a vector ${\lvert}w_{\cal A}\rangle\in{\cal A}$ such that
${\lvert}w_{\cal B}\rangle\colonequals{\lvert}\psi_{0}\rangle-{\lvert}w_{\cal
A}\rangle\in{\cal B}$.

######  Definition 2.6 (Positive Witness).

A _positive witness_ for $(H,{\lvert}\psi_{0}\rangle,\Psi^{\cal A},\Psi^{\cal
B})$ is a vector ${\lvert}w\rangle\in{\cal A}^{\bot}\cap{\cal B}^{\bot}$ such
that ${{\langle}\psi_{0}|}w\rangle\neq 0$.

Note that a negative witness exists if and only if
${\lvert}\psi_{0}\rangle\in{\cal A}+{\cal B}$, whereas a positive witness
exists if and only if ${\lvert}\psi_{0}\rangle$ has a non-zero component in
$({\cal A}+{\cal B})^{\bot}={\cal A}^{\bot}\cap{\cal B}^{\bot}$, which is if
and only if ${\lvert}\psi_{0}\rangle\not\in{\cal A}+{\cal B}$. The following
theorem describes an algorithm for distinguishing these two cases.

######  Theorem 2.7 ([JZ23]).

Fix $(H,{\lvert}\psi_{0}\rangle,\Psi^{\cal A},\Psi^{\cal B})$ as in Definition
2.4. Suppose we can generate the state ${\lvert}\psi_{0}\rangle$ in cost ${\sf
S}$, and implement $U_{\cal AB}=(2\Pi_{\cal A}-I)(2\Pi_{\cal B}-I)$ in cost
${\sf A}$.

Let $c_{+}\in[1,50]$ be some constant, and let ${\cal C}_{-}\geq 1$ be a
positive real number that may scale with $|x|$, such that we are guaranteed
that one of the following holds:

Positive Condition:

There is a positive witness ${\lvert}w\rangle$ s.t.
$\frac{|{{\langle}w|}\psi_{0}\rangle|^{2}}{\left\|{\lvert}w\rangle\right\|^{2}}\geq\frac{1}{c_{+}}$.

Negative Condition:

There is a negative witness ${\lvert}w_{\cal A}\rangle$ s.t.
$\left\|{\lvert}w_{\cal A}\rangle\right\|^{2}\leq{\cal C}_{-}$.

Then there is a quantum algorithm that distinguishes these two cases with
bounded error in time

$O\left({\sf S}+\sqrt{{\cal C}_{-}}{\sf A}\right)$

and space $O(\log\dim H+\log{\cal C}_{-})$.

The reason we assume that ${\cal A}$ and ${\cal B}$ are given by bases is that
this extra structure allows us to implement the reflections around these
spaces, which we describe shortly. For this reason, we refer to these given
bases as _working bases_.

######  Definition 2.8 (Working Basis Generation).

We say an orthonormal basis $\Psi=\\{{\lvert}b_{\ell}\rangle\\}_{\ell\in
L}\subset H_{G}$ can be generated in time $T$ if

  1. 1.

The reflection around the subspace
$\mathrm{span}\\{{\lvert}\ell\rangle:\ell\in L\\}$ of $H_{G}$ can be
implemented in time $T$.

  2. 2.

There is a map that acts as
${\lvert}\ell\rangle\mapsto{\lvert}b_{\ell}\rangle$ for all $\ell\in L$ that
can be implemented in time $T$.

######  Claim 2.9.

If $\Psi_{\cal A}$ and $\Psi_{\cal B}$ are working bases for ${\cal A}$ and
${\cal B}$, respectively, that can each be generated in time $T$, then
$U=(2\Pi_{\cal A}-I)(2\Pi_{\cal B}-I)$ can be implemented in time $T$.

###### Proof.

Run the map ${\lvert}\ell\rangle\mapsto{\lvert}b_{\ell}\rangle$ in reverse,
reflect around $\mathrm{span}\\{{\lvert}\ell\rangle:ell\in L\\}$, and then run
the map ${\lvert}\ell\rangle\mapsto{\lvert}b_{\ell}\rangle$. ∎

We end by remarking that it is enough to have a working basis for the
complement of ${\cal A}$ or ${\cal B}$.

######  Corollary 2.10.

If $\Psi$ is a working basis that can each be generated in time $T$, then
there is a basis $\Psi^{\prime}$ for $\mathrm{span}\\{\Psi\\}^{\bot}$ that can
be generated in time $T$.

###### Proof.

Suppose $\Psi=\\{{\lvert}b_{\ell}\rangle\\}_{\ell\in L}$, and
$H_{G}\equiv\mathrm{span}\\{{\lvert}\ell\rangle:\ell\in Z\\}$ where
$L\subseteq Z$. Let $U_{\Psi}$ be the given map that acts as
${\lvert}\ell\rangle\mapsto{\lvert}b_{\ell}\rangle$ for $\ell\in L$, in time
$T$. Then define
$\Psi^{\prime}=\\{{\lvert}b_{\ell}^{\prime}\rangle=U_{\Psi}{\lvert}\ell\rangle\\}_{\ell\in
Z\setminus L}$. ∎

##  3 Subspace Graphs for Multidimensional Quantum Walks

###  3.1 Subspace Graphs

Multidimensional quantum walks were introduced as such in [JZ23], although
they generalize various quantum algorithms that have appeared previously,
including [Sze04, RŠ12, Bel13, BCJ+13, IJ19]. We wish to consider very general
kinds of composition of multidimensional quantum walks, and in order to be
clear about the precise types of objects we are composing, we give a more
formal definition than has appeared previously.

######  Definition 3.1 (Subspace Graph).

A _subspace graph_ consists of a (undirected) graph $G=(V,E)$, a boundary
$B\subseteq V$, and the following subspaces of a space $H=H_{G}$:

Edge and Boundary Spaces

We assume $H$ can be decomposed into a direct sum of spaces as follows:
$H=\bigoplus_{e\in E}\Xi_{e}\oplus\bigoplus_{u\in B}\Xi_{u}$.

Edge and Boundary Subspaces

For each $e\in E\cup B$, let $\Xi_{e}^{\cal A}$ and $\Xi_{e}^{\cal B}$ be
subspaces of $\Xi_{e}$. These need not be orthogonal, and they may each be
$\\{0\\}$, all of $\Xi_{e}$, or something in between.

Vertex Spaces and Boundary Space

For each $u\in V$, let ${\cal V}_{u}\subseteq\bigoplus_{e\in E(u)}\Xi_{e}$ be
pairwise orthogonal spaces. Let ${\cal V}_{B}\subseteq\bigoplus_{u\in
B}\Xi_{u}$ be orthogonal to all ${\cal V}_{u}$.

Then we define

${\cal A}_{G}=\bigoplus_{e\in E\cup B}\Xi_{e}^{\cal A}\mbox{ and }{\cal
B}_{G}=\bigoplus_{u\in V}{\cal V}_{u}\oplus{\cal V}_{B}+\bigoplus_{e\in E\cup
B}\Xi_{e}^{\cal B}.$

We will refer to a subspace graph as simply $G$, with the associated spaces
implicit. In this work, we will always have ${\cal V}_{B}=\\{0\\}$, so we
generally omit it.

We fix some notation for talking about subspace graphs. For any $e\in E\cup
B$, we let $\Pi_{e}$, $\Pi_{e}^{\cal A}$ and $\Pi_{e}^{\cal B}$ denote
orthogonal projectors onto $\Xi_{e}$, $\Xi_{e}^{\cal A}$, and $\Xi_{e}^{\cal
B}$, respectively. For any set $F\subseteq E\cup B$, we let
$\Xi_{F}=\bigoplus_{e\in F}\Xi_{e}$, $\Xi_{F}^{\cal A}=\bigoplus_{e\in
F}\Xi_{e}^{\cal A}$, and similarly for $\Xi_{F}^{\cal B}$. We let $\Pi_{F}$,
$\Pi_{F}^{\cal A}$ and $\Pi_{F}^{\cal B}$ denote the orthogonal projectors
onto $\Xi_{F}$, $\Xi_{F}^{\cal A}$ and $\Xi_{f}^{\cal B}$, respectively.

We will allow subspace graphs to implicitly depend on some input, and
associate them with a computation. Specifically, if we fix some initial state
${\lvert}\psi_{0}\rangle\in H_{G}$, then this, along with ${\cal A}_{G}$ and
${\cal B}_{G}$, define a phase estimation algorithm (Section 2.4) that decides
if ${\lvert}\psi_{0}\rangle\in{\cal A}_{G}+{\cal B}_{G}$. With this in mind,
we say a subspace graph that depends on some input $x$, _computes a function
$f$_ (with respect to ${\lvert}\psi_{0}\rangle$, which should be clear from
context) if $f(x)=0$ if and only if ${\lvert}\psi_{0}\rangle\in{\cal
A}_{G}+{\cal B}_{G}$. We make this formal in Section 3.2.

One motivating example from which we derive intuition is the special case of a
quantum walk on a graph. We will see other examples in later sections, and our
results will mainly be based on these, but we describe how quantum walks fit
into this picture as an illustration. First, we define a special case for
${\cal V}_{u}$. While the definition of subspace graph is independent of any
weights of the graph $G$, we can always assume $G$ has associated edge weights
from which we derive extra structure.

######  Definition 3.2 (Simple Vertex).

Fix a subspace graph $G$ with associated edge weights $\\{{\sf w}_{e}\\}_{e\in
E}$. For $u\in V$, define

${\lvert}\psi_{\star}(u)\rangle\colonequals\sum_{e\in
E^{\rightarrow}(u)}\sqrt{{\sf w}_{e}}{\lvert}\rightarrow,u\rangle+\sum_{e\in
E^{\leftarrow}(u)}\sqrt{{\sf w}_{e}}{\lvert}\leftarrow,u\rangle.$

A vertex $u\in V$ is _simple_ if for all $e\in E^{\rightarrow}(u)$,
${\lvert}\rightarrow,e\rangle\in\Xi_{e}$, for all $e\in E^{\leftarrow}(u)$,
${\lvert}\leftarrow,e\rangle\in\Xi_{e}$, and if $u\in V\setminus B$ ${\cal
V}_{u}=\mathrm{span}\\{{\lvert}\psi_{\star}(u)\rangle\\};$ and if $u\in B$,
either ${\lvert}\rightarrow,u\rangle\in\Xi_{u}$ and ${\cal
V}_{u}=\mathrm{span}\\{{\lvert}\rightarrow,u\rangle+{\lvert}\psi_{\star}(u)\rangle\\}$
or ${\lvert}\leftarrow,u\rangle\in\Xi_{u}$ and ${\cal
V}_{u}=\mathrm{span}\\{{\lvert}\leftarrow,u\rangle+{\lvert}\psi_{\star}(u)\rangle\\}.$

To motivate this definition, consider the following example.

######  Example 3.3 (Quantum Walk on a Graph).

A subspace graph $G$, with associated edge weights, in which

  1. 1.

all vertices are simple,

  2. 2.

$\Xi_{E\cup B}^{\cal B}=\\{0\\}$,

  3. 3.

for all $e\in E$, $\Xi_{e}^{\cal
A}=\mathrm{span}\\{{\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle\\}$,

  4. 4.

$B=\\{s\\}\sqcup M$, where for all $u\in M$, $\Xi_{u}^{\cal A}+\Xi_{u}^{\cal
B}=\\{0\\}$,

is a _quantum walk_ on the weighted graph $G=(V,E)$. To motivate this
terminology, the phase estimation algorithm in the next section implements a
quantum walk on $G$, in the sense that it decides if $\exists t\in M$ in the
same component as $s$444This is if we use
${\lvert}\psi_{0}\rangle={\lvert}s\rangle$. More generally, we can let
$B=S\sqcup M$ and let ${\lvert}\psi_{0}\rangle=\sum_{s\in
S}\sqrt{\sigma(s)}{\lvert}s\rangle$ for _initial distribution_ $\sigma$ on
$S$..

Simple vertices are motivated by quantum walks, and related constructions, as
follows. In a random walk on a weighted graph, in order to take a step from a
vertex $u\in V$ to a neighbour, the random walker chooses an edge $e\in E(u)$
to traverse, with probability ${\sf w}_{e}/(\sum_{e^{\prime}\in E(u)}{\sf
w}_{e^{\prime}})$. This is precisely the distribution obtained by measuring
${\lvert}\psi_{\star}(u)\rangle/\left\|{\lvert}\psi_{\star}(u)\rangle\right\|$.
The states ${\lvert}\psi_{\star}(u)\rangle$ correspond to _quantum walk
states_ – alternating a reflection around these with a reflection around the
states $\\{{\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle\\}_{e\in
E}$ implements a discrete-time quantum walk, as in [Sze04, MNRS11,
Bel13].555In some previous works, it is assumed that the graph is bipartite,
and then the walk is implemented by alternating reflections around the states
${\lvert}\psi_{\star}(u)\rangle$ of the two parts of the bipartition. We are
actually doing the same thing here, we have just ensured the graph is
bipartite by inserting a vertex in the middle of each edge.

A related example is that of a _switching network_ , which, unlike quantum
walks, will actually be one of the building blocks of our results in this
paper. We first define what it means for an edge to be a switch.

######  Definition 3.4 (Switch Edge).

Fix a subspace graph $G$. We call an edge $e\in E$ a _switch_ (or _switch
edge_) if there is some value $\varphi(e)\in\\{0,1\\}$ associated with that
edge (implicitly depending on the input), such that

$\displaystyle\Xi_{e}$
$\displaystyle=\mathrm{span}\\{{\lvert}\rightarrow,e\rangle,{\lvert}\leftarrow,e\rangle\\},$
$\displaystyle\Xi_{e}^{{\cal A}}$
$\displaystyle=\mathrm{span}\\{{\lvert}\rightarrow,e\rangle-(-1)^{\varphi(e)}{\lvert}\leftarrow,e\rangle\\}\quad\mbox{and}\quad\Xi_{e}^{{\cal
B}}=\mathrm{span}\\{{\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle\\},$

and moreover, if $e\in E^{\rightarrow}(u)\cap E^{\leftarrow}(v)$, (that is,
$e=(u,v)$), then ${\cal
V}_{u}\cap\Xi_{e}=\mathrm{span}\\{{\lvert}\rightarrow,e\rangle\\}$ and ${\cal
V}_{v}\cap\Xi_{e}=\mathrm{span}\\{{\lvert}\leftarrow,e\rangle\\}$.

The idea behind a switch edge is that if $\varphi(e)=0$, $\Xi_{e}^{\cal
A}+\Xi_{e}^{\cal B}=\Xi_{e}$, and so $\Xi_{e}^{\bot}=\\{0\\}$. Recall that a
_positive witness_ is some ${\lvert}w\rangle\in{\cal A}_{G}^{\bot}\cap{\cal
B}_{G}^{\bot}$ (Definition 2.6). If $\Xi_{e}^{\bot}=\\{0\\}$, then
${\lvert}w\rangle$ can have no overlap with $\Xi_{e}$, so $e$ is essentially
blocked from use, so we say the edge is _switched off_. In switching networks,
defined shortly, the positive witness is an $st$-flow, and it is restricted to
edges in the subgraph $G(x)$ of edges that are switched on (we discuss this
more in Section 3.3 – in particular, see (4)).

Next, we define some conditions that are satisfied by switching networks, as
well as other examples considered in this paper.

######  Definition 3.5 (Canonical $st$-boundary).

We say a subspace graph $G$ has _canonical $st$-boundary_ if $B=\\{s,t\\}$,
where:

  * •

$\Xi_{s}=\mathrm{span}\\{{\lvert}s\rangle,{\lvert}\leftarrow,s\rangle\\}$,
$\Xi_{s}^{\cal
A}=\mathrm{span}\\{{\lvert}s\rangle+{\lvert}\leftarrow,s\rangle\\}$ and
$\Xi_{s}^{\cal B}=\\{0\\}$, where ${\cal V}_{s}$ only overlaps
${\lvert}\leftarrow,s\rangle$.

  * •

$\Xi_{t}=\mathrm{span}\\{{\lvert}\rightarrow,t\rangle,{\lvert}t\rangle\\}$,
$\Xi_{t}^{\cal
A}=\mathrm{span}\\{{\lvert}\rightarrow,t\rangle+{\lvert}t\rangle\\}$ and
$\Xi_{t}^{\cal B}=\\{0\\}$, where ${\cal V}_{t}$ only overlaps
${\lvert}\rightarrow,t\rangle$.

  * •

${\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle\in{\cal B}_{G}$.

Note that when $G$ has canonical $st$-boundary, we always have
${\lvert}s\rangle+{\lvert}t\rangle\in{\cal A}_{G}+{\cal B}_{G}$.

As discussed in Section 1, a switching network is actually a classical object,
but we overload the term to describe a specific kind of subspace graph. This
is justified by the fact that, evaluating such a subspace graph is equivalent
to evaluating a switching network (see the discussion in Section 3.3).

######  Definition 3.6 (Switching Network).

A _switching network_ is a subspace graph with canonical $st$-boundary in
which all edges are switches (Definition 3.4), and all vertices are simple
(Definition 3.2).

Note that if a subspace graph is a switching network, then all its spaces are
fixed by the graph structure $(V,E)$, and the associated weights. This is not
true for subspace graphs more generally, and in Section 3.5, we will see an
example of a subspace graph with other kinds of subspaces.

We discuss more properties of switching networks, including several examples,
in Section 3.3. The examples we will detail in this paper will not be
restricted to switching networks, but all, aside from some pedagogical
examples, will have canonical boundary, and we will let some of the edges be
switches.

###  3.2 Phase Estimation Algorithm

A subspace graph, as in Definition 3.1, gives rise to a phase estimation
algorithm (see Section 2.4) with spaces ${\cal A}_{G}$ and ${\cal B}_{G}$ as
in Definition 3.1 and some initial state ${\lvert}\psi_{0}\rangle\in\Xi_{B}$.
Though it is possible to consider more general states
${\lvert}\psi_{0}\rangle$, throughout this paper, we will always assume $G$
has canonical $st$-boundary, and will let

${\lvert}\psi_{0}\rangle=\frac{1}{\sqrt{2}}({\lvert}s\rangle-{\lvert}t\rangle).$
(1)

To fully specify a phase estimation algorithm, we need a pair of orthogonal
bases for ${\cal A}_{G}$ and ${\cal B}_{G}$ that are easily generated, in
order to implement their respective reflections. We therefore always assume we
have such a basis pair associated with $G$, which we call the _working bases_.
For example, if $\Xi_{e}^{\cal B}=\\{0\\}$ for all $e$, then it suffices to
have good bases for all the pairwise orthogonal spaces ${\cal V}_{v}$; and
good bases for all the pairwise orthogonal spaces $\Xi_{e}^{\cal A}$. However,
it is in our interest to put as much of $\Xi_{e}^{\cal A}+\Xi_{e}^{\cal B}$
into $\Xi_{e}^{\cal B}$ as we can manage while still maintaining a good
working basis for ${\cal B}_{G}$. That is because of how the negative witness
complexity is defined (Definition 2.5, and also Definition 3.10 below): only
the part of ${\lvert}\psi_{0}\rangle$ in ${\cal A}_{G}$ is counted in the
complexity. We will see this in action in switching networks, in Section 3.3.

To facilitate our later constructions, we will make the following extra
assumptions on the working bases.

######  Definition 3.7 (Composable Bases).

Fix a subspace graph with canonical $st$-boundary, and some ${\sf
r}\in\mathbb{R}_{>0}$. We say a pair of working bases $\Psi_{\cal A}$ and
$\Psi_{\cal B}$ (see Definition 2.8) for ${\cal A}_{G}$ and ${\cal B}_{G}$ are
$st$-composable, with scaling factor ${\sf r}$, if they satisfy the following
assumptions:

  1. 1.

$\Psi_{{\cal A}}=\bigcup_{e\in E\cup B}\Psi_{{\cal A}}(e)$, where $\Psi_{{\cal
A}}(e)$ is an orthonormal basis for $\Xi_{e}^{\cal A}$;

  2. 2.

$\Psi_{\cal B}=\Psi_{\cal B}^{-}\cup\bigcup_{e\in E\cup B}\Psi_{{\cal B}}(e)$,
for some $\Psi_{\cal B}^{-}$, where $\Psi_{{\cal B}}(e)$ is an orthonormal
basis for $\Xi_{e}^{\cal B}$;

  3. 3.

${\lvert}b_{0}\rangle\in\Psi_{\cal B}^{-}$ satisfies
${\lvert}b_{0}\rangle=\frac{1}{\sqrt{2}}({\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle)$;

  4. 4.

${\lvert}b_{1}\rangle\in\Psi_{\cal B}^{-}$ satisfies
${\lvert}b_{1}\rangle=\frac{{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle+\sqrt{{\sf
r}}{\lvert}\bar{b}_{1}\rangle}{\sqrt{2+{\sf r}}}$ for some unit vector
${\lvert}\bar{b}_{1}\rangle$ that is orthogonal to
${\lvert}\leftarrow,s\rangle$ and ${\lvert}\rightarrow,t\rangle$;

  5. 5.

$\Psi_{\cal B}\setminus\\{{\lvert}b_{0}\rangle,{\lvert}b_{1}\rangle\\}$ is
orthogonal to ${\lvert}\leftarrow,s\rangle$ and
${\lvert}\rightarrow,t\rangle$.

We note that generally we will be able to choose the scaling factor ${\sf r}$
by applying a linear map to $H_{G}$ that scales $\Xi_{E}$ relative to
$\Xi_{B}$. See also the remark after Theorem 3.12.

Now we can define the special form of subspace graph that will apply to all
subspace graphs studied in this paper (aside from some examples mentioned
informally):

######  Definition 3.8.

We say a subspace graph $G$ is _$st$ -composable_ if:

  1. 1.

$G$ has canonical $st$-boundary (Definition 3.5);

  2. 2.

$G$ is equipped with composable working bases (Definition 3.7);

  3. 3.

for each $e\in E\setminus\overline{E}$, $\Xi_{e}^{\cal B}=\\{0\\}$, where
$\overline{E}$ is the set of edges that are switches.

To analyze a phase estimation algorithm, we need to exhibit positive and
negative witnesses. A positive witness for a phase estimation algorithm
(Definition 2.6) is a vector ${\lvert}w\rangle\in{\cal A}_{G}^{\bot}\cap{\cal
B}^{\bot}_{G}$ such that ${{\langle}\psi_{0}|}w\rangle\neq 0$. By scaling
${\lvert}w\rangle$, we can make ${{\langle}\psi_{0}|}w\rangle\neq 0$ take any
scalar value, without impacting the complexity $c_{+}$ from Theorem 2.7. This
motivates the following definition.

######  Definition 3.9 (Positive Witness for a Graph).

We say ${\lvert}w\rangle\in{\cal A}_{G}^{\bot}\cap{\cal B}^{\bot}_{G}$ is a
positive witness for $G$ if it can be expressed as

${\lvert}w\rangle={\lvert}s\rangle-{\lvert}\leftarrow,s\rangle+\Pi_{E}{\lvert}w\rangle+{\lvert}\rightarrow,t\rangle-{\lvert}t\rangle.$

We let $W_{+}(G)$ be an upper bound (over some implicit input) on the minimum
$\left\|{\lvert}w\rangle\right\|^{2}$ of any positive witness for $G$. We call
${\lvert}\hat{w}\rangle\colonequals\Pi_{E}{\lvert}w\rangle$ the _cropped
witness_ , and we let $\hat{W}_{+}(G)=W_{+}(G)-4$ be an upper bound on the
minimum $\left\|{\lvert}\hat{w}\rangle\right\|^{2}$.

To parse the definition above, note that if
${{\langle}\psi_{0}|}w\rangle=\sqrt{2}$, then we can always express
${\lvert}w\rangle$ as

${\lvert}w\rangle=\sqrt{2}{\lvert}\psi_{0}\rangle+(I-{\lvert}\psi_{0}\rangle{\langle}\psi_{0}\rvert){\lvert}w\rangle={\lvert}s\rangle-{\lvert}t\rangle+(I-{\lvert}\psi_{0}\rangle{\langle}\psi_{0}\rvert){\lvert}w\rangle,$

but more than that, ${\lvert}w\rangle$ is orthogonal to
${\lvert}s\rangle+{\lvert}t\rangle\in{\cal A}+{\cal B}$, so
$(I-{\lvert}\psi_{0}\rangle{\langle}\psi_{0}\rvert){\lvert}w\rangle$ is
orthogonal to both ${\lvert}s\rangle-{\lvert}t\rangle$ and
${\lvert}s\rangle+{\lvert}t\rangle$, so we have:

${\lvert}w\rangle={\lvert}s\rangle-{\lvert}t\rangle+(I-{\lvert}s\rangle{\langle}s\rvert-{\lvert}t\rangle{\langle}t\rvert){\lvert}w\rangle={\lvert}s\rangle-{\lvert}\leftarrow,s\rangle-{\lvert}t\rangle+{\lvert}\rightarrow,t\rangle+(I-\Pi_{B}){\lvert}w\rangle,$

since ${\lvert}w\rangle$ must be orthogonal to
${\lvert}s\rangle+{\lvert}\leftarrow,s\rangle$ and
${\lvert}t\rangle+{\lvert}\rightarrow,t\rangle$. We consider
${\lvert}w\rangle$ with its boundary $\Pi_{B}{\lvert}w\rangle$ removed – which
we call a cropped witness – because in Section 4, when we compose subspace
graphs, we will crop off their boundary spaces to save additive constants in
the witness sizes, which become relevant when we have very deep recursive
structures. Thus, we similarly define:

######  Definition 3.10 (Negative Witness for a Graph).

We say ${\lvert}w_{\cal A}\rangle\in{\cal A}_{G}$ is a negative witness for
$G$ if ${\lvert}w_{\cal A}\rangle-{\lvert}s\rangle+{\lvert}t\rangle\in{\cal
B}_{G}$. We define the corresponding _cropped negative witness_ by
${\lvert}\hat{w}_{\cal A}\rangle=\Pi_{E}{\lvert}w_{\cal A}\rangle$.

For the above, recall that a negative witness for a phase estimation algorithm
is a vector ${\lvert}w_{\cal A}\rangle\in{\cal A}$ such that ${\lvert}w_{\cal
B}\rangle\colonequals{\lvert}\psi_{0}\rangle-{\lvert}w_{\cal A}\rangle\in{\cal
B}$. We have slightly modified the definition, by replacing
${\lvert}\psi_{0}\rangle=\frac{1}{\sqrt{2}}({\lvert}s\rangle-{\lvert}t\rangle)$
with ${\lvert}s\rangle-{\lvert}t\rangle$, in order to save factors of
$\sqrt{2}$ everywhere, but this changes very little. We will use the following
later in the paper.

######  Lemma 3.11.

Assume $G$ has canonical $st$-boundary. Then ${\lvert}w_{\cal
A}\rangle\in{\cal A}_{G}$ is a negative witness for $G$ if and only if
${\lvert}\hat{w}_{\cal
A}\rangle+{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle\in{\cal
B}_{G}$.

###### Proof.

${\lvert}w_{\cal A}\rangle\in{\cal A}_{G}$ is a negative witness for $G$ if
and only if ${\lvert}w_{\cal
A}\rangle={\lvert}s\rangle-{\lvert}t\rangle+{\lvert}w_{\cal B}\rangle$ for
some ${\lvert}w_{\cal B}\rangle\in{\cal B}_{G}$. Since the only vectors in
${\cal A}_{G}$ that overlap the boundary $\Xi_{B}$ are $\Xi_{B}^{\cal
A}=\mathrm{span}\\{{\lvert}s\rangle+{\lvert}\leftarrow,s\rangle,{\lvert}t\rangle+{\lvert}\rightarrow,t\rangle\\}$,
it must be the case that

${\lvert}w_{\cal
A}\rangle={\lvert}s\rangle+{\lvert}\leftarrow,s\rangle-{\lvert}t\rangle-{\lvert}\rightarrow,t\rangle+\underbrace{\Pi_{E}{\lvert}w_{\cal
A}\rangle}_{={\lvert}\hat{w}_{\cal A}\rangle}.$

Thus, ${\lvert}w_{\cal A}\rangle$ is a negative witness if and only if

$\displaystyle{\lvert}w_{\cal
A}\rangle-{\lvert}s\rangle+{\lvert}t\rangle\in{\cal B}_{G}$
$\displaystyle\Leftrightarrow\;\;$ $\displaystyle{\lvert}\hat{w}_{\cal
A}\rangle+{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle\in{\cal
B}_{G}.\qed$

In the next section, we describe what positive and negative witnesses look
like for switching networks, and compare them with the witnesses for quantum
walks on a graph (see Example 3.3).

Finally, we can define the complexity of a subspace graph by:

${\cal C}(G)\colonequals\sqrt{{W}_{+}(G){W}_{-}(G)}.$

In the case of subspaces graphs with canonical boundary, where we have defined
cropped witnesses, we will often use

$\hat{\cal C}(G)\colonequals\sqrt{\hat{W}_{+}(G)\hat{W}_{-}(G)},$

which differs from ${\cal C}(G)$ by additive constants. Then it follows from
Theorem 2.7 and Claim 2.9 that:

######  Theorem 3.12.

Let $G$ be a subspace graph that computes
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ with respect to
${\lvert}\psi_{0}\rangle$, with working bases that can be generated in time
$T$, and such that $\hat{W}_{+}(G)=O(1)$. Then there exists a quantum
algorithm that decides $f$ in time complexity
${O}\left(T\sqrt{\hat{W}_{-}(G)}\right)$ and space $O(\log\dim
H_{G}+\log\hat{W}_{-}(G))$.

Given any subspace graph $G$, we can apply the linear map

$\Pi_{B}+\frac{1}{\hat{W}_{+}(G)}\Pi_{E}$

to $H_{G}$ to get a new subspace graph $G^{\prime}$, which will still have
canonical boundary if $G$ did, and such that

$\hat{W}_{+}(G^{\prime})=1\quad\mbox{and}\quad\hat{W}_{-}(G^{\prime})=\hat{W}_{+}(G)\hat{W}_{-}(G).$

This justifies thinking of $\hat{\cal C}(G)$ as a complexity. Such a scaling
preserves the basis properties in Definition 3.7, and simply scales ${\sf r}$.
We can see this formally in Corollary 4.2.

###  3.3 Example: Switching Networks

We now discuss switching networks (Definition 3.6) in more detail, and give
several examples. In the classical model of switching networks, a switching
network is a graph with a variable $\varphi(e)$ associated with each edge $e$,
and two terminals $s,t\in V$. A switching network computes a function
$f:\\{0,1\\}^{E}\rightarrow\\{0,1\\}$ if for any $x\in\\{0,1\\}^{E}$, $f(x)=1$
if and only if $s$ and $t$ are connected in $G(x)$, the subgraph consisting
only of edges $e$ such that $x_{e}=1$ if $\varphi(e)$ is a positive literal,
and $x_{e}=0$ otherwise – that is, edges labelled by literals that are true
when the variables are set according to $x$. Here, we let “switching network”
refer to a special kind of subspace graph, but this subspace graph implements
the switching network, in the sense that the algorithm referred to in Theorem
3.12 decides if $s$ and $t$ are connected in $G(x)$.

We start by discussing some properties of switching networks. A switching
network always has:

${\cal
A}_{G}=\mathrm{span}\left\\{{\lvert}a_{s}\rangle\colonequals\frac{1}{\sqrt{2}}({\lvert}s\rangle+{\lvert}\leftarrow,s\rangle),{\lvert}a_{t}\rangle\colonequals\frac{1}{\sqrt{2}}({\lvert}t\rangle+{\lvert}\rightarrow,t\rangle)\right\\}\\\
\cup\left\\{{\lvert}a_{e}\rangle\colonequals\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle-(-1)^{\varphi(e)}{\lvert}\leftarrow,e\rangle):e\in
E\right\\},$ (2)

so there is a natural choice of working basis $\Psi_{\cal A}$, and we
immediately get the following:

######  Lemma 3.13.

If $G$ is a switching network and $\Psi_{\cal A}$ is the basis in (3), then
$\Psi_{\cal A}$ satisfies the conditions of Definition 3.7, and can be
generated in one query to the unitary
${\lvert}e\rangle\mapsto(-1)^{\varphi(e)}{\lvert}e\rangle$ and $O(1)$
additional operations.

Turning to ${\cal B}_{G}$, a switching network always has:

${\cal B}_{G}=\mathrm{span}\\{{\lvert}\psi_{\star}(u)\rangle:u\in
V\setminus\\{s,t\\}\\}\cup\\{{\lvert}\leftarrow,s\rangle+{\lvert}\psi_{\star}(s)\rangle,{\lvert}\rightarrow,t\rangle+{\lvert}\psi_{\star}(t)\rangle\\}\\\
+\mathrm{span}\left\\{\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle):e\in
E\right\\}.$ (3)

The working basis for ${\cal B}_{G}$ is less obvious, since the first and
second space are not orthogonal, but one choice is given by the following,
which we state for intuition (the proof is a simple exercise).

######  Lemma 3.14.

If $G$ is a switching network,

$\Psi_{\cal B}=\Psi_{\cal
B}^{-}\cup\left\\{{\lvert}b_{e}\rangle\colonequals\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle):e\in
E\right\\}$

is an orthonormal basis for ${\cal B}_{G}$ whenever $\Psi_{\cal B}^{-}$ is an
orthonormal basis for

${\cal B}^{-}=\mathrm{span}\\{{\lvert}\psi^{-}_{\star}(u)\rangle:u\in
V\setminus\\{s,t\\}\\}\cup\\{{\lvert}\leftarrow,s\rangle+{\lvert}\psi^{-}_{\star}(s)\rangle,{\lvert}\rightarrow,t\rangle+{\lvert}\psi^{-}_{\star}(t)\rangle\\},$

where

${\lvert}\psi_{\star}^{-}(u)\rangle=\sum_{e\in
E^{\rightarrow}(u)}\frac{\sqrt{{\sf
w}_{e}}}{2}({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)+\sum_{e\in
E^{\leftarrow}(u)}\frac{\sqrt{{\sf
w}_{e}}}{2}({\lvert}\leftarrow,e\rangle-{\lvert}\rightarrow,e\rangle).$

For intuition, the space $\mathrm{\cal B}^{-}$ is the _cut space_ of $G$,
which is the span of all states that are (correctly weighted) superpositions
of “edges” – where an edge is represented by
${\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle$ – that for a cut
set (their removal leaves $G$ disconnected).

We give some intuition on the positive and negative witnesses of a switching
network, which can also, to some extent, be used for intuition about the
positive and negative witnesses for the more general subspace graphs
considered in this paper. One can show that the orthogonal complement of
${\cal B}_{G}$ is the span of all unit $st$-flows (Definition 2.1) of $G$, by
which we mean, precisely, all states of the form

${\lvert}w\rangle={\lvert}s\rangle-{\lvert}\leftarrow,s\rangle+\underbrace{\sum_{e\in
E}\frac{\theta(e)}{\sqrt{{\sf
w}_{e}}}({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)}_{{\lvert}\hat{w}\rangle}+{\lvert}\rightarrow,t\rangle-{\lvert}t\rangle,$
(4)

where $\theta$ is a unit $st$-flow. For every $e\in E$ such that
$\varphi(e)=0$, we add
${\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle$ to ${\cal
A}_{G}+{\cal B}_{G}$, which adds the constraint on ${\lvert}w\rangle\in{\cal
A}_{G}^{\bot}\cap{\cal B}_{G}^{\bot}$ that $\theta(e)=0$. Thus, $\theta$ must
be a unit flow on the graph $G(x)$.

A negative witness exists if and only if there is no unit $st$-flow on $G(x)$,
meaning $s$ and $t$ are not connected. In that case, there is always an
$st$-cut-set of edges missing from $G(x)$, $F$. It is a simple exercise to
show that

${\lvert}w_{\cal
A}\rangle={\lvert}s\rangle+{\lvert}\leftarrow,s\rangle+\sum_{e\in F}\sqrt{{\sf
w}_{e}}({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)-{\lvert}\rightarrow,t\rangle-{\lvert}t\rangle$

is a cropped negative witness. However, not all witnesses have this form –
superpositions of cuts are also negative witnesses. Ref. [JJKP18] gives a
tight analysis of negative witness for switching networks.

We briefly remark here on the difference between switching networks and
quantum walks. In a quantum walk, the positive witnesses are also of the form
in (4), except that they are not restricted to a subgraph $G(x)$, but rather,
can be on all of $G$. Negative witnesses for quantum walks are somewhat
different, although they are also derived from $s$-$M$-cuts; they instead
involve summing over all edges in the component containing $s$, which should
not be connected to $M$ in the negative case. This is because in switching
networks, ${\cal B}_{G}$ contains more, since $\Xi_{E}^{\cal B}$ is non-
trivial, which makes finding a basis for ${\cal B}_{G}$ more difficult, but
makes negative witnesses smaller.

Finally, we give two examples of switching networks – for computing the OR of
$d$ bits (Section 3.3.1) and the AND of $d$ bits (Section 3.3.2). These
examples will also be important building blocks for our later results.
Switching networks for Boolean formulas date back to work of Shannon [Sha38,
Sha49], and their analysis as subspace graphs was already implicit in the span
program constructions of [JK17]. While [JK17] also analyzes the time
complexity of evaluating switching networks, the reflection around ${\cal
B}_{G}$ is done via a quantum walk on $G$, which results in a dependence on
the relaxation time of $G$. In our examples, we improve on this by giving an
orthonormal basis for ${\cal B}_{G}$ that can be used to reflect around it
directly. Such a basis that is also efficient to generate might not be
available for arbitrary switching networks, but in the case of series-parallel
graphs, which correspond exactly to switching networks for Boolean formulas,
our work implies that a good basis exists.

####  3.3.1 Switching Network for OR

In this section, we describe a switching network (Definition 3.6) that
computes the OR of $d$ Boolean variables. This serves as a simple example, and
will also be a building block in our divide-and-conquer application in Section
4.3. Formally, we prove the following.

######  Lemma 3.15.

For any $d\geq 1$, and positive weights $\\{{\sf w}_{i}\\}_{i\in[d]}$, there
is a switching network $G_{\textsc{or},d}$ that computes
$\bigvee_{i=1}^{d}\varphi(e_{i})$ with $\dim H_{G_{\textsc{or},d}}=2d+4$ such
that:

  1. 1.

$G_{\textsc{or},d}$ has $st$-composable working bases, with scaling factor
${\sf r}=2\sum_{i=1}^{d}{\sf w}_{i}$, that can be generated in $O(\log d)$
time, assuming the state proportional to $\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}i\rangle$ can be generated in time $O(\log d)$;

  2. 2.

if $\varphi(e_{i})=1$ for some $i\in[d]$, $G_{\textsc{or},d}$ has cropped
positive witness ${\lvert}\hat{w}\rangle=\frac{1}{\sqrt{{\sf
w}_{i}}}({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle)$; and

  3. 3.

if $\varphi(e_{i})=0$ for all $i\in[d]$, $G_{\textsc{or},d}$ has cropped
negative witness ${\lvert}\hat{w}_{\cal A}\rangle=\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle)$.

$\vdots$$s$$e_{1}$$e_{2}$$e_{d}$$t$ Figure 1: The graph $G_{\textsc{or}}$. The
dashed lines represent dangling boundary “edges”.

We remark that if ${\sf w}_{i}=1$ for all $i$, then Lemma 3.15 implies
$\hat{W}_{+}(G_{\textsc{or},d})=2$ and $\hat{W}_{-}(G_{\textsc{or},d})=2d$, so
by Theorem 3.12, there is a quantum algorithm for evaluating $d$-bit OR with
time complexity $\widetilde{O}(\sqrt{d})$, which is optimal. This is a good
sanity check, but we will mostly be interested in this construction as a
building block, rather than in its own right.

Let $G=G_{\textsc{or},d}$ be defined, as shown in Figure 1 by:

$V=\\{s,t\\}\mbox{ and }E=\\{e_{i}:i\in[d]\\}$

where each $e_{i}$ has endpoints $s$ and $t$, so $E(s)=E^{\rightarrow}(s)=E$
and $E(t)=E^{\leftarrow}(t)=E$. Since $G$ is a switching network, it has
boundary $B=V=\\{s,t\\}.$ We will let the graph be weighted, with weights
${\sf w}_{e_{i}}={\sf w}_{i}$. The only reason to let these vary in $i$ is for
later when we replace an edge with a gadget by composition, but for the sake
of intuition, the reader may wish to imagine ${\sf w}_{i}=1$ for all $i$.
Since $G$ is a switching network, every edge is a switch, which fixes the
following spaces (we simplify notation by using $i$ to label the edge
$e_{i}$):

$\displaystyle\forall i\in[d],\;$
$\displaystyle\Xi_{e_{i}}=\mathrm{span}\\{{\lvert}\rightarrow,i\rangle,{\lvert}\leftarrow,i\rangle\\},$
$\displaystyle\Xi_{e_{i}}^{\cal
A}=\mathrm{span}\\{{\lvert}\rightarrow,i\rangle-(-1)^{\varphi(e_{i})}{\lvert}\leftarrow,i\rangle\\},\mbox{
and }\Xi_{e_{i}}^{\cal
B}=\mathrm{span}\\{{\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle\\}.$

Furthermore, as a switching network has canonical $st$-boundary, the following
spaces are fixed:

$\displaystyle\Xi_{s}=\mathrm{span}\\{{\lvert}s\rangle,{\lvert}\leftarrow,s\rangle\\},\quad\Xi_{s}^{\cal
A}=\mathrm{span}\\{{\lvert}s\rangle+{\lvert}\leftarrow,s\rangle\\},\mbox{ and
}\Xi_{s}^{\cal B}=\\{0\\}$
$\displaystyle\Xi_{t}=\mathrm{span}\\{{\lvert}\rightarrow,t\rangle,{\lvert}t\rangle\\},\quad\Xi_{t}^{\cal
A}=\mathrm{span}\\{{\lvert}\rightarrow,t\rangle+{\lvert}t\rangle\\},\mbox{ and
}\Xi_{t}^{\cal B}=\\{0\\}.$

Finally, since all vertices are simple, the following spaces are fixed:

$\displaystyle{\cal
V}_{s}=\mathrm{span}\Bigg{\\{}{\lvert}\leftarrow,s\rangle+\underbrace{\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}\rightarrow,i\rangle}_{{\lvert}\psi_{\star}(s)\rangle}\Bigg{\\}}\mbox{
and }{\cal V}_{t}=\mathrm{span}\Bigg{\\{}\underbrace{\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}\leftarrow,i\rangle}_{{\lvert}\psi_{\star}(t)\rangle}+{\lvert}\rightarrow,t\rangle\Bigg{\\}}.$

Then we have:

$\begin{split}{\cal A}_{G}&=\bigoplus_{e\in E\cup B}\Xi_{e}^{\cal
A}=\mathrm{span}\\{{\lvert}\rightarrow,i\rangle-(-1)^{\varphi(e_{i})}{\lvert}\leftarrow,i\rangle:i\in[d]\\}\cup\\{{\lvert}s\rangle+{\lvert}\leftarrow,s\rangle,{\lvert}t\rangle+{\lvert}\rightarrow,t\rangle\\}\\\
\mbox{and }{\cal B}_{G}&={\cal V}_{s}\oplus{\cal V}_{t}+\bigoplus_{e\in
E}\Xi_{e}^{\cal B}={\cal V}_{s}\oplus{\cal
V}_{t}+\mathrm{span}\\{{\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle:i\in[d]\\}.\end{split}$
(5)

By Lemma 3.13, since we assume we can query the values $\varphi(e)$ in unit
cost, there is a working basis for $\Psi_{\cal A}$ satisfying the conditions
of Definition 3.7 that can be generated in unit time. To complete the proof of
the the first item of Lemma 3.15, we prove the following.

######  Lemma 3.16.

Let

$\Psi_{\cal
B}=\left\\{{\lvert}b_{0}\rangle=\frac{1}{\sqrt{2}}({\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle),{\lvert}b_{1}\rangle=\frac{{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle+\sqrt{{\sf
r}}{\lvert}\bar{b}_{1}\rangle}{\sqrt{2+{\sf r}}}\right\\}\\\
\cup\left\\{{\lvert}b_{e_{i}}\rangle=\frac{1}{\sqrt{2}}({\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle):i\in[d]\right\\},$

where

${\sf r}=2\sum_{i=1}^{d}{\sf w}_{i}\quad\mbox{ and
}\quad{\lvert}\bar{b}_{1}\rangle=\frac{1}{\sqrt{{\sf
r}}}\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle).$

Then $\Psi_{\cal B}$ is an orthonormal basis for ${\cal B}_{G}$, and it
satisfies all the conditions of an $st$-composable basis in Definition 3.7.
Furthermore, as long as we can generate the state proportional to
$\sum_{i=1}^{d}\sqrt{{\sf w}_{i}}{\lvert}i\rangle$ in time $O(\log d)$,
$\Psi_{\cal B}$ can be generated in time $O(\log d)$.

###### Proof.

Note that:

${\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle=\underbrace{{\lvert}\leftarrow,s\rangle+\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}\rightarrow,i\rangle}_{\in{\cal
V}_{s}}+\underbrace{\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}\leftarrow,i\rangle+{\lvert}\rightarrow,t\rangle}_{\in{\cal
V}_{t}}-\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}\underbrace{({\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle)}_{\in\Xi_{e}^{\cal
B}}$

and

${\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle+\sqrt{{\sf
r}}{\lvert}\bar{b}_{1}\rangle=\underbrace{{\lvert}\leftarrow,s\rangle+\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}\rightarrow,i\rangle}_{\in{\cal
V}_{s}}-\underbrace{\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}\leftarrow,i\rangle+{\lvert}\rightarrow,t\rangle}_{\in{\cal
V}_{t}}.$

From there, it is simple to check that $\Psi_{\cal B}\subset{\cal B}_{G}$. It
is also simple to see that $\Xi_{e}^{\cal B}\subset\mathrm{span}\Psi_{\cal B}$
for all $e$. Thus, we check ${\cal V}_{s}$ and ${\cal V}_{t}$. We have:

$\displaystyle{\lvert}\leftarrow,s\rangle+\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}\rightarrow,i\rangle={}$
$\displaystyle\frac{1}{2}\left({\lvert}\leftarrow,s\rangle+\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}\left({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle\right)-{\lvert}\rightarrow,t\rangle\right)$
$\displaystyle\qquad+\frac{1}{2}\left({\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle\right)+\frac{1}{2}\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}({\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle),$

showing that ${\cal V}_{s}\subset\mathrm{span}\Psi_{\cal B}$. A similar proof
shows that ${\cal V}_{t}\subset\mathrm{span}\Psi_{\cal B}$.

It is clear by inspection that $\Psi_{\cal B}$ satisfies the properties of
Definition 3.7, so to complete the proof, it is a simple exercise to observe
that the basis can be generated in $O(\log d)$ time. ∎

To prove the second item of Lemma 3.15, we show the following.

######  Lemma 3.17.

If $\varphi(e_{i})=1$ for some $i$, then the following is a positive witness
for $G$ (Definition 3.9):

${\lvert}w\rangle={\lvert}s\rangle-{\lvert}\leftarrow,s\rangle+\underbrace{\frac{1}{\sqrt{{\sf
w}_{i}}}\left({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle\right)}_{{\lvert}\hat{w}\rangle}+{\lvert}\rightarrow,t\rangle-{\lvert}t\rangle.$

###### Proof.

One can check that ${\lvert}w\rangle\in{\cal A}_{G}^{\bot}\cap{\cal
B}_{G}^{\bot}$, by verifying that it is orthogonal to each of the spaces in
(5). For orthogonality with

$\Xi_{e_{i}}^{\cal
A}=\mathrm{span}\\{{\lvert}\rightarrow,i\rangle-(-1)^{\varphi(i)}{\lvert}\leftarrow,i\rangle\\},$

we relied on the fact that $\varphi(i)=1$. Otherwise, we would have
$\Xi_{e_{i}}^{\cal A}+\Xi_{e_{i}}^{\cal B}=\Xi_{e_{i}}$, and a positive
witness must be orthogonal to $\Xi_{e}$, so the edge $e$ is effectively
blocked. ∎

Finally, to prove the third item of Lemma 3.15, we show the following.

######  Lemma 3.18.

If $\varphi(e_{i})=0$ for all $i$, then the following is a negative witness
for $G$ (Definition 3.10):

$\displaystyle{\lvert}w_{\cal A}\rangle$
$\displaystyle={\lvert}s\rangle+{\lvert}\leftarrow,s\rangle+\underbrace{\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}\left({\lvert}\rightarrow,i\rangle-(-1)^{\varphi(i)}{\lvert}\leftarrow,i\rangle\right)}_{{\lvert}\hat{w}_{\cal
A}\rangle}-{\lvert}\rightarrow,t\rangle-{\lvert}t\rangle.$

###### Proof.

Since $\varphi(i)=0$ for all $i\in[d]$, we have:

${\lvert}s\rangle-{\lvert}t\rangle=\underbrace{{\lvert}s\rangle+{\lvert}\leftarrow,s\rangle}_{\in\Xi_{s}^{\cal
A}}-\Bigg{(}\underbrace{{\lvert}\leftarrow,s\rangle+\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}\rightarrow,i\rangle}_{\in{\cal V}_{s}\subset{\cal
B}}\Bigg{)}+\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}\underbrace{({\lvert}\rightarrow,i\rangle-(-1)^{\varphi(i)}{\lvert}\leftarrow,i\rangle)}_{\in\Xi_{e_{i}}^{\cal
A}}\\\ +\Bigg{(}\underbrace{\sum_{i=1}^{d}\sqrt{{\sf
w}_{i}}{\lvert}\leftarrow,i\rangle+{\lvert}\rightarrow,t\rangle}_{\in{\cal
V}_{t}\subset{\cal
B}}\Bigg{)}-(\underbrace{{\lvert}\rightarrow,t\rangle+{\lvert}t\rangle}_{\in\Xi_{t}^{\cal
A}}),$

implying that ${\lvert}w_{\cal A}\rangle$ is a negative witness. Note that
this crucially relies on $\varphi(e_{i})=0$ for all $i$, otherwise the above
expression fails to hold. ∎

####  3.3.2 Switching Network for AND

In this section, we describe a switching network (Definition 3.6) that
computes the AND of $d$ Boolean variables.

######  Lemma 3.19.

For any $d\geq 1$, and positive weights $\\{{\sf w}_{i}\\}_{i\in d}$, there is
a switching network $G_{\textsc{and},d}$ that computes
$\bigwedge_{i=1}^{d}\varphi(e_{i})$ with $\dim H_{G_{\textsc{and},d}}=2d+4$
such that:

  1. 1.

$G_{\textsc{and},d}$ has $st$-composable working bases, with scaling factor
${\sf r}=2/\sum_{i=1}^{d}(1/{\sf w}_{i})$, that can be generated in $O(\log
d)$ time, assuming the state proportional to
$\sum_{i=1}^{d}\frac{1}{\sqrt{{\sf w}_{i}}}{\lvert}i\rangle$ can be generated
in time $O(\log d)$;

  2. 2.

if $\varphi(e_{i})=1$ for all $i\in[d]$, $G_{\textsc{and},d}$ has cropped
positive witness ${\lvert}\hat{w}\rangle=\sum_{i=1}^{d}\frac{1}{\sqrt{{\sf
w}_{i}}}({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle)$; and

  3. 3.

if $\varphi(e_{i})=0$ for some $i\in[d]$, $G_{\textsc{and},d}$ has cropped
negative witness ${\lvert}\hat{w}_{\cal A}\rangle=\sqrt{{\sf
w}_{i}}({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle)$.

As with the OR switching network in Section 3.3.1, a corollary of this lemma
is that there is a quantum algorithm for evaluating AND in optimal time
$\widetilde{O}(\sqrt{d})$.

$\dots$$u_{0}$$e_{1}$$u_{1}$$e_{2}$$u_{2}$$u_{d}$ Figure 2: The graph
$G_{\textsc{and}}$. The dashed lines represent dangling boundary “edges”.

Let $G=G_{\textsc{and},d}$ be the graph in Figure 2, defined by

$V=\\{s=u_{0},u_{1},\dots,u_{d}=t\\}\mbox{ and
}E=\\{e_{i}=(u_{i-1},u_{i}):i\in[d]\\},$

so $E(s)=E^{\rightarrow}(s)=\\{e_{1}\\}$,
$E(t)=E^{\leftarrow}(t)=\\{e_{d}\\}$, and for all $i\in[d-1]$,
$E^{\leftarrow}(u_{i})=\\{e_{i}\\}$ and $E^{\rightarrow}(u_{i})\\{e_{i+1}\\}$.
Since $G$ is a switching network, it has boundary $B=\\{s,t\\}$. We will let
the graph be weighted, with weights ${\sf w}_{e_{i}}={\sf w}_{i}$. Since $G$
is a switching network: every edge is a switch, which fixes $\Xi_{e_{i}}$,
$\Xi_{e_{i}}^{\cal A}$ and $\Xi_{e_{i}}^{\cal B}$ for all $i\in[d]$; $G$ has
canonical $st$-boundary, which fixes $\Xi_{s}$, $\Xi_{s}^{\cal A}$,
$\Xi_{s}^{\cal B}$, $\Xi_{t}$, $\Xi_{t}^{\cal A}$, and $\Xi_{t}^{\cal B}$; and
every vertex is simple, which fixes the spaces ${\cal V}_{u_{i}}$ for
$i\in\\{0,\dots,d\\}$. In particular, letting ${\sf w}_{0}={\sf w}_{d+1}=1$,
$s=0$, $t=d+1$, and $i\in[d]$ label $e_{i}$, we must have:

$\displaystyle\forall i\in\\{0,\dots,d\\},\;$ $\displaystyle{\cal
V}_{u_{i}}=\mathrm{span}\left\\{\sqrt{{\sf
w}_{i}}{\lvert}\leftarrow,i\rangle+\sqrt{{\sf
w}_{i+1}}{\lvert}\rightarrow,i+1\rangle\right\\}.$

This fully defines

${\cal A}_{G}=\bigoplus_{e\in E\cup B}\Xi_{e}^{\cal A}\quad\mbox{ and
}\quad{\cal B}_{G}=\bigoplus_{i=0}^{d}{\cal V}_{u_{i}}+\bigoplus_{e\in
E}\Xi_{e}^{\cal B}.$

By Lemma 3.13, since we assume we can query the values $\varphi(e)$ in unit
cost, there is a working basis for $\Psi_{\cal A}$ satisfying the conditions
of Definition 3.7 that can be generated in unit time. To complete the proof of
the the first item of Lemma 3.19, we prove the following.

######  Lemma 3.20.

Let ${\lvert}b_{2}\rangle,\dots,{\lvert}b_{d}\rangle$ be an orthonormal basis
for

$\mathrm{span}\\{{\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle\\}\cap\mathrm{span}\left\\{{\lvert}\bar{b}_{1}\rangle=\frac{\sum_{i=1}^{d}\frac{1}{\sqrt{{\sf
w}_{i}}}({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle)}{\sqrt{\sum_{i=1}^{d}\frac{2}{{\sf
w}_{i}}}}\right\\}^{\bot}.$

Let

$\Psi_{\cal
B}^{-}=\left\\{{\lvert}b_{0}\rangle=\frac{1}{\sqrt{2}}({\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle),{\lvert}b_{1}\rangle=\frac{{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle+\sqrt{{\sf
r}}{\lvert}\bar{b}_{1}\rangle}{\sqrt{2+{\sf r}}}\right\\}\\\
\cup\left\\{{\lvert}b_{2}\rangle,\dots,{\lvert}b_{d}\rangle\right\\}.$

Then

$\Psi_{\cal B}=\Psi_{\cal
B}^{-}\cup\left\\{{\lvert}b_{e_{i}}\rangle=\frac{1}{\sqrt{2}}({\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle):i\in[d]\right\\}$

is an orthonormal basis for ${\cal B}_{G}$ when ${\sf
r}=2/{\sum_{i=1}^{d}\frac{1}{{\sf w}_{i}}}$, and it satisfies all the
conditions of an $st$-composable basis in Definition 3.7. Furthermore, as long
as we can generate the state proportional to
$\sum_{i=1}^{d}\frac{1}{\sqrt{{\sf w}_{i}}}{\lvert}i\rangle$ in time $O(\log
d)$, $\Psi_{\cal B}$ can be generated in time $O(\log d)$.

###### Proof.

First, it is easy to verify that $\Psi_{\cal B}$ is indeed orthonormal. For
each $i\in[d]$, ${\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle$ is
orthogonal to $\Psi_{\cal
B}^{-}\subset\mathrm{span}\\{{\lvert}\leftarrow,s\rangle,{\lvert}\rightarrow,t\rangle\\}\cup\\{{\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle:i\in[d]\\}$.
Finally, $\Psi_{\cal B}^{-}$ is an orthonormal set because for
$i\in\\{2,\dots,d\\}$,
${{\langle}\leftarrow,s|}b_{i}\rangle={{\langle}\rightarrow,t|}b_{i}\rangle={{\langle}\bar{b}_{1}|}b_{i}\rangle=0$,
and ${\lvert}b_{0}\rangle$ and ${\lvert}b_{1}\rangle$ are also orthogonal.

Next, observe

$\displaystyle{\cal B}$ $\displaystyle=\mathrm{span}\left\\{\sqrt{{\sf
w}_{i}}{\lvert}\leftarrow,i\rangle+\sqrt{{\sf
w}_{i+1}}{\lvert}\rightarrow,i+1\rangle:i\in\\{0,\dots,d\\}\right\\}\cup\left\\{\sqrt{{\sf
w}_{i}}({\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle):i\in[d]\right\\},$

from which it follows that $\dim{\cal B}\leq d+1+d=2d+1$, and in fact, it is
not difficult to see that $\dim{\cal B}=2d+1$.

We next argue that $\overline{\cal B}_{G}={\cal B}_{G}^{\bot}$, where

$\overline{\cal
B}_{G}=\mathrm{span}\\{{\lvert}s\rangle,{\lvert}t\rangle\\}\oplus\mathrm{span}\left\\{{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle-\frac{2}{\sqrt{{\sf
r}}}{\lvert}\bar{b}_{1}\rangle\right\\}.$ (6)

We clearly have ${\lvert}s\rangle,{\lvert}t\rangle\in{\cal B}_{G}^{\bot}$, and
rewriting:

$\displaystyle{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle-\frac{2}{\sqrt{{\sf
r}}}{\lvert}\bar{b}_{1}\rangle$
$\displaystyle={\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle-\sum_{i=1}^{d}\frac{1}{\sqrt{{\sf
w}_{i}}}({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle)$
$\displaystyle=\sum_{i=0}^{d}\left(\frac{1}{\sqrt{{\sf
w}_{i}}}{\lvert}\leftarrow,i\rangle-\frac{1}{\sqrt{{\sf
w}_{i+1}}}{\lvert}\rightarrow,i+1\rangle\right),$

where we have used $s=0$, $t=d+1$, and ${\sf w}_{0}={\sf w}_{d+1}=1$, we see
that it is also in ${\cal B}_{G}^{\bot}$, so $\overline{\cal
B}_{G}\subseteq{\cal B}_{G}^{\bot}$. Since $\dim\overline{\cal B}_{G}=3$, and

$\dim{\cal
B}_{G}^{\bot}=\underbrace{\dim\Xi_{s}+\sum_{i=1}^{d}\dim\Xi_{e_{i}}+\dim\Xi_{t}}_{H_{G}}-\dim{\cal
B}=2+2d+2-(2d+1)=3,$

(see Definition 3.4 and Definition 3.5) we see that $\overline{\cal
B}_{G}={\cal B}_{G}^{\bot}$.

Next, to check that $\Psi_{\cal B}\subseteq{\cal B}_{G}$, we just need to
check that each element of $\Psi_{\cal B}$ is orthogonal to each of the three
vectors in the definition of $\overline{\cal B}_{G}$. This will be sufficient,
since $\Psi_{\cal B}$ is an orthonormal set with $|\Psi_{\cal
B}|=2+d-1+d=2d+1=\dim{\cal B}_{G}$. It is simple to see that everything in
$\Psi_{\cal B}$ is orthogonal to ${\lvert}s\rangle$ and ${\lvert}t\rangle$. It
is also simple to see that everything in $\Psi_{\cal B}\setminus\Psi_{\cal
B}^{-}$ is orthogonal to all of $\overline{\cal B}_{G}$.

We turn our attention to $\Psi_{\cal B}^{-}$. ${\lvert}b_{0}\rangle$ is
obviously orthogonal to $\overline{\cal B}_{G}$. For ${\lvert}b_{1}\rangle$,
we have:

$\displaystyle{\langle}b_{1}\rvert\left({\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle-\frac{2}{\sqrt{{\sf
r}}}{\lvert}\bar{b}_{1}\rangle\right)={}$ $\displaystyle\frac{1}{\sqrt{2+{\sf
r}}}\left({\langle}\leftarrow,s\rvert-{\langle}\rightarrow,t\rvert+\sqrt{{\sf
r}}{\langle}\bar{b}_{1}\rvert\right)\left({\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle-\frac{2}{\sqrt{{\sf
r}}}{\lvert}\bar{b}_{1}\rangle\right)$ $\displaystyle={}$
$\displaystyle\frac{1}{\sqrt{2+{\sf r}}}\left(2-\sqrt{\sf
r}\frac{2}{\sqrt{{\sf r}}}{{\langle}\bar{b}_{1}|}\bar{b}_{1}\rangle\right)=0.$

Finally, for any $i\in\\{2,\dots,d\\}$, we have:

$\displaystyle{\langle}b_{i}\rvert\left({\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle-\frac{2}{\sqrt{{\sf
r}}}{\lvert}\bar{b}_{1}\rangle\right)$ $\displaystyle=-\frac{2}{\sqrt{{\sf
r}}}{{\langle}b_{i}|}\bar{b}_{1}\rangle=0,$

since the ${\lvert}b_{i}\rangle$ are all orthogonal to
${\lvert}\bar{b}_{1}\rangle$. Thus $\Psi_{\cal B}\subseteq{\cal B}_{G}$, and
so $\Psi_{\cal B}$ is an orthonormal basis for ${\cal B}_{G}$.

It is clear by inspection that $\Psi_{\cal B}$ satisfies the properties of
Definition 3.7, so to complete the proof, we need to argue that $\Psi_{\cal
B}$ can be generated in $O(\log d)$ time. It is a simple exercise to observe
that the basis in (6) can be generated in $O(\log d)$ time, and then the
result follows from Corollary 2.10. ∎

To prove the second item of Lemma 3.19, we show the following.

######  Lemma 3.21.

If $\varphi(e_{i})=1$ for all $i\in[d]$, then the following is a positive
witness for $G$ (Definition 3.9):

${\lvert}w\rangle={\lvert}s\rangle-{\lvert}\leftarrow,s\rangle+\underbrace{\sum_{i=1}^{d}\frac{1}{\sqrt{{\sf
w}_{i}}}({\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle)}_{{\lvert}\hat{w}\rangle}+{\lvert}\rightarrow,t\rangle-{\lvert}t\rangle.$

###### Proof.

Since $\varphi(e_{i})=1$ for all $i\in[d]$, we have $\Xi_{e_{i}}^{\cal
A}=\Xi_{e_{i}}^{\cal
B}=\mathrm{span}\\{{\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle\\}$,
so clearly ${\lvert}w\rangle$ is orthogonal to $\Xi_{e_{i}}^{\cal
A}+\Xi_{e_{i}}^{\cal B}$ for each $i$. One can similarly verify by inspection
that it is orthogonal to $\Xi_{s}^{\cal A}$, as well as $\Xi_{t}^{\cal A}$.
This leaves only the spaces ${\cal V}_{u_{i}}$ for $i\in\\{0,\dots,d\\}$,
which we can verify are orthogonal to ${\lvert}w\rangle$ by rewriting it as:

${\lvert}w\rangle={\lvert}s\rangle-\sum_{i=0}^{d}\left(\frac{1}{\sqrt{{\sf
w}_{i}}}{\lvert}\leftarrow,i\rangle-\frac{1}{\sqrt{{\sf
w}_{i+1}}}{\lvert}\rightarrow,i+1\rangle\right)-{\lvert}t\rangle.$

We used the fact that ${\sf w}_{0}={\sf w}_{d+1}=1$, $0=s$ and $d+1=t$. Thus,
${\lvert}w\rangle\in{\cal A}_{G}^{\bot}\cap{\cal B}_{G}^{\bot}$. ∎

Finally, to prove the third item of Lemma 3.19, we show the following.

######  Lemma 3.22.

If $\varphi(e_{i})=0$ for some $i\in[d]$, then the following is a negative
witness for $G$ (Definition 3.10):

${\lvert}w_{\cal
A}\rangle={\lvert}s\rangle+{\lvert}\leftarrow,s\rangle+\underbrace{{\sqrt{{\sf
w}_{j}}}({\lvert}\rightarrow,j\rangle-{\lvert}\leftarrow,j\rangle)}_{{\lvert}\hat{w}\rangle}-{\lvert}\rightarrow,t\rangle-{\lvert}t\rangle.$

###### Proof.

First note that for any $j\in[d]$, using ${\sf w}_{0}=1$ and
${\lvert}\leftarrow,0\rangle={\lvert}\leftarrow,s\rangle$:

$\displaystyle\sum_{i=1}^{j}\underbrace{(\sqrt{{\sf
w}_{i-1}}{\lvert}\leftarrow,i-1\rangle+\sqrt{{\sf
w}_{i}}{\lvert}\rightarrow,i\rangle)}_{\in{\cal V}_{u_{i-1}}\subset{\cal
B}}-\sum_{i=1}^{j-1}\sqrt{{\sf
w}_{i}}(\underbrace{{\lvert}\rightarrow,i\rangle+{\lvert}\leftarrow,i\rangle}_{\in\Xi_{e_{i}}^{\cal
B}})$ $\displaystyle={}$ $\displaystyle\sqrt{{\sf
w}_{0}}{\lvert}\leftarrow,0\rangle+\sqrt{{\sf
w}_{j}}{\lvert}\rightarrow,j\rangle={\lvert}\leftarrow,s\rangle+\sqrt{{\sf
w}_{j}}{\lvert}\rightarrow,j\rangle$

is in ${\cal B}_{G}$. By a similar argument, $\sqrt{{\sf
w}_{j}}{\lvert}\leftarrow,j\rangle+{\lvert}\rightarrow,t\rangle\in{\cal
B}_{G}$.

Since $\varphi(e_{i})=0$,
${\lvert}\rightarrow,i\rangle-(-1)^{\varphi(e_{i})}{\lvert}\leftarrow,i\rangle={\lvert}\rightarrow,i\rangle-{\lvert}\leftarrow,i\rangle$
is in $\Xi_{e_{i}}^{\cal A}$, we have:

${\lvert}s\rangle-{\lvert}t\rangle=\underbrace{{\lvert}s\rangle+{\lvert}\leftarrow,s\rangle}_{\in\Xi_{s}^{\cal
A}}-\underbrace{({\lvert}\leftarrow,s\rangle+\sqrt{{\sf
w}_{j}}{\lvert}\rightarrow,j\rangle)}_{\in{\cal B}}+\sqrt{{\sf
w}_{j}}\underbrace{({\lvert}\rightarrow,j\rangle-{\lvert}\leftarrow,j\rangle)}_{\in\Xi_{e_{j}}^{\cal
A}}\\\ +\underbrace{\sqrt{{\sf
w}_{j}}{\lvert}\leftarrow,j\rangle+{\lvert}\rightarrow,t\rangle}_{\in{\cal
B}}-\underbrace{({\lvert}\rightarrow,t\rangle+{\lvert}t\rangle)}_{\in\Xi_{t}^{\cal
A}},$

implying that ${\lvert}{w}_{\cal A}\rangle$ is a negative witness. ∎

###  3.4 Example: Classical Deterministic Algorithms

In the next section, we will see how to turn a quantum algorithm into a
subspace graph. As a warmup example, we first see how classical deterministic
algorithms fit into this framework. The simplest example is a reversible
classical algorithm, which we can model as an undirected random walk on a
line. It is not very sensible to model a classical algorithm as a random walk
on a line, because we incur a quadratic slow-down by letting the algorithm
travel backwards sometimes, instead of always forwards, but when we move from
random walks to quantum walks, it is a perfectly valid thing to do, since a
quantum walker traverses a line in linear time, rather than quadratic.

A reversible classical deterministic algorithm can be described by the
following objects.

  * •

A finite set ${\cal Z}$ of the algorithm’s states;

  * •

A sequence of permutations $\pi_{1},\ldots,\pi_{T}:{\cal Z}\to{\cal Z}$ that
depend (implicitly) on the input;

  * •

An initial state $z_{1}\in{\cal Z}$;

  * •

A partitioning of ${\cal Z}$ into accepting and rejecting states ${\cal
Z}={\cal Z}_{\text{acc}}\sqcup{\cal Z}_{\text{rej}}$.

$\dots$$\dots$$v_{0,z_{1}}$$v_{t,z}$$v_{t+1,\pi_{t+1}(z)}$$v_{T,z}$$V_{0}$$V_{t}$$V_{t+1}$$V_{T}$
Figure 3:  The graph $G$ for a reversible classical deterministic algorithm
with five algorithm states. Between each set $V_{t}$ and $V_{t+1}$, there is
exactly one edge connected to $s=v_{0,z_{1}}$. The dashed lines represent
dangling boundary “edges”.

From these, we define $G=(V,E)$ by specifying its vertices and edges:

$\displaystyle V$ $\displaystyle=\bigsqcup_{\ell=0}^{T}V_{\ell},\mbox{ where
}V_{\ell}=\\{v_{\ell,z}:z\in{\cal Z}\\},$ $\displaystyle\mbox{and }E$
$\displaystyle=\\{e_{\ell,z}=(v_{\ell,z},v_{\ell+1,\pi_{\ell+1}(z)}):0\leq\ell\leq
T-1,z\in{\cal Z}\\}.$

Note that the graph $G$ depends on the input because the edges are specified
by the permutations. The boundary is defined $B=\\{s\\}\cup M$ where
$s=v_{0,z_{1}}$ and $M=\\{v_{T,z}:z\in{\cal Z}_{\text{acc}}\\}$.

Next, we introduce a subspace graph structure on $G$ in order to run a quantum
walk following Example 3.3. It is easy to see that the connected component
containing $s$ is a line with one vertex in each of $V_{\ell}$, and the
algorithm accepts if and only if the vertex in $V_{T}$ connected to $s$ is in
$M$ – that is, if and only if $s$ is connected to some vertex in $M$. Thus the
quantum walk will decide whether
$\pi_{T}\circ\ldots\circ\pi_{1}(z_{1})\in{\cal Z}_{\text{acc}}$. See Figure 3
for a visualization of $G$. We set all edge weights to be $1$, and then,
following Example 3.3, we define boundary and edge spaces:

$\displaystyle\Xi_{s}$
$\displaystyle=\mathrm{span}\\{{\lvert}s\rangle,{\lvert}\leftarrow,s\rangle\\},\quad\Xi_{s}^{\cal
A}=\mathrm{span}\\{{\lvert}s\rangle+{\lvert}\leftarrow,s\rangle\\},\quad\mbox{and}\quad\Xi_{s}^{\cal
B}=\\{0\\}$ $\displaystyle\forall z\in{\cal Z}_{\text{acc}},\;\Xi_{v_{T,z}}$
$\displaystyle=\mathrm{span}\\{{\lvert}\rightarrow,v_{T,z}\rangle,{\lvert}v_{T,z}\rangle\\},\quad\mbox{and}\quad\Xi_{v_{T,z}}^{\cal
A}=\Xi_{v_{T,z}}^{\cal B}=\\{0\\}$
$\displaystyle\forall\ell\in\\{0,\dots,T-1\\},z\in{\cal Z},\;\Xi_{e_{\ell,z}}$
$\displaystyle=\mathrm{span}\\{{\lvert}\rightarrow,\ell,z\rangle,{\lvert}\leftarrow,\ell,z\rangle\\},$
$\displaystyle\Xi_{e_{\ell,z}}^{\cal A}$
$\displaystyle=\mathrm{span}\\{{\lvert}\rightarrow,\ell,z\rangle+{\lvert}\leftarrow,\ell,z\rangle\\},\;\mbox{
and }\Xi_{e_{\ell,z}}^{\cal B}=\\{0\\},$

and all vertices are simple (Definition 3.2), so:

$\displaystyle\forall z\in{\cal Z},\;{\cal V}_{v_{0,z}}$
$\displaystyle=\mathrm{span}\\{{\lvert}\psi_{\star}(v_{0,z})\rangle={\lvert}\rightarrow,{0,z}\rangle\\},$
$\displaystyle\forall t\in\\{1,\dots,T-1\\},z\in{\cal Z},\;{\cal
V}_{v_{\ell,z}}$
$\displaystyle=\mathrm{span}\\{{\lvert}\psi_{\star}(v_{\ell,z})\rangle={\lvert}\leftarrow,{\ell-1,\pi_{\ell}^{-1}(z)}\rangle+{\lvert}\rightarrow,{\ell,z}\rangle\\}$
$\displaystyle\forall z\in{\cal Z},\;{\cal V}_{v_{T,z}}$
$\displaystyle=\mathrm{span}\\{{\lvert}\psi_{\star}(v_{0,z})\rangle={\lvert}\leftarrow,{T-1,\pi_{T}^{-1}(z)}\rangle\\}.$

While the algorithm is represented by a path, as is the graph for AND in
Section 3.3.2, in contrast to Section 3.3.2, we represent this path in terms
of the local constraints
${\lvert}\leftarrow,\ell-1,\pi_{\ell}^{-1}(z)\rangle+{\lvert}\rightarrow,\ell,z\rangle$.
That is because, unlike the path in Section 3.3.2, this path is defined
sequentially. These local constraints can be generated by calling the relevant
permutation, which is one step of the algorithm, whereas one can verify that
generating a basis like that in Section 3.3.2, which includes a superposition
over the whole path, or whole sequence of algorithm steps, would require
running the whole algorithm.

Unlike the other examples in this paper, to get a quantum walk algorithm,
following Example 3.3, we need ${\lvert}\psi_{0}\rangle={\lvert}s\rangle$. We
do not have $B=\\{s,t\\}$ (assuming $|{\cal Z}_{\text{acc}}|\neq 1$), so we
cannot use canonical boundary here, but it would be possible to modify this
subspace graph to have canonical boundary, as follows. We can essentially take
two copies of $G$, $G^{\rightarrow}$ and $G^{\leftarrow}$, and identify the
points $M$ in each of the two copies, so that the connected component of $s$
is a line that first goes through $G^{\rightarrow}$ to some vertex in $V_{T}$,
and then, if it has reached a point in $M$, goes through $G^{\leftarrow}$ back
to the second copy of $s$, which we could call $t$. This is like a classical
algorithm that computes a final state, copies out the answer bit, and then
uncomputes, which is also what we do for quantum algorithms in the next
section, except that the answer bit goes into the phase.

Another modification we could make to this subspace graph is as follows. We
mentioned that a classical reversible algorithm is like a walk on a line, but
$G$ is not a line, though the connected component containing $s$ always is. We
can actually modify $G$ to get a subspace graph $G^{\prime}$ that is a line of
length $T$, where $v_{\ell}$ corresponds to the set $V_{\ell}$ in $G$, which
better captures our intuition that a deterministic algorithm is a linear
process. The edge spaces of $G^{\prime}$ are obtained by combining those of
$G$: $\Xi_{e_{\ell}}^{\prime}=\bigoplus_{z\in{\cal Z}}\Xi_{e_{\ell,z}}$, and
similarly for $\Xi_{e_{\ell}}^{{}^{\prime}\cal A}$. The vertex spaces are
similarly obtained: ${\cal V}_{v_{\ell}}^{\prime}=\bigoplus_{z\in{\cal
Z}}{\cal V}_{v_{\ell,z}}$. This is essentially what we do for quantum
algorithms in the next section.

###  3.5 Example: Quantum Algorithms

In this section, we describe a subspace graph from any quantum algorithm. This
construction is essentially the same as the one in [Jef22], but we state it
here explicitly as a subspace graph. While the construction in [Jef22] applies
to _variable-time_ quantum algorithms, for simplicity, we will consider
algorithms that run for a fixed time $\sf T$. However, Lemma 3.23 below, and
all results that use it, also apply for variable-time algorithms, replacing
$\sf T$ with the expected running time.

A quantum algorithm is a sequence of unitaries $U_{1},\dots,U_{T}$ acting on
the space

${H}_{\cal Y}\otimes H_{\cal
Z}=\mathrm{span}\\{{\lvert}a\rangle{\lvert}z\rangle:a\in\\{0,1\\},z\in{\cal
Z}\\}.$

We assume each unitary can be implemented in unit cost, and moreover, the
unitary $\sum_{r=1}^{T}{\lvert}r\rangle{\langle}r\rvert\otimes U_{r}$ can be
implemented in unit cost.

The algorithm may implicitly depend on some input $x\in\\{0,1\\}^{n}$, for
example, by letting some of the unitaries be queries to $x$ (or in any other
way, we don’t care). We say the algorithm _computes_ some
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ if

$U_{T}\dots
U_{1}{\lvert}0,0\rangle\in\mathrm{span}\\{{\lvert}f(x),z\rangle:z\in{\cal
Z}\\}$

on input $x$. We are assuming the algorithm has no error for simplicity. In
some of our conclusions, we can always substitute an algorithm with error if
the error is small enough that the algorithm is indistinguishable from an
error-free one. In this section, we will prove the following.

######  Lemma 3.23.

From any quantum algorithm computing some
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ with no error in time $T$, and any
positive weights $\\{\alpha_{r}\\}$ such that $\alpha_{0}=1$, we can derive an
$st$-composable subspace graph (Definition 3.8) $G$ that computes $f$ with
$\dim H_{G}=O(|{\cal Z}|T)$, $\hat{W}_{+}\leq
2\sum_{r=1}^{T}\frac{1}{\alpha_{r}}$ and $\hat{W}_{-}\leq
2\sum_{r=1}^{T}\alpha_{r}$; with $st$-composable working bases that have
scaling factor ${\sf r}=2$ and can be generated in time $O(\log(T))$.

For example, we can set the weights all to 1, and then we get $\hat{W}_{+}$
and $\hat{W}_{-}$ both at most $2T$.

In order to remain consistent with [Jef22] so that we can easily use results
proven there, while still keeping the boundary of $G$ simple, we are going to
assume that $U_{1}=-I$, at the expense of potentially making the algorithm one
step longer. Thus, we will let ${\sf T}=T+1$, and the algorithm referred to in
Lemma 3.23 is actually $U_{2},\dots,U_{\sf T}$.

We define a subspace graph $G=(V,E)$ as follows. We will assume $\sf T$ is
even, and let:

$V=\\{v_{2\ell-1}^{\rightarrow},v_{2\ell-1}^{\leftarrow}\\}_{\ell=1}^{{\sf
T}/2},\quad
E=\\{e_{2\ell}^{\rightarrow},e_{2\ell}^{\leftarrow}\\}_{\ell=1}^{{\sf
T}/2-1}\cup\\{e_{\sf T}^{\leftrightarrow}\\},\quad\mbox{and}\quad
B=\\{s\colonequals v_{1}^{\rightarrow},t\colonequals v_{1}^{\leftarrow}\\}$

with $e_{i}^{\rightarrow}=(v_{i-1}^{\rightarrow},v_{i+1}^{\rightarrow})$ (and
similarly for $e_{i}^{\leftarrow}$), and $e_{\sf T}^{\leftrightarrow}=(v_{{\sf
T}-1}^{\rightarrow},v_{{\sf T}-1}^{\leftarrow})$.

$\dots$$\dots$$v_{1}^{\rightarrow}$$e_{2}^{\rightarrow}$$v_{3}^{\rightarrow}$$e_{4}^{\rightarrow}$$v_{5}^{\rightarrow}$$v_{{\sf
T}-1}^{\rightarrow}$$e_{\sf
T}^{\leftrightarrow}$$v_{1}^{\leftarrow}$$e_{2}^{\leftarrow}$$v_{3}^{\leftarrow}$$e_{4}^{\leftarrow}$$v_{5}^{\leftarrow}$$v_{{\sf
T}-1}^{\leftarrow}$ Figure 4: The graph $G$. The dashed lines represent
dangling boundary “edges”.

We define:

$\begin{split}\forall\ell\in\\{1,\dots,({\sf
T}-1)/2\\},\;\Xi_{e_{2\ell-1}^{\rightarrow}}&\colonequals\mathrm{span}\\{{\lvert}\rightarrow\rangle{\lvert}a,z\rangle{\lvert}2\ell-1\rangle,{\lvert}\rightarrow\rangle{\lvert}a,z\rangle{\lvert}2\ell\rangle:a\in\\{0,1\\},z\in{\cal
Z}\\}\\\ \forall\ell\in\\{1,\dots,({\sf
T}-1)/2\\},\;\Xi_{e_{2\ell-1}^{\leftarrow}}&\colonequals\mathrm{span}\\{{\lvert}\leftarrow\rangle{\lvert}a,z\rangle{\lvert}2\ell-1\rangle,{\lvert}\leftarrow\rangle{\lvert}a,z\rangle{\lvert}2\ell\rangle:a\in\\{0,1\\},z\in{\cal
Z}\\}\\\ \Xi_{e_{\sf
T}^{\leftrightarrow}}&\colonequals\mathrm{span}\\{{\lvert}\rightarrow\rangle{\lvert}a,z\rangle{\lvert}{\sf
T}\rangle,{\lvert}\leftarrow\rangle{\lvert}a,z\rangle{\lvert}{\sf
T}\rangle:a\in\\{0,1\\},z\in{\cal Z}\\}\\\
\Xi_{s}=\Xi_{v_{1}^{\rightarrow}}&\colonequals\mathrm{span}\\{{\lvert}s\rangle\colonequals{\lvert}\rightarrow\rangle{\lvert}0,0\rangle{\lvert}0\rangle,{\lvert}\leftarrow,s\rangle\colonequals{\lvert}\rightarrow\rangle{\lvert}0,0\rangle{\lvert}1\rangle\\}\\\
\Xi_{t}=\Xi_{v_{1}^{\leftarrow}}&\colonequals\mathrm{span}\\{{\lvert}t\rangle\colonequals{\lvert}\leftarrow\rangle{\lvert}0,0\rangle{\lvert}0\rangle,{\lvert}\rightarrow,t\rangle\colonequals{\lvert}\leftarrow\rangle{\lvert}0,0\rangle{\lvert}1\rangle\\}.\end{split}$
(7)

Following [Jef22, Definition 3.1], we define the following sets of vectors in
$H_{G}=\Xi_{E}\oplus\Xi_{B}$ to use in the construction of our subspaces, for
positive weights $\\{\alpha_{r}\\}_{r}$ such that $\alpha_{0}=\alpha_{1}=1$.

######  Definition 3.24.

The _forward transition states_ are defined:

$\begin{split}\forall r\in\\{0,\dots,{\sf
T}-1\\},\;\Psi_{r}^{\rightarrow}&\colonequals\left\\{{\lvert}\psi_{a,z,r}^{\rightarrow}\rangle\colonequals{\lvert}\rightarrow\rangle\left(\sqrt{\alpha_{r}}{\lvert}a,z\rangle{\lvert}r\rangle-\sqrt{\alpha_{r+1}}U_{r+1}{\lvert}a,z\rangle{\lvert}r+1\rangle\right):a\in\\{0,1\\},z\in{\cal
Z}\right\\}.\end{split}$

The _backward transition states_ are defined:

$\begin{split}\forall r\in\\{0,\dots,{\sf
T}-1\\},\;\Psi_{r}^{\leftarrow}&\colonequals\left\\{{\lvert}\psi_{a,z,r}^{\leftarrow}\rangle\colonequals{\lvert}\leftarrow\rangle\left(\sqrt{\alpha_{r}}{\lvert}a,z\rangle{\lvert}r\rangle-\sqrt{\alpha_{r+1}}U_{r+1}{\lvert}a,z\rangle{\lvert}r+1\rangle\right):a\in\\{0,1\\},z\in{\cal
Z}\right\\}.\end{split}$

The _reversal states_ are defined:

$\Psi_{\sf T}^{\leftrightarrow}\colonequals\left\\{{\lvert}\psi_{a,z,{\sf
T}}^{\leftrightarrow}\rangle\colonequals\sqrt{\alpha_{\sf
T}}\left({\lvert}\rightarrow\rangle-(-1)^{a}{\lvert}\leftarrow\rangle\right){\lvert}a,z\rangle{\lvert}{\sf
T}\rangle:a\in\\{0,1\\},z\in{\cal Z}\right\\}.$

Finally, let:

$\Psi_{0}=\bigcup_{\ell=0}^{{\sf
T}/2-1}(\Psi_{2\ell}^{\rightarrow}\cup\Psi_{2\ell}^{\leftarrow})\cup\Psi_{\sf
T}^{\leftrightarrow}\quad\mbox{ and }\quad\Psi_{1}=\bigcup_{\ell=0}^{{\sf
T}/2}(\Psi_{2\ell-1}^{\rightarrow}\cup\Psi_{2\ell-1}^{\leftarrow}).$

Note that since we assume $U_{1}=-I$, we have:

${\lvert}\psi_{0,0,0}^{\rightarrow}\rangle={\lvert}\rightarrow\rangle{\lvert}0,0\rangle{\lvert}0\rangle-{\lvert}\rightarrow\rangle
U_{1}{\lvert}0,0\rangle{\lvert}1\rangle={\lvert}s\rangle+{\lvert}\rightarrow\rangle{\lvert}0,0\rangle{\lvert}1\rangle={\lvert}s\rangle+{\lvert}\leftarrow,s\rangle,$

and similarly,

${\lvert}\psi_{0,0,0}^{\leftarrow}\rangle={\lvert}\leftarrow\rangle{\lvert}0,0\rangle{\lvert}0\rangle+{\lvert}\leftarrow\rangle{\lvert}0,0\rangle{\lvert}1\rangle={\lvert}t\rangle+{\lvert}\rightarrow,t\rangle.$

Then we define:

$\begin{split}&{\cal
V}_{v_{1}^{\rightarrow}}\colonequals\mathrm{span}\\{{\lvert}\psi_{0,0,1}^{\rightarrow}\rangle\\}\quad\mbox{
and }\quad{\cal
V}_{v_{1}^{\leftarrow}}\colonequals\mathrm{span}\\{{\lvert}\psi_{0,0,1}^{\leftarrow}\rangle\\}\\\
\forall\ell\in\\{2,\dots,{\sf T}/2\\},\;&{\cal
V}_{v_{2\ell-1}^{\rightarrow}}\colonequals\mathrm{span}\Psi_{2\ell-1}^{\rightarrow}\quad\mbox{
and }\quad{\cal
V}_{v_{2\ell-1}^{\leftarrow}}\colonequals\mathrm{span}\Psi_{2\ell-1}^{\leftarrow}\\\
\forall\ell\in\\{1,\dots,{\sf T}/2-1\\},\;&\Xi_{e_{2\ell}^{\rightarrow}}^{\cal
A}\colonequals\mathrm{span}\Psi_{2\ell}^{\rightarrow}\quad\mbox{ and
}\quad\Xi_{e_{2\ell}^{\leftarrow}}^{\cal
A}\colonequals\mathrm{span}\Psi_{2\ell}^{\leftarrow}\\\ &\Xi_{e_{\sf
T}^{\leftrightarrow}}^{\cal A}\colonequals\mathrm{span}\Psi_{\sf
T}^{\leftrightarrow}\\\ &\Xi_{s}^{\cal
A}\colonequals\mathrm{span}\\{{\lvert}\psi_{0,0,0}^{\rightarrow}\rangle\\}=\mathrm{span}\\{{\lvert}s\rangle+{\lvert}\leftarrow,s\rangle\\}\\\
&\Xi_{t}^{\cal
A}\colonequals\mathrm{span}\\{{\lvert}\psi_{0,0,0}^{\leftarrow}\rangle\\}=\mathrm{span}\\{{\lvert}t\rangle+{\lvert}\rightarrow,t\rangle\\}.\end{split}$
(8)

For all $e\in E\cup B$, we will have $\Xi_{e}^{\cal B}=\\{0\\}$. Note that the
subspace graph we have just defined has canonical $st$-boundary (Definition
3.5). As per Definition 3.1, we have

$\begin{split}{\cal A}_{G}&=\Xi_{s}^{\cal A}\oplus\Xi_{t}^{\cal
A}\oplus\bigoplus_{\ell=1}^{{\sf T}/2-1}(\Xi_{e_{2\ell}^{\rightarrow}}^{\cal
A}\oplus\Xi_{e_{2\ell}^{\leftarrow}}^{\cal A})\oplus\Xi_{e_{\sf
T}^{\leftrightarrow}}^{\cal A}\\\ {\cal B}_{G}&=\bigoplus_{\ell=1}^{{\sf
T}/2}\left({\cal V}_{v_{2\ell-1}^{\rightarrow}}\oplus{\cal
V}_{v_{2\ell-1}^{\leftarrow}}\right).\end{split}$ (9)

In [Jef22], the vectors in Definition 3.24 form the working basis, which works
perfectly fine, because since all $\Xi_{e}^{\cal B}$ are trivial, we have a
decomposition of ${\cal B}_{G}$ into orthogonal spaces ${\cal V}_{v}$, so we
can simply combine their bases. However, here, we will use a slightly
different working basis for ${\cal B}_{G}$ to conform to Definition 2.8, as
follows.

Let $\bar{\Psi}_{r}^{\rightarrow}$ contain normalized vectors.

$\Psi_{{\cal
A}}=\left\\{{\lvert}\bar{\psi}_{0,0,0}^{\rightarrow}\rangle=\frac{1}{\sqrt{2}}\left({\lvert}s\rangle+{\lvert}\leftarrow,s\rangle\right),{\lvert}\bar{\psi}_{0,0,0}^{\rightarrow}\rangle=\frac{1}{\sqrt{2}}\left({\lvert}t\rangle+{\lvert}\rightarrow,t\rangle\right)\right\\}\cup\bigcup_{\ell=1}^{{\sf
T}/2-1}(\bar{\Psi}_{2\ell}^{\rightarrow}\cup\bar{\Psi}_{2\ell}^{\leftarrow})\cup\bar{\Psi}_{{\sf
T}}^{\leftrightarrow}.$

Note that

${\lvert}\psi_{0,0,1}^{\rightarrow}\rangle={\lvert}\rightarrow\rangle{\lvert}0,0\rangle{\lvert}1\rangle-{\lvert}\rightarrow\rangle
U_{2}{\lvert}0,0\rangle{\lvert}2\rangle={\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow\rangle
U_{2}{\lvert}0,0\rangle{\lvert}2\rangle$

and similarly,

${\lvert}\psi_{0,0,1}^{\leftarrow}\rangle={\lvert}\rightarrow,t\rangle-{\lvert}\leftarrow\rangle
U_{2}{\lvert}0,0\rangle{\lvert}2\rangle.$

Define:

$\begin{split}{\lvert}b_{0}\rangle&\colonequals\frac{1}{\sqrt{2}}\left({\lvert}\psi_{0,0,1}^{\rightarrow}\rangle+{\lvert}\psi_{0,0,1}^{\leftarrow}\rangle+({\lvert}\rightarrow\rangle+{\lvert}\leftarrow\rangle)U_{2}{\lvert}0,0\rangle{\lvert}2\rangle)\right)=\frac{1}{\sqrt{2}}({\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle)\\\
{\lvert}b_{1}\rangle&\colonequals\frac{1}{2}\left({\lvert}\psi_{0,0,1}^{\rightarrow}\rangle-{\lvert}\psi_{0,0,1}^{\leftarrow}\rangle\right)=\frac{1}{2}\left({\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle-({\lvert}\rightarrow\rangle-{\lvert}\leftarrow\rangle)U_{2}{\lvert}0,0\rangle{\lvert}2\rangle\right)\\\
{\lvert}b_{2}\rangle&\colonequals\frac{1}{\sqrt{2}}({\lvert}\rightarrow\rangle+{\lvert}\leftarrow\rangle)U_{2}{\lvert}0,0\rangle{\lvert}2\rangle\end{split}$

Then we have

$\mathrm{span}\\{{\lvert}b_{0}\rangle-{\lvert}b_{2}\rangle,{\lvert}b_{1}\rangle\\}=\mathrm{span}\\{{\lvert}\psi_{0,0,1}^{\rightarrow}\rangle,{\lvert}\psi_{0,0,1}^{\leftarrow}\rangle\\}={\cal
V}_{v_{1}^{\rightarrow}}\oplus{\cal V}_{v_{1}^{\leftarrow}}.$

Thus

$\Psi_{{\cal
B}}=\\{{\lvert}b_{0}\rangle,{\lvert}b_{1}\rangle,{\lvert}b_{2}\rangle\\}\cup\bigcup_{\ell=2}^{{\sf
T}/2}(\Psi_{2\ell-1}^{\rightarrow}\cup\Psi_{2\ell-1}^{\leftarrow})\cup\Psi_{{\sf
T}}^{\leftrightarrow}$

is an orthonormal basis for ${\cal B}_{G}$.

The following is given by a trivial modification of [Jef22, Lemma 3.3].

######  Lemma 3.25.

Assuming unit-time access to $\sum_{\ell=1}^{{\sf
T}}{\lvert}\ell\rangle{\langle}\ell\rvert\otimes U_{\ell}$, the working bases
$\Psi_{{\cal A}}$ and $\Psi_{{\cal B}}$ can be generated in $O(\log({\sf T}))$
complexity.

We will also use the following states from [Jef22, Definition 3.4] in the
construction of our witnesses:

######  Definition 3.26 (Algorithm States).

Define the following _algorithm states_ in $H_{G}$:

$\displaystyle{\lvert}w^{0}\rangle$
$\displaystyle={\lvert}0\rangle,\quad\forall t\in[{\sf
T}],\;{\lvert}w^{t}\rangle=U_{t}{\lvert}w^{t-1}\rangle.$

The _positive history state_ of the algorithm is defined:

${\lvert}w_{+}\rangle=({\lvert}\rightarrow\rangle+(-1)^{f(x)}{\lvert}\leftarrow\rangle)\sum_{t=0}^{{\sf
T}}\frac{1}{\sqrt{\alpha_{t}}}{\lvert}w^{t}\rangle{\lvert}t\rangle.$

The _negative history state_ of the algorithm is defined:

${\lvert}w_{-}\rangle=({\lvert}\rightarrow\rangle-(-1)^{f(x)}{\lvert}\leftarrow\rangle)\sum_{t=0}^{{\sf
T}}{\sqrt{\alpha_{t}}}(-1)^{t}{\lvert}w^{t}\rangle{\lvert}t\rangle.$

We will use the following properties from [Jef22], using the fact that the
algorithm has no error:

######  Claim 3.27.

  1. 1.

$\left\|{\lvert}w_{-}\rangle\right\|^{2}=2\sum_{t=0}^{{\sf T}}\alpha_{t}$
(Corollary 3.7)

  2. 2.

$\left\|{\lvert}w_{+}\rangle\right\|^{2}=2\sum_{t=0}^{{\sf
T}}\frac{1}{\alpha_{t}}$ (Corollary 3.7)

  3. 3.

${\lvert}w_{+}\rangle\in\mathrm{span}\Psi_{0}^{\bot}\cap\mathrm{span}\Psi_{1}^{\bot}$
(Claim 3.8).

  4. 4.

${\lvert}w_{-}\rangle\in\mathrm{span}\Psi_{0}$ and
${\lvert}w_{-}\rangle-\underbrace{({\lvert}\rightarrow\rangle-(-1)^{f(x)}{\lvert}\leftarrow\rangle){\lvert}0\rangle{\lvert}0\rangle}_{{\lvert}s\rangle-(-1)^{f(x)}{\lvert}t\rangle}\in\mathrm{span}\Psi_{1}$
(Claim 3.9).

Items (1) and (2) are rather obvious in the case of fixed time quantum
algorithms that we are specializing to here in order to avoiding defining
variable-time quantum algorithms. However, we remark that in [Jef22], the more
general case of variable-time algorithms is considered, so ${\sf T}$ is
allowed to be a random variable, and the expressions in (1) and (2) are
replaced by expectations. The construction in this section, which again, is
just putting the construction of [Jef22] into the language of subspace graphs,
would be the same in this more general case, and thus our composition results
also hold for this more general kind of algorithm.

We have the following corollaries, which, combined with Lemma 3.25, prove
Lemma 3.23.

######  Corollary 3.28 (Positive analysis).

When $f(x)=1$, ${\lvert}w_{+}\rangle$ is a positive witness for $G$ (see
Definition 3.9) with

$\left\|{\lvert}\hat{w}_{+}\rangle\right\|^{2}=2\sum_{\ell=2}^{{\sf
T}}\frac{1}{\alpha_{\ell}}.$

###### Proof.

When $f(x)=1$, since $\alpha_{0}=\alpha_{1}=1$ and
${\lvert}w^{0}\rangle={\lvert}0,0\rangle$ and
${\lvert}w^{1}\rangle=U_{1}{\lvert}0,0\rangle$,

${\lvert}w_{+}\rangle=\underbrace{{\lvert}\rightarrow\rangle{\lvert}0,0\rangle{\lvert}0\rangle}_{{\lvert}e\rangle}-\underbrace{{\lvert}\leftarrow\rangle{\lvert}0,0\rangle{\lvert}0\rangle}_{{\lvert}t\rangle}+\underbrace{{\lvert}\rightarrow\rangle
U_{1}{\lvert}0,0\rangle{\lvert}1\rangle}_{-{\lvert}\leftarrow,s\rangle}-\underbrace{{\lvert}\leftarrow\rangle
U_{1}{\lvert}0,0\rangle{\lvert}1\rangle}_{-{\lvert}\rightarrow,t\rangle}\\\
+\underbrace{({\lvert}\rightarrow\rangle+(-1)^{f(x)}{\lvert}\leftarrow\rangle)\sum_{\ell=2}^{{\sf
T}}\frac{1}{\sqrt{\alpha_{\ell}}}{\lvert}w^{\ell}\rangle{\lvert}\ell\rangle}_{{\lvert}\hat{w}_{+}\rangle}.$

By inspection (see (9) and Definition 3.24), we have ${\cal
A}_{G}\subseteq\mathrm{span}\Psi_{0}$ and ${\cal
B}_{G}\subseteq\mathrm{span}\Psi_{1}\cup\\{{\lvert}b_{0}\rangle\\}$. By Claim
3.27,
${\lvert}w_{+}\rangle\in\mathrm{span}\Psi_{0}^{\bot}\cap\mathrm{span}\Psi_{1}^{\bot}\subset{\cal
A}_{G}^{\bot}\cap{\cal B}_{G}^{\bot}$, and we can see that
${\lvert}w_{+}\rangle$ is orthogonal to
${\lvert}b_{0}\rangle=\frac{1}{\sqrt{2}}({\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle)$.
Thus ${\lvert}w_{+}\rangle$ is a positive witness, and

$\left\|{\lvert}\hat{w}_{+}\rangle\right\|^{2}=\left\|(I-\Pi_{B}){\lvert}w_{+}\rangle\right\|^{2}=2\sum_{\ell=2}^{{\sf
T}}\frac{1}{\alpha_{\ell}}.$

∎

######  Corollary 3.29 (Negative analysis).

When $f(x)=0$, ${\lvert}w_{-}\rangle$ is a negative witness for $G$ (see
Definition 3.10) with

$\left\|{\lvert}\hat{w}_{-}\rangle\right\|^{2}=2\sum_{\ell=2}^{{\sf
T}}\alpha_{\ell}.$

Thus $\hat{W}_{-}(G)\leq 2\sum_{\ell=2}^{{\sf T}}\alpha_{\ell}$.

###### Proof.

By Claim 3.27, we have ${\lvert}w_{+}\rangle\in\mathrm{span}\Psi_{0}$. Though
$\Psi_{0}$ is slightly bigger than ${\cal A}_{G}$, since we also have
${\lvert}w_{+}^{0}\rangle={\lvert}0,0\rangle$ and
${\lvert}w_{+}^{1}\rangle=-{\lvert}0,0\rangle$, we can see that
${\lvert}w_{+}\rangle\in{\cal A}_{G}$. Similarly, it is not difficult to
conclude that when $f(x)=0$,
${\lvert}w_{-}\rangle-({\lvert}s\rangle-{\lvert}t\rangle)\in{\cal B}_{G}$,
since it’s in $\Psi_{1}$ (Claim 3.27), and its projection onto
${\lvert}0\rangle$ or ${\lvert}1\rangle$ in the last register is in
$\mathrm{span}\Psi_{0}^{\rightarrow}\cup\Psi_{0}^{\leftarrow}\cup\Psi_{1}^{\rightarrow}\cup\Psi_{1}^{\leftarrow}$.
∎

##  4 Recursion with Subspace Graphs

Subspace graphs lend themselves well to very general kinds of recursion. We
can compose subspace graphs, say $G_{1}$, $G_{2}$ and $G_{3}$, as in Figure 5,
by identifying some of the vertices on their boundaries. In full generality,
this may result in a subspace graph that is difficult to analyze. For example,
if we replace two parallel edges with subspace graphs derived from quantum
algorithms, “flow” along these edges may have complex phases that interfere on
the other side. Our nice classical intuition of flows breaks down in the fully
general case, which is not surprising, since quantum algorithms are not
classical. However, an important question is in which special cases, and to
what extent, we can compose subspace graphs and keep enough classical
intuition to analyze them.

One special case is implicit in [Jef22], and we here we present another
special case, which we call _switch composition_. Switch composition
generalizes a very simple kind of recursion that can be done in switching
networks. Since an $st$-path (or more generally, flow) is allowed to use an
edge if and only if $\varphi(e)=1$, we can replace it with a switching network
$G^{e}$ for some function $f_{e}$, which will have an $st$-path from one
endpoint to the other if and only if $f_{e}(x)=1$. We can view this as
removing $e$ from the graph, and then adding its endpoints to the boundary, to
then be identified with the boundary $\\{s,t\\}$ of $G^{e}$. By applying this
type of composition, the OR and AND switching networks in Section 3.3.1 and
Section 3.3.2 can be combined to make switching networks for any Boolean
formula [JK17].

$G_{1}$$G_{2}$$G_{3}$$G_{1}$$G_{2}$$G_{3}$$G^{\circ}$ Figure 5: Some perhaps
complicated graphs $G_{1}$, $G_{2}$ and $G_{3}$, but we need only consider
their boundaries, and can abstract their internal structure. To compose them,
we identify points on their boundaries, yielding a new graph, $G^{\circ}$.

###  4.1 Switch Composition

Here we investigate how to compose subspace graphs with specific properties
that generalize switching networks – $st$-composable subspace graphs
(Definition 3.8) – into the switches of a graph $G$. Specifically, if
$\overline{E}$ is the set of edges of $G$ that are switches, we will replace
$e\in\overline{E}$ with an $st$-composable graph $G^{e}$. We can assume
without loss of generality that we replace every $e\in\overline{E}$ with some
$G^{e}$, since letting $G^{e}$ be the graph consisting of a single edge from
$s$ to $t$ is just like not replacing $e$. In particular, we will prove the
following theorem.

######  Theorem 4.1.

Let $G$ be an $st$-composable subspace graph (Definition 3.8) with
$st$-composable working bases that can be generated in time $T$, with scaling
factor ${\sf r}$. For each $e\in\overline{E}$, the set of switches of $G$, let
$G^{e}$ be an $st$-composable subspace graph with $st$-composable working
bases that can be generated in time at most $T^{\prime}$, with scaling factor
${\sf r}^{e}$. Then there exists an $st$-composable subspace graph $G^{\circ}$
with $\dim H_{G^{\circ}}\leq\dim
H_{G}-2|\overline{E}|+\sum_{e\in\overline{E}}\dim H_{G^{e}}$ such that:

  * •

$G^{\circ}$ has $st$-composable working bases that can be generated in time
$T+T^{\prime}+O(1)$, with scaling factor ${\sf r}$.

  * •

If ${\lvert}\hat{w}\rangle$ is a cropped positive witness for $G$ (Definition
3.9), and for each $e\in\overline{E}$ such that
${{\langle}\rightarrow,e|}\hat{w}\rangle\neq 0$, ${\lvert}\hat{w}^{e}\rangle$
is a cropped positive witness for $G^{e}$, then

${\lvert}\hat{w}^{\circ}\rangle=\sum_{e\in\overline{E}}\sqrt{\frac{{\sf
r}^{e}}{2}}{{\langle}\leftarrow,e|}\hat{w}\rangle{\lvert}\hat{w}^{e}\rangle+\Pi_{E\setminus\overline{E}}{\lvert}\hat{w}\rangle$

is a cropped positive witness for $G^{\circ}$.

  * •

If ${\lvert}\hat{w}_{\cal A}\rangle$ is a cropped negative witness for $G$
(Definition 3.10), and for each $e\in\overline{E}$ such that
${{\langle}\rightarrow,e|}\hat{w}_{\cal A}\rangle\neq 0$,
${\lvert}\hat{w}^{e}_{\cal A}\rangle$ is a cropped negative witness for
$G^{e}$, then

${\lvert}\hat{w}^{\circ}_{\cal
A}\rangle=\sum_{e\in\overline{E}}\sqrt{\frac{2}{{\sf
r}^{e}}}{{\langle}\leftarrow,e|}\hat{w}_{\cal
A}\rangle{\lvert}\hat{w}^{e}_{\cal
A}\rangle+\Pi_{E\setminus\overline{E}}{\lvert}\hat{w}_{\cal A}\rangle$

is a cropped negative witness for $G^{\circ}$.

It follows, using the observation that ${\lvert}\hat{w}\rangle$ must only
overlap switches that are on, and ${\lvert}\hat{w}_{\cal A}\rangle$ must only
overlap switches tht are off, that if $G$ computes $f$ and each $G^{e}$
computes $f^{e}$, the function computed by $G^{\circ}$ is the composed
function $f\circ(f_{e})_{e\in\overline{E}}$ (see Section 2.3).

Before we prove Theorem 4.1, we note the following useful corollary of Theorem
4.1 and Lemma 3.15.

######  Corollary 4.2.

Let $G$ be an $st$-composable subspace graph with $st$-composable working
bases that can be generated in time $T$ that computes $f$. Then there is an
$st$-composable subspace graph $G^{\circ}$ with $st$-composable bases that can
be generated in time $T+O(1)$ that computes $f$, and such that $\dim
H_{G^{\circ}}=\dim H_{G}+O(1)$, $\hat{W}_{+}(G^{\circ})\leq 1$ and
$\hat{W}_{-}(G^{\circ})\leq\hat{W}_{+}(G)\hat{W}_{-}(G)$.

###### Proof.

Let $G_{\textsc{or}}$ be the graph from Lemma 3.15 with $d=1$, and ${\sf
w}_{1}=\frac{{\sf r}}{2}\hat{W}_{+}(G)$, where ${\sf r}$ is the scaling factor
of the basis for $G$. It is $st$-composable since it is a switching network.
This graph has a single edge, $e_{i}$, and we will compose $G$ into this edge
using Theorem 4.1, so $G_{\textsc{or}}$ plays the role of $G$ in Theorem 4.1,
and $G$ plays the role of $G^{e_{1}}$. If $f(x)=1$, then $G$ has a cropped
positive witness ${\lvert}\hat{w}^{1}\rangle$, and using the positive witness
from Lemma 3.15, by Theorem 4.1, $G^{\circ}$ has cropped positive witness

${\lvert}\hat{w}^{\circ}\rangle=\sqrt{\frac{{\sf r}}{2}}\frac{1}{\sqrt{{\sf
w}_{1}}}{\lvert}\hat{w}^{1}\rangle=\frac{1}{\sqrt{\hat{W}_{+}(G)}}{\lvert}\hat{w}^{1}\rangle,$

so since $\left\|{\lvert}\hat{w}^{1}\rangle\right\|^{2}\leq\hat{W}_{+}(G)$,
$\hat{W}_{+}(G^{\circ})\leq 1$.

On the other hand, if $f(x)=0$, then $G$ has a cropped negative witness
${\lvert}\hat{w}_{\cal A}^{1}\rangle$, and using the negative witness for
Lemma 3.15, by Theorem 4.1, $G^{\circ}$ has cropped negative witness

${\lvert}\hat{w}_{\cal A}^{\circ}\rangle=\sqrt{\frac{2}{{\sf r}}}\sqrt{{\sf
w}_{1}}{\lvert}\hat{w}_{\cal
A}^{1}\rangle=\sqrt{\hat{W}_{+}(G)}{\lvert}\hat{w}_{\cal A}^{1}\rangle,$

so $\hat{W}_{-}(G^{\circ})\leq\hat{W}_{+}(G)\hat{W}_{-}(G)$.

To complete the proof, by Lemma 3.15, the basis for $G_{\textsc{or}}$ can be
generated in unit time, and thus by Theorem 4.1, the basis for $G^{\circ}$ can
be generated in time $T+O(1)$. ∎

In the remainder of this section, we prove Theorem 4.1.

$G$$s$$e_{1}$$e_{2}$$t$$G^{e_{1}}$$s$$t$$G^{e_{2}}$$s$$t$$G^{\circ}$$s$$t$
Figure 6: An example of replacing edges $e_{1}$ and $e_{2}$ in $G$ with graphs
$G^{e_{1}}$ and $G^{e_{2}}$ to obtain $G^{\circ}$. Boundary “edges” are
represented by dashed lines. Switching networks already lend themselves to
this type of recursion: we can replace an edge with a 2-terminal graph, and
then the “edge” is traversable if and only if the terminals are connected. The
difference with the more general recursion in Theorem 4.1 is that the subspace
graphs used to replace edges (as well as other parts of $G$) might have more
complicated structure than just their graph structure; for example, they might
encode quantum algorithms like in Section 3.5.

Informally, we obtain $G^{\circ}$ from $G$ by, for each $e\in\overline{E}$,
removing the edge $e$, and identifying its endpoints with the vertices
$s=s^{e}$ and $t=t^{e}$ of the graph $G^{e}$. This is illustrated in Figure 6.
The subspaces associated with $G^{\circ}$ are mostly inherited from $G$ and
$G^{e}$, except for those on the glued boundaries. There, intuitively, we
replace ${\lvert}\rightarrow,e\rangle$ with the edges incident to $s=s^{e}$ in
$G^{e}$, and ${\lvert}\leftarrow,e\rangle$ with the edges incident to
$t=t^{e}$ in $G^{e}$. This is formalized by the map $\widetilde{\Lambda}$
defined in (14).

##### Definition of the Subspace Graph $G^{\circ}$

We now formally define $G^{\circ}$ and its associated spaces. We will shortly
define a working basis $\Psi_{{\cal B}_{G^{\circ}}}$ for ${\cal
B}_{G^{\circ}}$, from working bases for ${\cal B}_{G}$ and ${\cal B}_{G^{e}}$.
It is actually these bases that are most important, but by defining ${\cal
B}_{G^{\circ}}$ and ${\cal A}_{G^{\circ}}$ as being built up from local
spaces, we show that the graph structure and intuition are preserved by the
composition.

The composed graph $G^{\circ}$ has vertex and edge sets:

$\begin{split}V^{\circ}&=V\sqcup\bigsqcup_{e\in\overline{E}}(V^{e}\setminus
B^{e})=V\sqcup\bigsqcup_{e\in\overline{E}}(V^{e}\setminus\\{s^{e},t^{e}\\})\\\
E^{\circ}&=(E\setminus\overline{E})\sqcup\bigsqcup_{e\in\overline{E}}E^{e}\end{split}$
(10)

and boundary

$B^{\circ}=B=\\{s,t\\}.$

We identify $s^{e}$ and $t^{e}$ in $G^{e}$ with the endpoints of $e$ in $G$,
so that the following edges are incident to $u\in V^{\circ}$:

$\begin{split}E^{\circ}(u)=\left\\{\begin{array}[]{cc}E^{e}(u)&\mbox{if }u\in
V^{e}\setminus\\{s^{e},t^{e}\\}\\\
(E(u)\setminus\overline{E})\sqcup\bigsqcup_{e\in\overline{E}\cap
E^{\rightarrow}(u)}E^{e}(s^{e})\sqcup\bigsqcup_{e\in\overline{E}\cap
E^{\leftarrow}(u)}E^{e}(t^{e})&\mbox{if }u\in V.\end{array}\right.\end{split}$
(11)

Recall that we assume for convenience that each edge has an orientation, and
$E^{\rightarrow}(u)\subseteq E(u)$ are the edges oriented outwards from $u$,
and $E^{\leftarrow}(u)=E(u)\setminus E^{\rightarrow}(u)$ those oriented
inwards. This is simply to decide which of the endpoints of $e$ is identified
with $s^{e}$ and which with $t^{e}$.

We define the edge spaces and edge subspaces of $G^{\circ}$ from those of $G$
and $G^{e}$ as follows:

$\Xi_{e^{\prime}}^{\circ}=\left\\{\begin{array}[]{ll}\Xi_{e^{\prime}}&\mbox{if
}e^{\prime}\in(E\setminus\overline{E})\cup B\\\ \Xi_{e^{\prime}}^{e}&\mbox{if
}e^{\prime}\in E^{e},\end{array}\right.$ (12)

and similarly for $\Xi_{e}^{\circ\cal A}$ and $\Xi_{e}^{\circ\cal B}$. Note
that since $G$ has canonical $st$-boundary, so does $G^{\circ}$. Furthermore,
since the switches and non-switches of $G^{\circ}$ are:

$\overline{E}^{\circ}=\bigsqcup_{e\in\overline{E}}\overline{E}^{e}\mbox{ and
}E^{\circ}\setminus\overline{E}^{\circ}=(E\setminus\overline{E})\sqcup\bigsqcup_{e\in\overline{E}}(E^{e}\setminus\overline{E}^{e}),$

we inherit the property that for all $e\in
E^{\circ}\setminus\overline{E}^{\circ}$, $\Xi_{e}^{\circ\cal B}=\\{0\\}$.

Next we define the vertex spaces. First, for each $e\in\overline{E}$, we are
assuming that ${\cal V}_{s^{e}}^{e}$ and ${\cal V}_{t^{e}}^{e}$ can be
written:

$\begin{split}{\cal
V}_{s^{e}}^{e}&=\mathrm{span}\\{{\lvert}\leftarrow,s^{e}\rangle+{\lvert}\psi_{\star}(s^{e})\rangle\\}\\\
{\cal
V}_{t^{e}}^{e}&=\mathrm{span}\\{{\lvert}\rightarrow,t^{e}\rangle+{\lvert}\psi_{\star}(t^{e})\rangle\\},\end{split}$
(13)

for some ${\lvert}\psi_{\star}(s^{e})\rangle\in\Xi_{E^{e}(s^{e})}^{e}$ and
${\lvert}\psi_{\star}(t^{e})\rangle\in\Xi_{E^{e}(t^{e})}^{e}$. Then define a
linear map $\widetilde{\Lambda}$ on $H_{G}$ by:

$\widetilde{\Lambda}=\sum_{e\in\overline{E}}\frac{1}{\sqrt{{\sf
r}^{e}}}({\lvert}\psi_{\star}(s^{e})\rangle{\langle}\rightarrow,e\rvert+{\lvert}\psi_{\star}(t^{e})\rangle{\langle}\leftarrow,e\rvert)+\Pi_{E\setminus\overline{{E}}}+\Pi_{B},$
(14)

and let

${\cal V}_{u}^{\circ}=\left\\{\begin{array}[]{ll}\widetilde{\Lambda}({\cal
V}_{u})&\mbox{if }u\in V\\\ {\cal V}_{u}^{e}&\mbox{if }u\in
V^{e}\setminus\\{s^{e},t^{e}\\}.\end{array}\right.$ (15)

The following lemma shows that $G^{\circ}$ is a well-defined subspace graph.

######  Lemma 4.3.

$\widetilde{\Lambda}({\cal V}_{u})\subseteq\Xi_{E^{\circ}(u)}^{\circ}$.

###### Proof.

We have ${\cal V}_{u}\subseteq\Xi_{E(u)}$, so

$\widetilde{\Lambda}({\cal
V}_{u})=\widetilde{\Lambda}\left(\Xi_{E(u)\setminus\overline{E}}\cap{\cal
V}_{u}\right)\oplus\bigoplus_{e\in\overline{E}\cap
E(u)}\widetilde{\Lambda}\left(\Xi_{e}\cap{\cal V}_{u}\right),$

We have $\widetilde{\Lambda}\left(\Xi_{E(u)\setminus\overline{E}}\cap{\cal
V}_{u}\right)=\Xi_{E(u)\setminus\overline{E}}\cap{\cal V}_{u}$, since
$\widetilde{\Lambda}$ fixes $\Xi_{E\setminus\overline{E}}$. Recall from
Definition 3.4 that for $e\in\overline{E}\cap E(u)$

$\Xi_{e}\cap{\cal
V}_{u}=\left\\{\begin{array}[]{ll}\mathrm{span}\\{{\lvert}\rightarrow,e\rangle\\}&\mbox{if
}e\in E^{\rightarrow}(u)\\\
\mathrm{span}\\{{\lvert}\leftarrow,e\rangle\\}&\mbox{if }e\in
E^{\leftarrow}(u).\end{array}\right.$

Thus,

$\widetilde{\Lambda}\left(\Xi_{e}\cap{\cal
V}_{u}\right)=\left\\{\begin{array}[]{ll}\mathrm{span}\\{\widetilde{\Lambda}{\lvert}\rightarrow,e\rangle\\}=\mathrm{span}\\{{\lvert}\psi_{\star}(s^{e})\rangle\\}\subseteq\Xi_{E^{e}(s^{e})}^{e}&\mbox{if
}e\in E^{\rightarrow}(u)\\\
\mathrm{span}\\{\widetilde{\Lambda}{\lvert}\leftarrow,e\rangle\\}=\mathrm{span}\\{{\lvert}\psi_{\star}(t^{e})\rangle\\}\subseteq\Xi_{E^{e}(t^{e})}^{e}&\mbox{if
}e\in E^{\leftarrow}(u).\end{array}\right.$

Thus

$\widetilde{\Lambda}({\cal
V}_{u})\subseteq\Xi_{E(u)\setminus\overline{E}}\oplus\bigoplus_{e\in\overline{E}\cap
E^{\rightarrow}(u)}\Xi_{E^{e}(s^{e})}^{e}\oplus\bigoplus_{e\in\overline{E}\cap
E^{\leftarrow}(u)}\Xi_{E^{e}(t^{e})}^{e}=\Xi_{E^{\circ}(u)}$

by (11). ∎

From these definitions, we conclude:

$\begin{split}{\cal A}_{G^{\circ}}&=\bigoplus_{e\in
E^{\circ}}\Xi_{e}^{\circ\cal A}\oplus\bigoplus_{u\in
B^{\circ}}\Xi_{u}^{\circ\cal A}=\bigoplus_{e\in
E\setminus\overline{E}}\Xi_{e}^{\cal
A}\oplus\bigoplus_{e\in\overline{E}}\bigoplus_{e^{\prime}\in
E^{e}}\Xi_{e^{\prime}}^{e\cal A}\oplus\Xi_{s}^{\cal A}\oplus\Xi_{t}^{\cal
A}\\\ &=\bigoplus_{e\in E\setminus\overline{E}}\Xi_{e}^{\cal
A}\oplus\bigoplus_{e\in\overline{E}}\bigoplus_{e^{\prime}\in
E^{e}}\Xi_{e^{\prime}}^{e\cal A}\oplus\Xi_{s}^{\cal A}\end{split}$ (16)

and similarly

$\begin{split}{\cal B}_{G^{\circ}}&=\bigoplus_{u\in V^{\circ}}{\cal
V}_{u}^{\circ}+\bigoplus_{e\in E\setminus\overline{E}}\Xi_{e}^{\cal
B}\oplus\bigoplus_{e\in\overline{E}}\bigoplus_{e^{\prime}\in
E^{e}}\Xi_{e^{\prime}}^{e\cal B}\oplus\Xi_{s}^{\cal B}\oplus\Xi_{t}^{\cal
B}\\\ &=\bigoplus_{u\in V}\widetilde{\Lambda}({\cal
V}_{u})\oplus\bigoplus_{e\in\overline{E}}\bigoplus_{u\in
V^{e}\setminus\\{s,t\\}}{\cal
V}_{u}^{e}+\oplus\bigoplus_{e\in\overline{E}}\bigoplus_{e^{\prime}\in\overline{E}^{e}}\Xi_{e^{\prime}}^{e\cal
B}.\end{split}$ (17)

##### Working Bases for $G^{\circ}$

By the assumptions of Definition 3.7, we have a working basis $\Psi_{{\cal
A}_{G}}$ for ${\cal A}_{G}$ of the form:

$\Psi_{{\cal A}_{G}}=\bigcup_{e\in E\cup B}\Psi_{{\cal A}_{G}}(e),$

where $\Psi_{{\cal A}_{G}}(e)$ is an orthonormal basis for $\Xi_{e}^{\cal A}$,
and similarly, for each $e\in\overline{E}$, we have a working basis
$\Psi_{{\cal A}_{G^{e}}}$ for ${\cal A}_{G^{e}}$ of the form:

$\Psi_{{\cal A}_{G^{e}}}=\bigcup_{e^{\prime}\in E^{e}\cup B^{e}}\Psi_{{\cal
A}_{G^{e}}}(e^{\prime}).$

Since the spaces $\Xi_{e}^{\circ\cal A}$ are simply inherited from the
corresponding spaces in $G$ and the $G^{e}$, their bases can be as well.
Specifically, we define a working basis

$\Psi_{{\cal A}_{G^{\circ}}}=\bigcup_{e\in E^{\circ}\cup B^{\circ}}\Psi_{{\cal
A}_{G^{\circ}}}(e)=\bigcup_{e\in(E\setminus\overline{E})\cup B}\Psi_{{\cal
A}_{G^{\circ}}}(e)\cup\bigcup_{e\in\overline{E}}\bigcup_{e^{\prime}\in
E^{e}}\Psi_{{\cal A}_{G^{\circ}}}(e^{\prime}).$

for ${\cal A}_{G^{\circ}}$, where for all $e\in E\setminus\overline{E}$,
$\Psi_{{\cal A}_{G^{\circ}}}(e)=\Psi_{{\cal A}_{G}}(e)$, and for all
$e\in\overline{E}$ and $e^{\prime}\in E^{e}$, $\Psi_{{\cal
A}_{G^{\circ}}}(e^{\prime})=\Psi_{{\cal A}_{G^{e}}}(e^{\prime})$. Then we have
the following.

######  Lemma 4.4 (Working Basis for ${\cal A}$).

$\Psi_{{\cal A}_{G^{\circ}}}$ can be generated in time $T+T^{\prime}+O(1)$.

###### Proof.

Assume without loss of generality that for $e\in\overline{E}$, $\Psi_{{\cal
A}_{G}}(e)$, which is one-dimensional, has label set $L(e)=\\{e\\}$. We let

$L_{\cal
A}^{\circ}=(\\{0\\}\times(L\setminus\overline{E}))\sqcup\bigsqcup_{e\in\overline{E}}\\{e\\}\times
L_{\cal A}^{e},$

so to map ${\lvert}\ell\rangle\mapsto{\lvert}b_{\ell}^{\circ}\rangle$ for
$\ell=(\ell_{0},\ell_{1})\in L^{\circ}$, we simply need to apply the relevant
basis generation map depending on the value of
$\ell_{0}\in\\{0\\}\cup\overline{E}$. We can check if
$\ell=(\ell_{0},\ell_{1})\in L_{\cal A}^{\circ}$ by membership in the relevant
set, controlled on $\ell_{0}$. For example, if $\ell_{0}=0$, we check if
$\ell_{1}\in L$, and $\ell_{1}\not\in\overline{E}$. ∎

By the assumptions of Definition 3.7, we have a working basis $\Psi_{{\cal
B}_{G}}$ for ${\cal B}_{G}$ of the form

$\Psi_{{\cal B}_{G}}=\Psi_{{\cal
B}_{G}}^{-}\cup\left\\{\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle):e\in\overline{E}\right\\},$

and similarly, for each $e\in\overline{E}$, we have a working basis
$\Psi_{{\cal B}_{G^{e}}}$ for ${\cal B}_{G^{e}}$ of the form

$\Psi_{{\cal B}_{G^{e}}}=\Psi_{{\cal
B}_{G^{e}}}^{-}\cup\left\\{\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e^{\prime}\rangle+{\lvert}\leftarrow,e^{\prime}\rangle):e^{\prime}\in\overline{E}^{e}\right\\},$

where $\Psi_{{\cal B}_{G^{e}}}^{-}\subseteq
H_{G^{e}}^{-}\colonequals\Xi_{B^{e}\cup
E^{e}\setminus\overline{E}^{e}}\oplus\mathrm{span}\\{{\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle:e\in\overline{E}^{e}\\}$
contains two distinguished vectors, ${\lvert}b_{0}^{e}\rangle$ and
${\lvert}b_{1}^{e}\rangle$. From these, we define the following isometry on
$H_{G}^{-}$:

$\Lambda\colonequals\Pi_{E\setminus\overline{E}}+\Pi_{B}+\sum_{e\in\overline{E}}\frac{1}{\sqrt{2}}{\lvert}\bar{b}_{1}^{e}\rangle({\langle}\rightarrow,e\rvert-{\langle}\leftarrow,e\rvert).$
(18)

Then we define:

$\Psi_{{\cal B}_{G}^{\circ}}=\underbrace{\Lambda(\Psi_{{\cal
B}_{G}}^{-})\cup\bigcup_{e\in\overline{E}}(\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\})}_{\equalscolon\Psi_{{\cal
B}_{G^{\circ}}}^{-}}\cup\Bigg{\\{}\underbrace{\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e^{\prime}\rangle+{\lvert}\leftarrow,e^{\prime}\rangle)}_{\Psi_{{\cal
B}_{G^{\circ}}}(e^{\prime}),\mbox{ spans }\Xi_{e^{\prime}}^{e\cal
B}}:e^{\prime}\in\overline{E}^{\circ}=\bigcup_{e\in\overline{E}}\overline{E}^{e}\Bigg{\\}}.$
(19)

In Appendix A, we prove that $\Psi_{{\cal B}_{G^{\circ}}}$ is indeed a basis
for ${\cal B}_{G^{\circ}}$. Again, this is actually not so important – we
could also have defined ${\cal B}_{G^{\circ}}$ from the basis, in which case,
we would not need the assumption, from canonical $st$-boundary, that the
spaces ${\cal V}_{s^{e}}^{e}$ and ${\cal V}_{t^{e}}^{e}$ are one-dimensional.
However, then it would not be obvious that any graph structure remains, which
we feel is beneficial for maintaining intuition when working with complicated
objects.

######  Lemma 4.5.

$\Psi_{{\cal A}_{G^{\circ}}}$ and $\Psi_{{\cal B}_{G^{\circ}}}$ are
$st$-composable bases as in Definition 3.7.

###### Proof.

The first two properties are clear, so we check properties 3-5. Since
$\Psi_{{\cal B}_{G}}$ is composable, $\Psi_{{\cal B}_{G}}^{-}$ contains
${\lvert}b_{0}\rangle=\frac{1}{\sqrt{2}}({\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle)$,
so $\Psi_{{\cal B}_{G^{\circ}}}^{-}$ contains

${\lvert}b_{0}^{\circ}\rangle=\Lambda({\lvert}b_{0}\rangle)=\frac{1}{\sqrt{2}}({\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle),$

establishing property 3 of Definition 3.7. Similarly, $\Psi_{{\cal
B}_{G}}^{-}$ contains ${\lvert}b_{1}\rangle=\frac{1}{\sqrt{2+{\sf
r}}}({\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle+\sqrt{{\sf
r}}{\lvert}\bar{b_{1}}\rangle)$, so $\Psi_{{\cal B}_{G^{\circ}}}^{-}$ contains

${\lvert}b_{1}^{\circ}\rangle=\Lambda({\lvert}b_{1}\rangle)=\frac{1}{\sqrt{2+{\sf
r}}}({\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle+\sqrt{{\sf
r}}\Lambda{\lvert}\bar{b_{1}}\rangle),$

establishing property 4 of Definition 3.7. Finally, it is easy to verify that
the remaining vectors of $\Psi_{{\cal B}_{G^{\circ}}}$ are orthogonal to
${\lvert}\leftarrow,s\rangle$ and ${\lvert}\rightarrow,t\rangle$, establishing
property 5. ∎

######  Lemma 4.6.

If the working basis $\Psi_{{\cal B}_{G}}$ has time complexity $T$, and for
each $e\in\overline{E}$, the working basis $\Psi_{{\cal B}_{G^{e}}}$ has time
complexity $T^{\prime}$, then $\Psi_{{\cal B}_{G^{\circ}}}$ has time
complexity $T+T^{\prime}+O(1)$.

###### Proof.

We have

$L_{\circ}=\underbrace{L^{-}\sqcup\bigsqcup_{e\in\overline{E}}L_{e}^{-}\setminus\\{0,1\\}}_{L_{\circ}^{-}}\sqcup\overline{E}^{\circ}.$

As always, for any label $e\in\overline{E}^{\circ}$, the mapping:

${\lvert}e\rangle\mapsto{\lvert}b_{e}^{\circ}\rangle=\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle)$

has time complexity $1$ (just apply a Hadamard).

For $\ell\in L^{-}_{e}\setminus\\{0,1\\}$ for some $e$, apply the map
${\lvert}\ell\rangle\mapsto{\lvert}b_{\ell}^{e}\rangle$ in cost $T^{\prime}$.

For $\ell\in L^{-}$, apply the map
${\lvert}\ell\rangle\mapsto{\lvert}b_{\ell}\rangle$ in cost $T$, and then use
the direct sum of basis maps for $\bar{\Psi}_{{\cal B}_{G^{e}}}^{-}$ to map:

$\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)\mapsto{\lvert}1,e\rangle\mapsto{\lvert}\bar{b}_{1}^{e}\rangle.\qed$

We complete the analysis by establishing positive and negative witnesses.

######  Lemma 4.7.

Let ${\lvert}w\rangle$ be a positive witness for $G$, so it necessarily only
overlaps switches that are on. For every switch $e$ that is on, let
${\lvert}w^{e}\rangle$ be a positive witness for $G^{e}$. Then

${\lvert}\hat{w}^{\circ}\rangle=\sum_{e\in\overline{E}}\sqrt{\frac{{\sf
r}^{e}}{2}}{{\langle}\rightarrow,e|}w\rangle{\lvert}\hat{w}^{e}\rangle+\Pi_{E\setminus\overline{E}}{\lvert}w\rangle$

is a positive witness for $G^{\circ}$.

###### Proof.

We need to show that
${\lvert}w^{\circ}\rangle={\lvert}s\rangle+{\lvert}\leftarrow,s\rangle+{\lvert}\hat{w}^{\circ}\rangle+{\lvert}\rightarrow,t\rangle+{\lvert}t\rangle$
is in ${\cal A}_{G^{\circ}}^{\bot}\cap{\cal B}_{G^{\circ}}^{\bot}$. We start
by showing that ${\lvert}w^{\circ}\rangle$ is orthogonal to everything in
${\cal A}_{G^{\circ}}$. Orthogonality with $\Xi_{s}^{\cal
A}=\mathrm{span}\\{{\lvert}s\rangle-{\lvert}\leftarrow,s\rangle\\}$ (see
Definition 3.5) is obvious. For $e\in E\setminus\overline{E}$,

$\Pi_{e}^{\cal A}{\lvert}w^{\circ}\rangle=\Pi_{e}^{\cal
A}\Pi_{E\setminus\overline{E}}{\lvert}w\rangle=\Pi_{e}^{\cal
A}{\lvert}w\rangle=0$

since ${\lvert}w\rangle\in{\cal A}_{G}^{\bot}$ (because it is a positive
witness). For all $e\in\overline{E}$ and $e^{\prime}\in E^{e}$,

$\Pi_{e^{\prime}}^{e\cal A}{\lvert}w^{\circ}\rangle=\sqrt{\frac{{\sf
r}^{e}}{2}}{{\langle}\rightarrow,e|}w\rangle{\Pi_{e^{\prime}}^{e\cal
A}{\lvert}\hat{w}^{e}\rangle}=\sqrt{\frac{{\sf
r}^{e}}{2}}{{\langle}\rightarrow,e|}w\rangle{\Pi_{e^{\prime}}^{e\cal
A}{\lvert}w^{e}\rangle}=0$

since ${\lvert}\hat{w}^{e}\rangle=(I-\Pi_{B^{e}}){\lvert}w^{e}\rangle$, and
$\Pi_{e^{\prime}}^{e\cal A}{\lvert}w^{e}\rangle=0$ because
${\lvert}w^{e}\rangle$ is a positive witness for $G^{e}$. Thus
${\lvert}w^{\circ}\rangle\in{\cal A}_{G^{\circ}}^{\bot}$.

By an identical proof, we can show that ${\lvert}w^{\circ}\rangle$ is
orthogonal to $\Xi_{e}^{\cal B}$ for all $e\in E\setminus\overline{E}$, and
$\Xi_{e^{\prime}}^{e\cal B}$ for all $e\in\overline{E}$ and $e^{\prime}\in
E^{e}$. Thus, it remains only to show orthogonality with $\Psi_{{\cal
B}_{G^{\circ}}}^{-}$.

Note that since
${\lvert}b_{1}\rangle\propto{\lvert}\leftarrow,s^{e}\rangle-{\lvert}\rightarrow,t^{e}\rangle+\sqrt{{\sf
r}^{e}}{\lvert}\bar{b}_{1}^{e}\rangle\in{\cal B}_{G^{e}}$, we must have

$\displaystyle\left({\langle}\leftarrow,s^{e}\rvert-{\langle}\rightarrow,t^{e}\rvert+\sqrt{{\sf
r}^{e}}{\langle}\bar{b}_{1}^{e}\rvert\right)\left({\lvert}s^{e}\rangle-{\lvert}\leftarrow,s^{e}\rangle+{\lvert}\hat{w}^{e}\rangle+{\lvert}\rightarrow,t^{e}\rangle-{\lvert}t^{e}\rangle\right)$
$\displaystyle=0$ $\displaystyle\sqrt{{\sf
r}^{e}}{{\langle}\bar{b}_{1}^{e}|}\hat{w}^{e}\rangle$ $\displaystyle=2.$

Thus:

$\begin{split}\Lambda^{\dagger}{\lvert}{\hat{w}}^{\circ}\rangle&=\sum_{e\in\overline{E}}\sqrt{\frac{{\sf
r}^{e}}{2}}{{\langle}\rightarrow,e|}w\rangle{\Lambda^{\dagger}{\lvert}\hat{w}^{e}\rangle}+\Pi_{E\setminus\overline{E}}{\lvert}w\rangle\\\
&=\sum_{e\in\overline{E}}\sqrt{\frac{{\sf
r}^{e}}{2}}{{\langle}\rightarrow,e|}w\rangle{{\langle}\bar{b}_{1}^{e}|}\hat{w}^{e}\rangle\frac{1}{\sqrt{2}}\left({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle\right)+\Pi_{E\setminus\overline{E}}{\lvert}w\rangle\\\
&=\sum_{e\in\overline{E}}\sqrt{\frac{{\sf
r}^{e}}{2}}{{\langle}\rightarrow,e|}w\rangle\frac{2}{\sqrt{{\sf
r}^{e}}}\frac{1}{\sqrt{2}}\left({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle\right)+\Pi_{E\setminus\overline{E}}{\lvert}w\rangle\\\
&=\sum_{e\in\overline{E}}{{\langle}\rightarrow,e|}w\rangle\left({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle\right)+\Pi_{E\setminus\overline{E}}{\lvert}w\rangle\\\
&=\Pi_{\overline{E}}{\lvert}w\rangle+\Pi_{E\setminus\overline{E}}{\lvert}w\rangle={\lvert}\hat{w}\rangle,\end{split}$
(20)

where we used the fact that
${{\langle}\rightarrow,e|}w\rangle=-{{\langle}\leftarrow,e|}w\rangle$. It
follows that $\Lambda^{\dagger}{\lvert}w^{\circ}\rangle={\lvert}w\rangle$, and
thus we have, for any ${\lvert}\psi\rangle\in\Psi_{{\cal B}_{G}}^{-}$,

${\langle}\psi\rvert\Lambda^{\dagger}{\lvert}w^{\circ}\rangle={{\langle}\psi|}w\rangle=0,$
(21)

since ${\lvert}w\rangle$ is a positive witness for $G$. To complete the proof,
we show orthogonality with $\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}$
for any $e\in\overline{E}$. ${\cal B}_{G^{e}}$ is orthogonal to
${\lvert}s^{e}\rangle$ and ${\lvert}t^{e}\rangle$, and furthermore, for $i>1$,
we have
${{\langle}\leftarrow,s^{e}|}b_{i}^{e}\rangle={{\langle}\rightarrow,t^{e}|}b_{i}^{e}\rangle=0$.
We have:

$\displaystyle{{\langle}b_{i}^{e}|}w^{\circ}\rangle=\sqrt{\frac{{\sf
r}^{e}}{2}}{{\langle}\rightarrow,e|}w\rangle{{\langle}b_{i}^{e}|}\hat{w}^{e}\rangle.$

Since ${\lvert}\hat{w}^{e}\rangle$ is a cropped positive witness for $G^{e}$,
we have:

$0={{\langle}b_{i}^{e}|}w\rangle={{\langle}b_{i}^{e}|}s\rangle-{{\langle}b_{i}^{e}|}\leftarrow,s\rangle+{{\langle}b_{i}^{e}|}\hat{w}^{e}\rangle+{{\langle}b_{i}^{e}|}\rightarrow,t^{e}\rangle-{{\langle}b_{i}^{e}|}t\rangle={{\langle}b_{i}^{e}|}\hat{w}^{e}\rangle,$

completing the proof. ∎

######  Lemma 4.8.

Let ${\lvert}w_{\cal A}\rangle$ be a negative witness for $G$ that only
overlaps switches that are off (this is always true for optimal witnesses,
because when a switch is on $\Xi_{e}^{\cal B}=\Xi_{e}^{\cal A}$, so might as
well put any overlap with $\Xi_{e}$ into ${\lvert}w_{\cal B}\rangle$). For
every switch $e\in\overline{E}$ that is off, let ${\lvert}w_{\cal
A}^{e}\rangle$ be a negative witness for $G^{e}$. Then:

${\lvert}\hat{w}_{\cal