# Quantum Subroutine Composition

Stacey Jeffery This work is supported by ERC STG grant 101040624-ASC-Q, NWO
Klein project number OCENW.Klein.061, and ARO contract no W911NF2010327. SJ is
a CIFAR Fellow in the Quantum Information Science Program.

###### Abstract

An important tool in algorithm design is the ability to build algorithms from
other algorithms that run as subroutines. In the case of quantum algorithms, a
subroutine may be called on a superposition of different inputs, which
complicates things. For example, a classical algorithm that calls a subroutine
${\sf Q}$ times, where the average probability of querying the subroutine on
input $i$ is $\bar{p}_{i}$, and the cost of the subroutine on input $i$ is
$T_{i}$, incurs expected cost ${\sf Q}\sum_{i}\bar{p}_{i}\mathbb{E}[T_{i}]$
from all subroutine queries. While this statement is obvious for classical
algorithms, for quantum algorithms, it is much less so, since naively, if we
run a quantum subroutine on a superposition of inputs, we need to wait for all
branches of the superposition to terminate before we can apply the next
operation. We nonetheless show an analogous quantum statement (*): If
$\bar{q}_{i}$ is the average _query weight on $i$_ over all queries, the cost
from all quantum subroutine queries is ${\sf
Q}\sum_{i}\bar{q}_{i}\mathbb{E}[T_{i}]$. Here the query weight on $i$ for a
particular query is the probability of measuring $i$ in the input register if
we were to measure right before the query.

We prove this result using the technique of multidimensional quantum walks,
recently introduced in [Jeffery, Zur 2022]. We present a more general version
of their quantum walk edge composition result, which yields _variable-time
quantum walks_ , generalizing variable-time quantum search, by, for example,
replacing the update cost with
$\sqrt{\sum_{u,v}\pi_{u}P_{u,v}\mathbb{E}[T_{u,v}^{2}]}$, where $T_{u,v}$ is
the cost to move from vertex $u$ to vertex $v$. The same technique that allows
us to compose quantum subroutines in quantum walks can also be used to compose
in any quantum algorithm, which is how we prove (*).

##  1 Introduction

Classical algorithms make extensive use of subroutines, which allow an
algorithm designer to build up an algorithm in modular blocks. Analysis of
such algorithms can also be done in a simple, modular way. Suppose an outer
classical algorithm makes use of some subroutine at ${\sf Q}$ steps of the
algorithm, and suppose the subroutine’s stopping time on input $i$ is some
random variable $T_{i}$. Suppose $\bar{p}_{i}$ is the average probability,
over all ${\sf Q}$ queries to the subroutine, that the subroutine is called on
input $i$ – so ${\sf Q}\bar{p}_{i}$ is the expected number of times the
subroutine is called on input $i$, and $\sum_{i}\bar{p}_{i}=1$. Let ${\sf L}$
denote the total number of _other_ operations used by the outer algorithm.
Then the expected running time of the classical algorithm is:

${\sf L}+{\sf Q}\sum_{i}\bar{p}_{i}\mathbb{E}[T_{i}].$ (1)

We can get a bounded-error algorithm with this asymptotic running time by
simply stopping after 10 times the expected number of steps, if the algorithm
has not already halted, and outputting an arbitrary (likely wrong) answer,
which happens with probability at most some small constant.

While subroutines are also quite useful in quantum algorithms, it is not at
all obvious how to do the above classical analysis in a quantum setting.
Suppose an outer quantum algorithm makes use of some subroutine. In general,
the subroutine will be called on a superposition of inputs $i$, so if some
branches of the superposition are finished early, it is not obvious how to
exploit this in the overall complexity. Generally, if ${\sf T}_{\max}$ is the
maximum time we must wait for the quantum subroutine to terminate, the total
complexity of the quantum algorithm is:

$O({\sf L}+{\sf Q}\cdot{\sf T}_{\max}),$ (2)

where again, ${\sf Q}$ is the number of queries to the subroutine, and ${\sf
L}$ is the number of other operations made by the outer algorithm. Our main
result is to give a quantum analogue of (1). Given a quantum algorithm that
decides $f$ using ${\sf L}$ basic operations, as well as ${\sf Q}$ queries to
a subroutine that runs in time $T_{i}$ on input $i$ to compute some bit
$g_{i}$, there is a bounded error quantum algorithm that computes $f(g)$ with
complexity (neglecting log factors):

${\sf L}+{\sf Q}\sum_{i}\bar{q}_{i}\mathbb{E}[T_{i}],$

where $\bar{q}_{i}$ is the _average query weight on $i$_ – the squared norm on
${\lvert}i\rangle$ averaged over all queries, so in particular,
$\sum_{i}\bar{q}_{i}=1$. We describe the result in more detail in Section 1.2.
While such a result is obvious in classical algorithms, it is much less so in
quantum algorithms. In fact, if the outer algorithm and subroutine are zero-
error algorithms, and we want to compose them to get a zero-error algorithm
with this _expected_ running time, while again obvious in the classical case,
this is _not_ possible in general for quantum algorithms [BdW03].

If $\mathbb{E}[T_{i}]=\mu$ is a known constant (in $i$), then this result is
much less interesting: we can always stop the subroutine after $10\mu$ steps,
and by Markov’s inequality, this introduces at most $1/10$ additional
probability of error (which we can reduce through logarithmic repetitions).
However, if the values $\mathbb{E}[T_{i}]$ vary significantly in $i$, in
contrast to the classical case, it is not obvious (to the best of our
knowledge) that this result should hold for quantum algorithms, and special
cases of this result have been the subject of significant effort.

For example, consider evaluating an unbalanced formula that is the OR of $n$
ANDs, of arity $k_{1},\dots,k_{n}$:

$f(x^{(1)},\dots,x^{(n)})=\mathrm{OR}_{n}(\mathrm{AND}_{k_{1}}(x^{(1)}),\dots,\mathrm{AND}_{k_{n}}(x^{(n)})),$

where $x^{(j)}\in\\{0,1\\}^{k_{j}}$. Naively, using nested quantum search, one
could search for a $j$ such that AND${}_{k_{j}}(x^{(j)})=1$, where
AND${}_{k_{j}}(x^{(j)})$ can be evaluated in $\sqrt{k_{j}}$ steps, for total
cost $\sqrt{n}\cdot\max_{j\in[n]}\sqrt{k_{j}}$ (we neglect log factors in this
paragraph), but this may be far from optimal. However, using highly non-
trivial techniques, it has been shown how to evaluate any such formula in
$\sqrt{n}\sqrt{\frac{1}{n}\sum_{j=1}^{n}k_{j}}$ quantum time or _any_ AND-OR
formula on $N$ bits in $\sqrt{N}$ time [ACR+07, Rei11a].

This non-trivial upper bound for OR of ANDs can be seen as a special case of a
technique called _variable-time quantum search_. Consider a setting in which a
quantum subroutine runs in time ${\sf T}_{i}$ on input $i$, and one wants to
decide if there exists an $i\in[n]$ on which the subroutine outputs 1.
Classically, it is easy to see that this can be decided in cost
$\sum_{i\in[n]}{\sf T}_{i}$. Naive use of quantum search gives an upper bound
of $\sqrt{n}{\sf T}_{\max}$, where ${\sf T}_{\max}=\max_{i\in[n]}{\sf T}_{i}$.
Ambainis showed, in a highly non-trivial way, an upper bound of
$\widetilde{O}\left(\sqrt{\sum_{i=1}^{n}{\sf T}_{i}^{2}}\right)$ [Amb10]. This
result assumes that if the $i$-th subroutine consists of unitaries
$U_{1}^{i},\dots,U_{{\sf T}_{\max}}^{i}$, the operator $\sum_{t=1}^{{\sf
T}_{\max}}{\lvert}t\rangle{\langle}t\rvert\otimes U_{t}^{i}$ can be
implemented in “unit cost”. We will make this assumption as well, throughout
this paper, and 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_{{\sf T}_{\max}}^{i}$ are arbitrary gates
(local unitaries), but it holds, for example, in the _fully quantum_ QRAM
model if $U_{1}^{i},\dots,U_{{\sf T}_{\max}}^{i}$ are stored as a list of
gates in QCRAM111Classical 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 [JZ22, Section 2.2]).

In [Amb12], Ambainis considers a slightly different setting, where a quantum
subroutine runs in time $T$, where $T$ is a random variable on
$\\{1,\dots,{\sf T}_{\max}\\}$ – that is, the algorithm may stop at different
times with different probabilities, outputting either a 0 or 1 in some answer
register whenever it stops. Ambainis shows how to amplify the 1 part of the
computation in complexity (neglecting log factors):

${\sf T}_{\max}+\sqrt{\frac{\mathbb{E}[T^{2}]}{\varepsilon}}$

where $\varepsilon$ is a lower bound on the probability that the algorithm
outputs 1 (assuming this is non-zero).

We consider a combination of Ambainis’ two settings, where a subroutine
computes some bit $g_{i}$ for any input $i$, and the time it takes is a random
variable $T_{i}$ on $\\{1,\dots,{\sf T}_{\max}\\}$. When the expected stopping
times $\mathbb{E}[T_{i}]$ are unknown, and $\varepsilon$ is a lower bound on
the probability in uniform input $i$ that the subroutine outputs 1, we obtain
(neglecting log factors)

$\sqrt{\frac{1}{n\varepsilon}\sum_{i\in[n]}\mathbb{E}[T_{i}^{2}]}.$ (3)

When the expected stopping times $\mathbb{E}[T_{i}]$ are known, we can replace
$\mathbb{E}[T_{i}^{2}]$ with $\mathbb{E}[T_{i}]^{2}$, which is better when
$T_{i}$ has large variance, and improve, but not remove, the polylogarithmic
dependence on ${\sf T}_{\max}$. We also show two alternative variable-time
search results that may be better in certain settings. Our variable-time
search results are a special case of a new technique: variable-time quantum
walk algorithms. Loosely speaking, if the cost of moving from a vertex $u$ to
a vertex $v$ in a random walk on a graph $G$ is some random variable $T_{u,v}$
on $\\{1,\dots,{\sf T}_{\max}\\}$, previous quantum walk search algorithms
would have incurred a multiplicative overhead on the complexity of ${\sf
T}_{\max}$. We show how to improve this overhead to $\sqrt{\sum_{\\{u,v\\}\in
E(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]}$, where $P$ is the transition
matrix of the random walk, and $\pi$ is its stationary distribution. We show a
similar variable-time dependence on the _checking cost_. We describe our
variable-time quantum search and variable-time quantum walk results in Section
1.1.

##### Techniques:

Our results build on multidimensional quantum walks, recently described in
[JZ22]. Given a collection of states, each of which can be efficiently
prepared, and therefore reflected around, we can define an _overlap graph_ ,
with one node for every state, and a pair of nodes adjacent if and only if the
states overlap. If this graph is bipartite, with bipartition $V_{\cal
A},V_{\cal B}$, then reflections around the states in $V_{\cal A}$ (resp.
$V_{\cal B}$) commute, and so we can also efficiently reflect around the span
of all states in $V_{\cal A}$, and around the span of all states in $V_{\cal
B}$. Then sufficiently precise phase estimation of the product of these two
reflections can be used to reflect around the span of _all_ states. When the
states are _quantum walk states_ for some graph $G$:
${\lvert}\psi_{\star}^{G}(u)\rangle=\sum_{v:\\{u,v\\}\in
E(G)}\sqrt{P_{u,v}}{\lvert}\\{u,v\\}\rangle$, then
${\lvert}\psi_{\star}^{G}(u)\rangle$ and ${\lvert}\psi_{\star}^{G}(v)\rangle$
overlap if and only if $\\{u,v\\}\in G$, so the overlap graph of these states
is exactly $G$. Quantum walk search algorithms, like those we describe shortly
in Section 1.1, use analysis of the properties of the graph $G$ to analyze
what precision of phase estimation is needed to reflect around the span of all
states.

Ref. [JZ22] extends this idea to a set of _spaces_ that can be efficiently
reflected around. If $\\{\Psi_{u}\\}_{u\in V}$ is a set of subspaces of some
inner product space $H$, we can define an overlap graph on $V$, with an edge
between $u$ and $v$ whenever $\Psi_{u}$ and $\Psi_{v}$ are non-orthogonal.
Just as in the case when each space is one-dimensional, if the overlap graph
is bipartite, a bipartition gives rise to two efficiently implementable
reflections, whose product can be used to reflect around the span of all the
spaces using sufficiently precise phase estimation. The properties of the
overlap graph can be used to bound the required precision.

Ref. [JZ22] use this idea in two ways. The first is the technique of
_alternative neighbourhoods_ , which is orthogonal to the ideas of this paper:
we do not deal with this technique here for simplicity, but there is no reason
it could not be used simltaneously with our techniques. This work builds on
the second technique, called _edge composition_ 222which is similar to the
concurrent, independent technique of _graph composition_ of span programs
[Cor23].. Suppose there is a subroutine that implements a step of the quantum
walk: for now imagine some reversible version of moving from $u$, to some
neighbour $v$, in cost ${\sf T}_{u,v}$. Then implementing the reflection
around the states $\\{{\lvert}\psi_{\star}^{G}(u)\rangle\\}_{u\in V_{\cal A}}$
costs $\max_{u,v}{\sf T}_{u,v}$. The edge composition technique uses the
random walk and the subroutine to define, for each $\\{u,v\\}\in E$, a
sequence of ${\sf T}_{u,v}$ spaces whose overlap graph is similar to $G$, but
each edge is replaced by a path of length ${\sf T}_{u,v}$ (see Figure 1). Our
quantum walk composition described in Section 1.1 is similar, except that we
allow the subroutine to have a variable, unknown stopping time, and then we
describe spaces whose overlap graph looks like $G$, but in place of an edge
$\\{u,v\\}$, there is a ladder-like gadget (see Figure 1), where we can
imagine getting from $u$ to $v$ by going up one side (representing
computation) and that at various “rungs” with various probabilities, crossing
to the other side of the ladder and uncomputing. By increasing or decreasing
the “weights” ($\\{\alpha_{t}\\}_{t}$ in Theorem 4.1) as the ladder goes up,
we can get various variable-time complexities without knowing the total
lengths of the ladders.

Our result for general algorithmic composition (Section 1.2) uses the same
ideas, but within an algorithm rather than a graph. This can be done by
defining a sequence of spaces from the outer algorithm whose overlap graph is
a line of length ${\sf L}$, and then plugging in ladder-like gadgets like
those in Figure 1 wherever there is a subroutine query (see Figure 4).

$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$ Figure
1: Instead of using a $T_{u,v}$ step quantum algorithm for the transition from
$u$ to $v$ to build a “bridge” from $u$ to $v$ that functions like a path of
length $T_{u,v}$ (left), we use a variable-time quantum algorithm to put a
ladder-like gadget between $u$ and $v$ (right). The rungs of the ladder
correspond to the steps of the quantum algorithm, and intuitively, we should
think of the weight of each rung as corresponding to the probability that the
algorithm terminates at that step.

##### Comparison with Previous and Concurrent Work:

Aside from the special cases of formula evaluation and variable-time search
already mentioned, previous work in composing quantum algorithms in non-
trivial ways has mainly been restricted to the model of query complexity.
_Span programs_ can be composed in various nice ways [RŠ12, Rei11b], for
example, to evaluate formulas in various gate sets with a quantum query
complexity that amortizes nicely – a fact exploited in [CKKD+22] (concurrent
with this work) to analyze the quantum query complexity of divide-and-conquer
algorithms. It is also rather simple to get a version of Ambainis’ variable-
time search result that applies only to query complexity using span program
composition. Ref. [CJOP20] showed how to extend span program composition to
time complexity, also reproducing Ambainis’ variable-time search in a time-
efficient way using span program composition. The main idea of [CJOP20] allows
span programs, also known as _dual adversary solutions_ , to maintain time
complexity structure where it is given, whereas previously span programs were
only used to study query complexity. The techniques of [CJOP20] are the basis
for characterizing time complexty in [JZ22], and now in this work as well.

In a concurrent, independent work, Belovs and Yolcu defined the notion of
quantum Las Vegas query complexity, and in particular, showed a version of our
main theorem (Theorem 1.1) that applies only to query complexity [BY23]. While
their results do not apply to time complexity, they work with a significantly
more general class of subroutines. While we assume subroutines compute a
single bit (which easily extends to any classical function), their results
work for subroutines that enact arbitrary state conversion, or even non-
unitary maps. Their techniques are quite novel, and distinct from ours.

###  1.1 Quantum Walk Composition

Quantum walk search algorithms were first introduced by Szegedy [Sze04] who
showed the following. Let $P$ be the transition matrix of a random walk on a
graph $G$ with stationary distribution $\pi$, and $M\subset V(G)$ a _marked
set_ , both of which may implicitly depend on some input $x$ – we write, for
example $M_{x}$ when we want to make this dependence explicit. Let ${\cal H}$
be a known bound such that whenever $M\neq\emptyset$, we are promised that the
hitting time to $M$ – the expected number of steps needed by a classical
random walk starting in the distribution $\pi$ to reach some $u\in M$ – is at
most ${\cal H}$. Then there is a quantum algorithm that decides, with bounded
error, if $M=\emptyset$, which starts by generating an initial state
$\sum_{u}\sqrt{\pi(u)}{\lvert}u\rangle$, and then makes some number
$\sqrt{\cal H}$ calls to a subroutine whose main components are: (1) for any
$u\in V(G)$, generating the quantum walk state
$\sum_{v}\sqrt{P_{u,v}}{\lvert}u,v\rangle$, which can be seen as the quantum
analogue of taking a random walk step (and are essentially the states
${\lvert}\psi_{\star}^{G}(u)\rangle$ mentioned above); (2) for any $u\in
V(G)$, checking if $u\in M$. In early work, the most important parameter in
the complexity was $\sqrt{\cal H}$ – a generic quadratic speedup over the
analogous classical algorithm – and it was assumed that other operations, such
as generating the quantum walk states had unit cost. In later applications,
these operations often had non-trivial costs, impacting the complexity in
different ways. Generally ${\sf S}$ is used to denote the cost of generating
$\sum_{u}\sqrt{\pi(u)}{\lvert}u\rangle$, ${\sf U}$ the cost of generating the
quantum walk states, and ${\sf C}$ the cost of checking if $u\in M$. In our
work, we will subdivide the task of generating quantum walk states. We suppose
(as is common in classical random walk algorithms) that for each $u\in V(G)$,
there is a set of labels $L(u)$, for example, $L(u)=[d_{u}]$, and a mapping
$f_{u}:L(u)\rightarrow V$ such that $f_{u}(i)$ is the $i$-th neighbour of $u$.
Then the following two subroutines can be used in place of generating quantum
walk states (this is not entirely obvious):

  1. 1.

Sampling: For each $u\in V$, generate $\sum_{i\in
L(u)}\sqrt{P_{u,f_{u}(i)}}{\lvert}i\rangle$. We assume this can be done in
unit cost.

  2. 2.

Transitions: For $\\{u,v\\}\in E(G)$ with $f_{u}(i)=v$ and $f_{v}(j)=u$, map
${\lvert}u,i\rangle\mapsto{\lvert}v,j\rangle$, in cost $T_{u,v}$, which is a
random variable on $[{\sf T}_{\max}]$.

In all applications that we know of, sampling has at most polylogarithmic
cost, and it is the transition that may be expensive.333For example, in
algorithms for triangle finding there is often a quantum walk step where the
sampling step consists of selecting a new vertex of the input graph (not the
graph being walked on) to add to a stored set of vertices, but to complete the
transition, it is necessary to find all neighbours of the new vertex in the
already stored set. We can also suppose the checking cost is variable, with
random variable $C_{u}$ on $[{\sf C}_{\max}]$ representing the cost of
checking if $u$ is marked. With this notation in place, the complexity of a
Szegedy walk is

${\sf S}+\sqrt{\cal H}({\sf T}_{\max}+{\sf C}_{\max}).$ (4)

Belovs generalized Szegedy’s framework to the _electric network framework_
[Bel13] (published in [BCJ+13]), in which the walk may start in any
distribution $\sigma$. If ${\sf S}_{\sigma}$ is the cost of generating
${\lvert}\sigma\rangle=\sum_{u}\sqrt{\sigma(u)}{\lvert}u\rangle$ (so ${\sf
S}={\sf S}_{\pi}$ above), and ${\cal C}_{\sigma,{\sf M}}$ is an upper bound on
a quantity ${\cal C}_{\sigma,M}(G)$, then Belovs exhibited a quantum algorithm
for deciding if $M=\emptyset$ with complexity

${\sf S}_{\sigma}+\sqrt{{\cal C}_{\sigma,{\sf M}}}({\sf T}_{\max}+{\sf
C}_{\max}).$ (5)

Let us say more about this quantity ${\cal C}_{\sigma,M}(G)$. If ${\cal W}(G)$
is the _total weight_ of $G$ (the number of edges when $G$ is unweighted) and
${\cal R}_{\sigma,M}(G)$ is the _effective resistance_ between $\sigma$ and
$M$ (see Definition 2.4), then ${\cal C}_{\sigma,M}(G)=2{\cal W}(G){\cal
R}_{\sigma,M}(G)$. This is probably not a very helpful definition, so we
mention some special cases that give some intuition. If $\sigma=\pi$ is the
stationary distribution, then ${\cal C}_{\pi,M}(G)$ is just the hitting time
from $\pi$ to $M$, and we recover the Szegedy framework. If $\sigma$ is
supported on a single vertex $s$, then ${\cal C}_{s,M}(G)$ is the _commute
time_ or expected number of steps starting from $s$, to get to any vertex in
$M$ and then return to $s$ [CRR+96] (see [AGJ20] for a proof of the case when
$|M|>1$, which was previously folklore).

Another framework, incomparable to Szegedy’s, is the MNRS framework [MNRS11],
in which the walk must start in the stationary distribution $\pi$, but the
cost is:

${\sf S}_{\pi}+\frac{1}{\sqrt{\varepsilon}}\left(\frac{1}{\sqrt{\delta}}{\sf
T}_{\max}+{\sf C}_{\max}\right),$ (6)

where $\delta$ is the _spectral gap_ of $P$, and $\varepsilon$ is a lower
bound on $\pi(M)=\sum_{u\in M}\pi(u)$. This framework has different dependence
on the cost of transitions and the cost of checking, since the checking
subroutine is run less frequently. Since the hitting time is between
$\frac{1}{\varepsilon}$ and $\frac{1}{\varepsilon\delta}$, this may be better
or worse than a Szegedy walk, depending on the relative values of ${\sf
T}_{\max}$ and ${\sf C}_{\max}$. In [AGJ20], the electric network framework
was extended to be able to not only detect if $M\neq\emptyset$, but to _find_
an element of $M$ as well, and this extension was shown to also include the
MNRS framework as a special case – simulating an MNRS walk with a walk whose
hitting time is $1/\varepsilon$, and update cost is ${\sf
T}_{\max}/\sqrt{\delta}$. In this paper, we do not consider finding a marked
vertex, but only detecting if there exists a marked vertex.

Finally, a result of Dohotaru and Høyer [DH17] shows how to achieve an optimal
number of both checking and update steps in the special case where $|M|\leq
1$, obtaining complexity:

${\sf S}_{\pi}+\sqrt{\cal H}{\sf T}_{\max}+\frac{1}{\sqrt{\varepsilon}}{\sf
C}_{\max}.$ (7)

Previously, quantum walk applications have used various tricks to handle the
case when the transitions can have different complexities. The MNRS framework
is already one means of handling the case when the checking cost is much
larger than the update cost. Nested quantum walks [JKM12, CJKM13], where the
checking or update is implemented by another quantum walk subroutine, can be
seen as one large quantum walk with multiple types of update operations with
different costs. Variable-time search has also been used _within_ the checking
subroutine of a quantum walk [LG14]. The most common method for handling
variability in the transition or checking cost has been through the use of
tail bounds, but this only works when the cost is highly concentrated around
the average. In the special case of MNRS quantum walks on _Johnson graphs_ ,
where subroutines are restricted to being in the framework of _extended
learning graphs_ and the measure of complexity is query complexity rather than
time complexity, [CLM20] showed how to replace ${\sf T}_{\max}$ and ${\sf
C}_{\max}$ with $\ell_{2}$-averages, also getting an average in the setup cost
${\sf S}_{\pi}$, in a way that is specific to Johnson graphs. While Johnson
graphs are quite a specific case, almost all known MNRS quantum walk
algorithms work on Johnson graphs.

The recent work of [JZ22], on whose techniques our results are heavily based,
achieves an improvement on the electric network framework (and by extension,
its special cases) as follows. Suppose the transition algorithm, rather than
having random stopping times, stops after a known time ${\sf T}_{u,v}\leq{\sf
T}_{\max}$ on input $(u,i)$, where $f_{u}(i)=v$. The value ${\sf T}_{u,v}$
must be computable from $(u,i)$, but also from $(v,j)$, where $f_{v}(j)=u$.
Suppose checking can be done in unit cost. Then there is a quantum algorithm
that decides if $M=\emptyset$ in complexity

${\sf S}_{\sigma}+\sqrt{{\cal C}_{\sigma,{\sf M}}^{\sf T}},$ (8)

where ${\cal C}_{\sigma,{\sf M}}^{\sf T}$ is an upper bound on ${\cal
C}_{\sigma,M}(G^{\sf T})$, where $G^{\sf T}$ is the graph $G$ where every edge
$\\{u,v\\}$ has been replaced by a path of length ${\sf T}_{u,v}$. This is
already a huge improvement over having worst case ${\sf T}_{\max}$ complexity.
The results presented in this section are based on a generalization of the
results in [JZ22], and a careful analysis of their implications.

##### Variable-time Quantum Walks:

We now state our results. For simplicity, we begin by stating our results in
the case that checking has unit cost. This is without loss of generality,
since we can always add extra edges to the graph from a vertex $u$ to a new
vertex that includes a bit indicating if $u\in M$, although this change to the
graph changes parameters such as hitting time. In that case, we can simply
replace ${\sf T}_{\max}$ with a weighted $\ell_{2}$ average, weighted by
$\pi(u)P_{u,v}$, which is the proportion of time spent traversing edge $(u,v)$
in an infinitely long random walk starting from any distribution, to get
complexity (see Corollary 4.2):

${\sf S}_{\sigma}+\sqrt{{\cal C}_{\sigma,{\sf
M}}}\sqrt{\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]}\log^{1.5}{\sf
T}_{\max}.$ (9)

Above, $\overrightarrow{E}(G)$ is the set of all edges, assigned some
arbitrary orientation (see Definition 2.1). If we further assume that the
values $\mathbb{E}[T_{u,v}]$ are computable in some strong sense (see
Corollary 4.2), then there is a quantum algorithm that decides if
$M=\emptyset$ with bounded error in complexity:

${\sf S}_{\sigma}+\sqrt{{\cal C}_{\sigma,{\sf
M}}}\sqrt{\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}]^{2}}\log{\sf
T}_{\max}.$ (10)

Aside from the log factor improvement, (10) is better when the variances of
$T_{u,v}$ are large, as
$\mathrm{Var}(T_{u,v})=\mathbb{E}[T_{u,v}^{2}]-\mathbb{E}[T_{u,v}]^{2}\geq 0$.
The expressions in (9) and (10) should be compared with the electric network
framework, (5) (or (4) in the special case when $\sigma=\pi$, and so ${\cal
C}_{\sigma,{\sf M}}={\cal H}$), and the graph composition in (8), although
comparison with (8) is more difficult. These results follow from a more
general statement (Theorem 4.1) of which a version of (8) where the transition
subroutine may have variable stopping times, and the values
$\mathbb{E}[T_{u,v}]$ need not be known in advance, also follows as a special
case. As we discuss further below, in some cases, the expressions in (9) and
(10) are better, whereas in some cases the expression in (8) is better, but
analysis of (9) and (10) may be easier, since we can work with the original
graph $G$, and need not analyze a modified graph $G^{\sf T}$.

As stated above, the checking cost can be made part of the update cost by
adding a new edge to each vertex $u$, whose other endpoint encodes $u$ and a
bit indicating if $u\in M$, and whose transition cost is $C_{u}$. For
comparison with previous work, we work out what impact this might have on the
complexity. For comparison with the MNRS framework, we restrict our attention
to initial distribution $\sigma=\pi$. Then we can decide if $M=\emptyset$ in
complexity (see Corollary 4.3):

${\sf
S}_{\pi}+\frac{1}{\sqrt{\varepsilon}}\left(\frac{1}{\sqrt{\delta}}\sqrt{\sum_{(u,v)\in\overrightarrow{E}}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]}+\sqrt{\sum_{u\in
V(G)}\pi(u)\mathbb{E}[C_{u}^{2}]}\right)\log^{.5}\frac{1}{\pi_{\min}}\log^{1.5}\left({\sf
T}_{\max}{\sf C}_{\max}\right),$ (11)

where $\pi_{\min}=\min_{u}\pi(u)$. Compared to the complexity achieved by the
MNRS framework in (6), ignoring log factors, we have replaced ${\sf T}_{\max}$
and ${\sf C}_{\max}$ with weighted $\ell_{2}$-averages. This also generalizes
the results of [CLM20] from Johnson graphs to general graphs, learning graphs
to arbitrary subroutines, and query complexity to time complexity. As before,
if the values $\mathbb{E}[C_{u}]$ and $\mathbb{E}[T_{u,v}]$ are computable in
some strong sense, then we can replace $\mathbb{E}[T_{u,v}^{2}]$ with
$\mathbb{E}[T_{u,v}]^{2}$ and $\mathbb{E}[C_{u}^{2}]$ with
$\mathbb{E}[C_{u}]^{2}$, and shave off a $\sqrt{\log}$ factor. For more
general initial distributions, see Corollary 4.2.

In the simpler case where $|M|\leq 1$, we can once again consider a more
general starting distribution $\sigma$. In that case, we get a variable-time
analogue of the results of Dohotaru and Høyer in (7), but even more general.
Specifically, let $\tau$ be _any_ distribution on $V(G)$ such that we are
promised that if $M=\\{m\\}\neq\emptyset$, then $\tau(m)\geq\varepsilon$. Then
we can decide if $M=\emptyset$ in complexity (see Corollary 4.2):

${\sf S}_{\sigma}+\left(\sqrt{{\cal C}_{\sigma,{\sf
M}}}\sqrt{\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]}+\frac{1}{\sqrt{\varepsilon}}\sum_{u\in
V(G)}\tau(u)\mathbb{E}[{C}_{u}^{2}]\right)\log^{1.5}\left({\sf T}_{\max}{\sf
C}_{\max}\right).$

When $\sigma=\tau=\pi$, so ${\cal C}_{\sigma,{\sf M}}={\cal H}$, we get a
variable-time version of the Dohotaru-Høyer result in (7). As before, if the
values $\mathbb{E}[C_{u}]$ and $\mathbb{E}[T_{u,v}]$ are computable in some
strong sense, then we can replace $\mathbb{E}[T_{u,v}^{2}]$ with
$\mathbb{E}[T_{u,v}]^{2}$ and $\mathbb{E}[C_{u}^{2}]$ with
$\mathbb{E}[C_{u}]^{2}$, and shave off a $\sqrt{\log}$ factor.

##### Variable-time Search:

As a special case of our variable-time quantum walk results, we recover
something similar to Ambainis variable-time search result, but allowing the
stopping time on input $i$ to be a random variable $T_{i}$, similar to the
setting Ambainis considers separately in variable-time amplitude
amplification. We restate our result (mentioned already in (3)) with slightly
more detail. Let $M\subset[n]$ be some marked set, and let $\pi$ be any
distribution on $[n]$ such that if $M\neq\emptyset$, $\pi(M)\geq\varepsilon$
for some known bound $\varepsilon$. Leting $T_{i}$ be the stopping time on
input $i\in[n]$ of a subroutine that checks if $i\in M$, we can decide if
$M=\emptyset$ with bounded error in the following complexities, assuming the
values $\mathbb{E}[T_{i}]$ are unknown (first expression), or known in a
certain strong sense (see Corollary 4.4):

$\mbox{(1)
unknown:}\sqrt{\frac{1}{\varepsilon}\sum_{i\in[n]}\pi(i)\mathbb{E}[T_{i}^{2}]}\log^{1.5}{\sf
T}_{\max}\qquad\mbox{known:}\sqrt{\frac{1}{\varepsilon}\sum_{i\in[n]}\pi(i)\mathbb{E}[T_{i}]^{2}}\log{\sf
T}_{\max}.$

The case when the values $\mathbb{E}[T_{i}]$ are known (computable from $i$)
follows from Ambainis’ variable-time search result, since in that case, on
input $i$ we can simply stop after ${\sf T}_{i}=10\mathbb{E}[T_{i}]$ steps
(repeating $O(\log n)$ times and taking a majority to reduce the error). In
the case when these values are unknown, this would probably also follow from a
combination of variable-time search and variable-time amplitude amplification.
What is perhaps more interesting is that we obtain alternative complexities
for variable-time search, by using different parameters. In the case of
unknown expected stopping times, we can also choose either of the following
two complexities (neglecting log factors).

$\mbox{(2)
}\quad\sqrt{\frac{\sum_{i\in[n]}\pi(i)\mathbb{E}[T_{i}]}{\min_{x:M_{x}\neq\emptyset}\sum_{i\in
M}\frac{\pi(i)}{\mathbb{E}[T_{i}]}}}\quad\mbox{ or }\quad\mbox{ (3)
}\quad\frac{1}{\sqrt{\min_{x:M_{x}\neq\emptyset}\sum_{i\in
M}\frac{\pi(i)}{\mathbb{E}[T_{i}^{2}]}}}.$

Above, we minimize over all allowed (non-empty) marked sets, assuming the
marked set depends on some implicit input. Table 1 shows the three
complexities we can obtain, and argues that there are settings where each of
the three is the smallest complexity. We note that we can achieve analogous
complexities to each of (1), (2) and (3) for more general quantum walk
algorithms. The generalization of (1) is the results we presented above. The
generalization of (2) is essentially what was shown in [JZ22] ((8)). We have
not explored the generalization of (3). Other settings of the parameters in
our main quantum walk theorem, Theorem 4.1, could lead to further
alternatives, although it is unclear if these would be useful.

###  1.2 Quantum Algorithm Composition

We use a similar technique to compose an arbitrary quantum query algorithm
with a variable-time subroutine. That is, fix functions
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$\\{g_{i}:\\{0,1\\}^{m}\rightarrow\\{0,1\\}\\}_{i\in[n]}$, and define $f\circ
g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$ by $f\circ
g(x)=f(g(x))=f(g_{1}(x),\dots,g_{n}(x))$. Suppose we have a quantum algorithm
algorithm that decides $f$ with bounded error in ${\sf L}$ time steps and
${\sf Q}$ queries to the input to $f$, and a quantum algorithm that decides
$g(i,x)=g_{i}(x)$ in ${\sf T}_{\max}$ steps with some sufficiently small
error. Then by composing these algorithms in a naive way, we get a bounded
error quantum algorithm for $f\circ g$ with complexity:

$\widetilde{O}({\sf L}+{\sf Q}\cdot{\sf T}_{\max}).$

As in the case of quantum walk algorithms, we show how we can do significantly
better if the inner algorithm’s running time varies significantly in the input
$i$, as well as its internal randomness. We show the following (see Theorem
5.1):

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

Let $\bar{\sf q}_{i}$ be the average (over all queries made by the outer
algorithm) squared amplitude on querying index $i\in[n]$ (see (52)). Let
$\epsilon_{i}$ be the error of the inner subroutine on input $i$, and $T_{i}$
the stopping time of the inner subroutine on input $i$, which is a random
variable. Let ${\sf T}_{\mathrm{avg}}$ be an upper bound such that:

$\sum_{i\in[n]}\bar{\sf q}_{i}\mathbb{E}[T_{i}]\leq{\sf T}_{\mathrm{avg}}$

and suppose the subroutine’s errors satisfy the following condition:

$\epsilon_{\mathrm{avg}}:=\sum_{i\in[n]}\bar{\sf
q}_{i}\epsilon_{i}\leq\frac{1}{{\sf Q}({\sf L}+{\sf Q}\cdot{\sf
T}_{\mathrm{avg}})}.$

Then there is a quantum algorithm that computes $f\circ g$ with bounded error
in complexity

$\widetilde{O}\left({\sf L}+{\sf Q}\cdot{\sf T}_{\mathrm{avg}}\right).$

We compare this with the naive upper bound of ${\sf L}+{\sf Q}\cdot{\sf
T}_{\max}$. Since ${\sf T}_{\max}$ is the _maximum_ running time of any
subroutine, this can be significantly better when $\mathbb{E}[T_{i}]$ varies
widely over different $i$. If the values $\mathbb{E}[T_{i}]$ are _known_ (i.e.
computable from $i$), we can always truncate the inner algorithm, on input
$i$, at some time ${\sf T}_{i}=10\mathbb{E}[T_{i}]$, and then by Markov’s
inequality, the probability that the algorithm has output correctly is not
impacted by more than a constant. In that case, Theorem 1.1 does better than
naive composition if and only if the values $\mathbb{E}[T_{i}]$ vary.

We remark that our error dependence is not optimal. If $\epsilon_{i}=\epsilon$
for all $i$, then a subroutine called ${\sf Q}$ times needs $\epsilon\leq
1/{\sf Q}^{2}$ to achieve overall bounded error. In the usual way of calling a
subroutine, there is no reason that the error bound on the subroutine queries
should scale with anything other than the number of times the subroutine is
called. In particular, it need not scale with the number of _other_ steps of
the algorithm (${\sf L}$) or the number of steps taken by a given call of the
subroutine, since $\epsilon$ is already totalled over all these steps. There
is also no reason to think that the error should scale with these things when
we combine a subroutine and outer algorithm in the way we do in the proof of
Theorem 5.1, so we suspect there is something here that can be improved. In
practice it does not make much difference, since the error of a bounded error
subroutine can be made as small as any $\epsilon$ at a multiplication cost of
$\log\frac{1}{\epsilon}$, so the overhead is at most logarithmic. Still, it
would be nice to understand, conceptually, how different errors add up, and at
the moment it seems there is something missing from the picture. We leave this
for future work.

###  1.3 Outline

The rest of this paper is organized as follows. In Section 2, we give
preliminaries on graph theory and random walks (Section 2.1) as well as phase
estimation algorithms, on which all of our algorithms are based (Section 2.2).
In Section 3, we introduce our model of variable-time quantum algorithms,
which is a slight generalization of the models of [Amb10] and [Amb12]. We
define certain states and subspaces from such algorithms, and prove a number
of properties of these that will be used in our composition results. In
Section 4, we state and prove our results for composing variable-time
subroutines in quantum walks, and in Section 5, we prove Theorem 1.1, by
showing how to compose a variable-time subroutine into an arbitrary quantum
algorithm.

##  2 Preliminaries

###  2.1 Graph Theory

In this section, we define graph theoretic concepts and notation, used in our
results on quantum walks.

######  Definition 2.1 (Network).

A _network_ is a weighted graph $G$ with an (undirected) edge set $E(G)$,
vertex set $V(G)$, and some weight function ${\sf
w}:E(G)\rightarrow\mathbb{R}_{>0}$. Since edges are undirected, we can
equivalently describe the edges by some set $\overrightarrow{E}(G)$ such that
for all $\\{u,v\\}\in E(G)$, exactly one of $(u,v)$ or $(v,u)$ is in
$\overrightarrow{E}(G)$. The choice of edge directions is arbitrary. Then we
can view the weights as a function ${\sf
w}:\overrightarrow{E}(G)\rightarrow\mathbb{R}_{>0}$, and for all
$(u,v)\in\overrightarrow{E}(G)$, define ${\sf w}_{v,u}={\sf w}_{u,v}$. For
convenience, we will define ${\sf w}_{u,v}=0$ for every pair of vertices such
that $\\{u,v\\}\not\in E(G)$. The _total weight_ of $G$ is

${\cal W}(G):=\sum_{e\in\overrightarrow{E}(G)}{\sf w}_{e}.$

For an implicit network $G$, and $u\in V(G)$, we will let $\Gamma(u)$ denote
the _neighbourhood_ of $u$:

$\Gamma(u):=\\{v\in V(G):\\{u,v\\}\in E(G)\\}.$

We use the following notation for _the out- and in-neighbourhoods_ of $u\in
V(G)$:

$\begin{split}\Gamma^{+}(u)&:=\\{v\in\Gamma(u):(u,v)\in\overrightarrow{E}(G)\\}\\\
\Gamma^{-}(u)&:=\\{v\in\Gamma(u):(v,u)\in\overrightarrow{E}(G)\\}.\end{split}$
(12)

##### Random Walks:

A _Markov process_ on a finite set $V$ is specified by a stochastic
_transition matrix_ $P\in\mathbb{R}^{V\times V}$, where we interpret $P_{u,v}$
as the probability of moving to the state $v$ when currently in the state $u$.
We can define a Markov process $P$ from a weighted graph $G$ by letting:

$P_{u,v}=\frac{{\sf w}_{u,v}}{{\sf w}_{u}},\mbox{ where }{\sf
w}_{u}:=\sum_{v\in\Gamma(u)}{\sf w}_{u,v}.$

Next, define

$\forall u\in V(G),\;\pi(u):=\frac{{\sf w}_{u}}{2{\cal W}(G)}.$

Then it is easy to check that $\sum_{u\in V(G)}\pi(u)=1$. Furthermore, if $G$
is connected, $\pi$ is the unique left-1-eigenvector of $P$, called the
_stationary distribution_. We note that for any $u,v\in V(G)$,

$\pi(u)P_{u,v}=\frac{{\sf w}_{u}}{2{\cal W}(G)}\frac{{\sf w}_{u,v}}{{\sf
w}_{u}}=\frac{{\sf w}_{u,v}}{2{\cal W}(G)}=\frac{{\sf w}_{v,u}}{2{\cal
W}(G)}=\pi(v)P_{v,u}.$ (13)

When $P$ satisfies this condition, called _detailed balance_ , we say that $P$
is _reversible_. We have just seen that any random walk on an undirected
weighted graph is reversible, and it is also true that any reversible Markov
process can be modelled as a random walk on an undirected weighted graph,
using edge weights ${\sf w}_{u,v}=\pi(u)P_{u,v}$.

Finally, we let $\delta$ denote the _spectral gap_ of $P$, which is the
smallest non-zero eigenvalue of $I-P$. For intuition, it is useful to know
that $\frac{1}{\delta}$ is within a $\log|V(G)|$ factor of the mixing time of
$P$ (see, for example, [LWP09]).

##### Accessing $G$:

In computations involving a (classical) random walk on a graph $G$, it is
usually assumed that for any $u\in V(G)$, it is possible to sample a neighbour
$v\in\Gamma(u)$ according to the distribution given by the $u$-th row of $P$.
It is standard to assume this is broken into two steps: (1) sampling some
$i\in[d_{u}]$, where $d_{u}:=|\Gamma(u)|$ is the degree of $u$, and (2)
computing the $i$-th neighbour of $u$. That is, we assume that for each $u\in
V(G)$, there is an efficiently computable function $f_{u}:[d_{u}]\rightarrow
V(G)$ such that $\mathrm{im}(f_{u})=\Gamma(u)$, and we call $f_{u}(i)$ the
_$i$ -th neighbour of $u$_. In the quantum case (see Definition 2.2 below), we
assume that the sample (1) can be done coherently, and we use a reversible
version of the map $(u,i)\mapsto f_{u}(i)$. We will also find it convenient to
suppose the indices $i$ of the neighbours of $u$ come from some more general
set $L(u)$, which may equal $[d_{u}]$, or some other convenient set, which we
call the _edge labels of $u$_. It is possible to have
$|L(u)|>|\Gamma(u)|=d_{u}$, meaning that some elements of $L(u)$ do not label
an edge adjacent to $u$ (these labels should be sampled with probability 0).
We assume we have a partition of $L(u)$ into disjoint $L^{+}(u)$ and
$L^{-}(u)$ such that:

$\begin{split}L^{+}(u)&\supseteq\\{i\in
L(u):(u,f_{u}(i))\in\overrightarrow{E}(G)\\}=\\{i\in
L(u):f_{u}(i)\in\Gamma^{+}(u)\\}\\\ L^{-}(u)&\supseteq\\{i\in
L(u):(f_{u}(i),u)\in\overrightarrow{E}(G)\\}=\\{i\in
L(u):f_{u}(i)\in\Gamma^{-}(u)\\}.\end{split}$

Note that for any $(u,v)\in\overrightarrow{E}(G)$, with $i=f_{u}^{-1}(v)$ and
$j=f_{v}^{-1}(u)$, any of $(u,v)$, $(v,u)$, $(u,i)$, or $(v,j)$ fully specify
the edge. Thus, it will be convenient to denote the weight of the edge using
any of the alternatives:

${\sf w}_{u,v}={\sf w}_{v,u}={\sf w}_{u,i}={\sf w}_{v,j}.$

For any $i\in L(u)$, we set ${\sf w}_{u,i}=0$ if and only if
$\\{u,f_{u}(i)\\}\not\in E(G)$.

######  Definition 2.2 (Quantum Walk access to $G$).

For each $u\in V(G)$, let $L(u)=L^{+}(u)\cup L^{-}(u)$ be some finite set of
_edge labels_ , and $f_{u}:L(u)\rightarrow V(G)$ a function such that
$\Gamma(u)\subseteq\mathrm{im}(f_{u})$. A quantum algorithm has _quantum walk
access_ to $G$ if it has access to the following subroutines:

  * •

A subroutine that generates quantum samples from $L(u)$ by implementing a
unitary $U_{\star}$ in cost ${\sf A}_{\star}$ that acts as:

$U_{\star}{\lvert}u,0\rangle\propto\sum_{i\in L^{+}(u)}\sqrt{{\sf
w}_{u,i}}{\lvert}u,i\rangle-\sum_{i\in L^{-}(u)}\sqrt{{\sf
w}_{u,i}}{\lvert}u,i\rangle=:{\lvert}\psi_{\star}^{G}(u)\rangle.$

  * •

A subroutine that implements the _transition map_

${\lvert}u,i\rangle\mapsto{\lvert}v,j\rangle$

(possibly with some error) where $i=f^{-1}_{u}(v)$ and $j=f^{-1}_{v}(u)$, with
costs $\\{{\sf T}_{u,i}={\sf T}_{u,v}\\}_{(u,v)\in\overrightarrow{E}(G)}$.

  * •

Query access to the total vertex weights ${\sf w}_{u}=\sum_{v\in\Gamma(u)}{\sf
w}_{u,v}$.

We call $\\{{\sf T}_{e}\\}_{e\in\overrightarrow{E}(G)}$ the set of _transition
costs_ and ${\sf A}_{\star}$ the _cost of generating the star states_.

##### Flows and Resistances:

Electric networks of resistors can be modelled as weighted graphs, where the
weights represent _conductances_ (so their inverses represent _resistances_).
This beautiful connection was expounded by Doyle and Snell [DS84], or see
[LWP09] for a modern exposition. This connection inspires the following
definitions.

######  Definition 2.3 (Flow, Circulation).

A _flow_ on a network $G$ is a real-valued function
$\theta:\overrightarrow{E}(G)\rightarrow\mathbb{R}$, extended to edges in both
directions by $\theta(u,v)=-\theta(v,u)$ for all
$(u,v)\in\overrightarrow{E}(G)$. For any flow $\theta$ on $G$, and vertex
$u\in V(G)$, we define $\theta(u)=\sum_{v\in\Gamma(u)}\theta(u,v)$ as the flow
coming out of $u$. If $\theta(u)=0$, we say flow is conserved at $u$. If flow
is conserved at every vertex, we call $\theta$ a _circulation_. If
$\theta(u)>0$, we call $u$ a _source_ , and if $\theta(u)<0$ we call $u$ a
_sink_. The set of sources and sinks is called the _boundary_ of $\theta$. A
flow with unique source $s$ and unique sink $t$ is called an _$st$ -flow_. If
additionally $\theta(s)=1$, we call $\theta$ a _unit_ $st$-flow. The _energy_
of $\theta$ is

${\cal
E}(\theta):=\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}.$

######  Definition 2.4 (Effective Resistance).

Let $\sigma$ and $\tau$ be distributions on $V(G)$. We define the _effective
resistance from $\sigma$ to $\tau$_:

${\cal R}_{\sigma,\tau}(G):=\min\\{{\cal E}(\theta):\forall u\in
V(G),\theta(u)=\sigma(u)-\tau(u)\\}.$

When $\sigma$ and $\tau$ have disjoint support, this is the minimum energy of
a flow whose sources are exactly $\mathrm{supp}(\sigma)$, with
$\theta(u)=\sigma(u)$, and whose sinks are exactly $\mathrm{supp}(\tau)$, with
$\theta(u)=-\tau(u)$. In the special case when $\mathrm{supp}(\sigma)=\\{s\\}$
and $\mathrm{supp}(\tau)=\\{t\\}$, then $\theta$ ranges over all unit
$st$-flows, and we denote ${\cal R}_{\sigma,\tau}(G)$ by ${\cal R}_{s,t}(G)$.
Finally, for any $M\subseteq V(G)\setminus\mathrm{supp}(\sigma)$, we define:

${\cal R}_{\sigma,M}(G):=\min\\{{\cal
R}_{\sigma,\tau}(G):\mathrm{supp}(\tau)\subseteq M\\}.$

That is, ${\cal R}_{\sigma,M}(G)$ is the minimum energy of a flow from
$\sigma$ to $M$ (where any distribution on $M$ is allowed).

There is always a unique $\theta$ from $\sigma$ to $\tau$ (or $\sigma$ to $M$)
that achieves energy ${\cal R}_{\sigma,\tau}(G)$ (or ${\cal
R}_{\sigma,M}(G)$): If two $\sigma$-$\tau$ flows achieve energy ${\cal E}$,
then there is some affine combination of them that achieves energy strictly
smaller than ${\cal E}$.

These concepts are related to random walks as follows.

######  Theorem 2.5 ([CRR+96]).

For any $s,t\in V(G)$, let ${\cal C}_{s,t}(G)$ be the _commute time_ from $s$
to $t$, which is the expected number of steps taken in a random walk starting
at $s$, before the walker reaches $t$, and then returns to $s$. Then ${\cal
C}_{s,t}(G)=2{\cal W}(G){\cal R}_{s,t}(G)$.

######  Theorem 2.6 (Folklore, or see [AGJ20]).

For any set $M\subset V(G)$ and $s\in V(G)$, let ${\cal C}_{s,M}(G)$ be the
_commute time_ from $s$ to $M$, which is the expected number of steps taken in
a random walk starting at $s$, before the walker reaches $M$, and then returns
to $s$. Then ${\cal C}_{s,M}(G)=2{\cal W}(G){\cal R}_{s,M}(G)$.

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

For any set $M\subset V(G)$, let ${\cal H}_{\pi,M}(G)$ be the _hitting time_
from the stationary distribution $\pi$ to $M$, which is the expected number of
steps taken in a random walk starting in a vertex sampled according to $\pi$,
before the walker reaches $M$. Then ${\cal H}_{\pi,M}(G)=2{\cal W}(G){\cal
R}_{\pi,M}(G)$.

Motivated by the three theorems above, we define

${\cal C}_{\sigma,\tau}(G):=2{\cal W}(G){\cal R}_{\sigma,\tau}(G)\mbox{ and
}{\cal C}_{\sigma,M}(G):=2{\cal W}(G){\cal R}_{\sigma,M}(G).$ (14)

###  2.2 Phase Estimation Algorithms

We will use the precise notion of a _phase estimation algorithm_ from [JZ22],
which is based on the phase estimation technique of [Kit96].

######  Definition 2.8 (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.9 (Negative Witness).

A $\delta$-_negative witness_ for $(H,{\lvert}\psi_{0}\rangle,\Psi^{\cal
A},\Psi^{\cal B})$ is a pair of vectors ${\lvert}w_{\cal
A}\rangle,{\lvert}w_{\cal B}\rangle\in H$ such that $\left\|(I-\Pi_{\cal
A}){\lvert}w_{\cal A}\rangle\right\|^{2}\leq\delta$, $\left\|(I-\Pi_{\cal
B}){\lvert}w_{\cal B}\rangle\right\|^{2}\leq\delta$, and
${\lvert}\psi_{0}\rangle={\lvert}w_{\cal A}\rangle+{\lvert}w_{\cal B}\rangle$.

######  Definition 2.10 (Positive Witness).

A $\delta$-_positive witness_ for $(H,{\lvert}\psi_{0}\rangle,\Psi^{\cal
A},\Psi^{\cal B})$ is a vector ${\lvert}w\rangle\in H$ such that
${{\langle}\psi_{0}|}w\rangle\neq 0$ and ${\lvert}w\rangle$ is almost
orthogonal to all ${\lvert}\psi\rangle\in\Psi^{\cal A}\cup\Psi^{\cal B}$, in
the sense that $\left\|\Pi_{\cal
A}{\lvert}w\rangle\right\|^{2}\leq\delta\left\|{\lvert}w\rangle\right\|^{2}$
and $\left\|\Pi_{\cal
B}{\lvert}w\rangle\right\|^{2}\leq\delta\left\|{\lvert}w\rangle\right\|^{2}$.444We
note that for technical reasons, positive witness error is defined
multiplicatively (relative error), whereas negative witness error is defined
additively.

######  Theorem 2.11 ([JZ22]).

Fix $(H,{\lvert}\psi_{0}\rangle,\Psi^{\cal A},\Psi^{\cal B})$ as in Definition
2.8. 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|$. Let $\delta$ and
$\delta^{\prime}$ be positive real parameters such that

$\delta\leq\frac{1}{(8c_{+})^{3}\pi^{8}{{\cal C}_{-}}}\quad\mbox{ and
}\quad\delta^{\prime}\leq\frac{3}{4}\frac{1}{\pi^{4}c_{+}}.$

Suppose we are guaranteed that exactly one of the following holds:

Positive Condition:

There is a $\delta$-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 $\delta^{\prime}$-negative witness ${\lvert}w_{\cal
A}\rangle,{\lvert}w_{\cal B}\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 cost

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

##  3 Variable-Time Subroutines

A variable-time subroutine is a sequence of unitaries $U_{1},\dots,U_{{\sf
T}}$, for some ${\sf T}={\sf T}_{\max}$, acting on the space

$H_{\cal I}\otimes H_{\cal A}\otimes H_{\cal
Z}=\mathrm{span}\\{{\lvert}i\rangle{\lvert}a\rangle{\lvert}z\rangle:i\in{\cal
I},a\in{\cal A},z\in{\cal Z}\\}$

for finite sets ${\cal I}$, representing inputs to the subroutine; ${\cal A}$,
representing answers the subroutine may output; and ${\cal Z}$, representing
states of the algorithm’s workspace. Both ${\cal A}$ and ${\cal Z}$ can be
assumed to be initialized to ${\lvert}0\rangle$. The unitaries are controlled
on $H_{\cal I}$, so we can express $U_{t}=\sum_{i\in{\cal
I}}{\lvert}i\rangle{\langle}i\rvert\otimes U_{t}^{i}$ for some unitaries
$U_{t}^{i}$. In other words, the input register is read only. Following
[Amb12], we make the following assumptions.

  1. 1.

There are subspaces

$\\{0\\}=H_{0}\subseteq H_{1}\subseteq\dots\subseteq H_{{\sf T}}=H_{\cal Z}$

such that $U_{t}$ leaves $H_{t-1}$ invariant, so any part of the algorithm in
$H_{t-1}$ after $U_{t-1}$ has been applied, does not get changed any more.
Letting $\Pi_{\leq t-1}$ denote the orthogonal projector onto $H_{t-1}$, we
can express this mathematically as:

$U_{t}\Pi_{\leq t-1}=\Pi_{\leq t-1}.$ (15)

For any $t$, we assume we can measure a bit indicating if we are in $H_{t}$ in
unit cost. 555For example, imagine having ${\sf T}$ single-qubit registers,
$F_{1},\dots,F_{\sf T}$, where we set a 1 in $F_{t}$ after $U_{t}$ has been
applied to indicate that the algorithm is ready to halt, and then all
subsequent unitaries are controlled on no 1s yet being set.

  2. 2.

We can implement $\sum_{t=1}^{{\sf T}}{\lvert}t\rangle{\langle}t\rvert\otimes
U_{t}$ in unit cost.

We say that $t$ is a potential stopping time if $\overline{H}_{t}:=H_{t}\cap
H_{t-1}^{\bot}\neq\\{0\\}$, so $H_{\cal
Z}:=\overline{H}_{1}\oplus\dots\oplus\overline{H}_{\sf T}$. We can imagine an
algorithm that, for every potential stopping time $t$, after applying $U_{t}$,
measures to see if the algorithm is in the space $H_{t}$, and if so, the
algorithm is done and the answer register can also be measured, and if not,
the algorithm continues. Since the later unitaries leave $H_{t}$ invariant,
these measurements do not affect the computation.

Let $\\{{\lvert}z\rangle:z\in{\cal Z}_{t}\\}$ be an orthonormal basis for
$\overline{H}_{t}$, for some disjoint sets ${\cal Z}=\bigcup_{t}{\cal Z}_{t}$.
Note that ${\cal Z}_{t}\neq\emptyset$ precisely when $t$ is a potential
stopping time. Since we assume we can measure if the algorithm is in each
space, we assume we can generate each of these bases.

For $t\in[{\sf T}]$, we let $\bar{p}_{i}(t)$ be the probability of stopping at
time $t$ (i.e. measuring “1” right after $U_{t}$ is applied) on input $i$.
Then

$p_{i}(t)=\bar{p}_{i}(0)+\dots+\bar{p}_{i}(t-1)$ (16)

is the probability that the algorithm halts some time before $U_{t}$ is
applied. We let $T_{i}$ be the random variable such that
$\Pr[T_{i}=t]=\bar{p}_{i}(t)$, so $T_{i}$ is the stopping time on input $i$.

Suppose the algorithm is meant to compute some function $g:{\cal
I}\rightarrow{\cal A}$. Then if we let $\Pi_{t}$ be the orthogonal projector
onto $\overline{H}_{t}$, and $\Xi_{a}$ the orthogonal projector onto $a$ in
the answer register, the probability that the algorithm outputs an incorrect
answer on input $i$, given that it stops at time $t$, is:

$\epsilon_{i}^{t}:=\frac{1}{\bar{p}_{i}(t)}\left\|((I-\Xi_{g(i)})\otimes\Pi_{t})U_{t}\dots
U_{1}{\lvert}i,0,0\rangle\right\|^{2}.$ (17)

##### Reversible Variable-Time Subroutines:

So far this is just a generalization of Ambainis’ notion of a variable
stopping time algorithm in [Amb12] to allowing the output to be more than just
a bit. We will extend it to what we call _Reversible Variable-Time
Subroutines_. Building on the above notation, suppose what we are _actually_
interested in is computing ${\lvert}i\rangle\mapsto A{\lvert}i\rangle$, for
some isometry $A$. A simple example we will consider (Section 5) is
$A{\lvert}i\rangle=(-1)^{g_{i}}{\lvert}i\rangle$ for some
$g:[n]\rightarrow\\{0,1\\}$. In the other example we will see, in Section 4,
$A{\lvert}u,i\rangle={\lvert}v,j\rangle$ for vertices
$(u,v)\in\overrightarrow{E}(G)$, with $f_{u}(i)=v$ and $f_{v}(j)=u$ (see
Definition 2.2). Whatever the case, we will suppose that computing $A$ can be
reduced to computing some auxiliary information $g(i)\in{\cal A}$, for which
we have a variable-time subroutine. To this end, we say that a variable-time
subroutine _reversibly computes $A$_ if it computes $g(i)$, and satisfies the
following additional assumptions:

  1. 1.

For $t\in\\{1,\dots,{\sf T}\\}$, letting

$\tilde{U}_{t}=\sum_{i\in{\cal I}}A{\lvert}i\rangle{\langle}i\rvert
A^{\dagger}\otimes U_{t}^{i},$

the unitary $\sum_{t=1}^{{\sf
T}}{\lvert}t\rangle{\langle}t\rvert\otimes\tilde{U}_{t}$ can be implemented in
unit cost.

  2. 2.

There exists a unitary $A^{\prime}$ of the following form that can be
implemented in unit cost:

$A^{\prime}=\sum_{a\in{\cal A}}{\lvert}a\rangle{\langle}a\rvert\otimes A_{a},$

and such that $A_{g(i)}=A$.

  3. 3.

For all $i,i^{\prime}\in{\cal I}$ such that $i\neq i^{\prime}$, and all
$a\in{\cal A}$, ${\langle}i^{\prime}\rvert
A^{\dagger}A_{a}{\lvert}i\rangle=0$.

If $A$ were easy to implement, then we would not need a subroutine. Instead,
we are assuming (condition 2) that there is an easy to implement $A^{\prime}$
that computes $A$ given the auxiliary information $g(i)$ computed by the
variable-time subroutine. Given a reversible variable-time subroutine for
computing $A$, we can implement the map ${\lvert}i\rangle\mapsto
A{\lvert}i\rangle$ by running the variable-time subroutine
$U_{1},\dots,U_{{\sf T}}$ until the algorithm halts at some step $T_{i}$,
applying $A^{\prime}$, and then uncomputing by running
$\tilde{U}_{T_{i}},\dots,\tilde{U}_{1}$ (condition 1). The last condition is
not strictly necessary, but the total error of algorithms that use the
subroutine (see Section 4 and Section 5) is different if we omit it. The
condition basically says that while the subroutine might output the wrong
answer, it will not output an answer that could interfere with the correct
part of another branch of the superposition running the algorithm on a
different input.

For example, suppose
$A{\lvert}i\rangle{\lvert}0\rangle={\lvert}i\rangle{\lvert}g(i)\rangle$, so
$A$ just adds information to the state – not in an information theoretic
sense, but in a computational sense. In that case, it is still possible to
control on $i$ to reverse the computation after we have applied $A$
(conditions 1 and 2), and condition 3 is satisfied, since
${{\langle}i^{\prime},g(i^{\prime})|}i,a\rangle=0$ whenever $i\neq
i^{\prime}$, regardless of $a$. Similarly, if $g(i)$ is a single bit, and
$A{\lvert}i\rangle=(-1)^{g(i)}{\lvert}i\rangle$, then a variable-time
subroutine for $g$ is trivially reversible, by setting $\tilde{U}_{t}=U_{t}$
for all $t$, and $A_{a}{\lvert}i\rangle=(-1)^{a}{\lvert}i\rangle$.

###  3.1 Transition States and Algorithm States

We define several states associated with a variable stopping time algorithm,
and prove some properties that will be useful later. We first define some
states called _transition states_ from the subroutine, and sort them into two
sets $\Psi_{0}$ and $\Psi_{1}$, such that each set is pairwise orthogonal.
These sets could be used to define a phase estimation algorithm as described
in Section 2.2. There would be little point in turning an algorithm into a
phase estimation algorithm – if we already have an algorithm, we do not need
another one – but we will later (in Section 4 and Section 5) combine these
states with some other ones to get a more complicated phase estimation
algorithm that uses the variable stopping time subroutine as a building block.

######  Definition 3.1.

Fix some set of positive weights $\\{\alpha_{t}\\}_{t=1}^{{\sf T}}$ such that
$\alpha_{0}=1$. The _transition states_ of a reversible variable stopping time
subroutine are defined as follows. The _forward transitions states_ are
defined:

$\forall i\in{\cal I},t\in\\{0,\dots,{\sf T}-1\\}\\\
\Psi_{t}^{i,\rightarrow}:=\left\\{{\lvert}\psi_{a,z,t}^{i,\rightarrow}\rangle:={\lvert}\rightarrow\rangle{\lvert}i\rangle\left(\sqrt{\alpha_{t}}{\lvert}a,z\rangle{\lvert}t\rangle-\sqrt{\alpha_{t+1}}U_{t+1}^{i}{\lvert}a,z\rangle{\lvert}t+1\rangle\right):a\in{\cal
A},z\in{\cal Z}_{>t}\right\\}.$

The _backward transition states_ are defined:

$\forall i\in{\cal I},t\in\\{0,\dots,{\sf T}-1\\}\\\
\Psi_{t}^{i,\leftarrow}:=\left\\{{\lvert}\psi_{a,z,t}^{i,\leftarrow}\rangle:={\lvert}\leftarrow\rangle
A{\lvert}i\rangle\left(\sqrt{\alpha_{t}}{\lvert}a,z\rangle{\lvert}t\rangle-\sqrt{\alpha_{t+1}}U_{t+1}^{i}{\lvert}a,z\rangle{\lvert}t+1\rangle\right):a\in{\cal
A},z\in{\cal Z}_{>t}\right\\}.$

The _reversal states_ are defined:

$\forall i\in{\cal I},t\in\\{1,\dots,{\sf
T}\\}\qquad\Psi_{t}^{i,\leftrightarrow}:=\left\\{{\lvert}\psi_{a,z,t}^{i,\leftrightarrow}\rangle:=\sqrt{\alpha_{t}}\left({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A_{a}{\lvert}i\rangle\right){\lvert}a,z\rangle{\lvert}t\rangle:a\in{\cal
A},z\in{\cal Z}_{t}\right\\}.$

We finally define $\Psi_{0}^{i,\leftrightarrow}=\Psi_{\sf
T}^{i,\rightarrow}=\Psi_{\sf T}^{i,\leftarrow}=\emptyset$, and:

$\displaystyle\Psi_{0}$ $\displaystyle=\bigcup_{i\in{\cal
I}}\bigcup_{t=0:t\;\mathrm{even}}^{{\sf
T}}\left(\Psi_{t}^{i,\rightarrow}\cup\Psi_{t}^{i,\leftarrow}\cup\Psi_{t}^{i,\leftrightarrow}\right)\quad\mbox{and}\quad\Psi_{1}=\bigcup_{i\in{\cal
I}}\bigcup_{t=0:t\;\mathrm{odd}}^{{\sf
T}}\left(\Psi_{t}^{i,\rightarrow}\cup\Psi_{t}^{i,\leftarrow}\cup\Psi_{t}^{i,\leftrightarrow}\right).$

######  Claim 3.2.

For $b\in\\{0,1\\}$, the states of $\Psi_{b}$ are pairwise orthogonal.

To convince oneself of Claim 3.2, one should notice that the states in each
set $\Psi_{t}^{i,d}$ are pairwise orthogonal, and the only overlaps between
sets are those shown in the graph in Figure 2. Then since $\Psi_{0}$ and
$\Psi_{1}$ are formed from a bipartition of this graph, they are each pairwise
orthogonal.

$\Psi_{0}^{i,\rightarrow}$$\Psi_{1}^{i,\leftrightarrow}$$\Psi_{0}^{i,\leftarrow}$$\Psi_{1}^{i,\rightarrow}$$\Psi_{2}^{i,\leftrightarrow}$$\Psi_{1}^{i,\leftarrow}$$\Psi_{2}^{i,\rightarrow}$$\Psi_{3}^{i,\leftrightarrow}$$\Psi_{2}^{i,\leftarrow}$$\dots$$\dots$$\dots$$\Psi_{t}^{i,\rightarrow}$$\Psi_{t+1}^{i,\leftrightarrow}$$\Psi_{t}^{i,\leftarrow}$$\dots$$\dots$$\dots$$\Psi_{{\sf
T}-1}^{i,\rightarrow}$$\Psi_{\sf T}^{i,\leftrightarrow}$$\Psi_{{\sf
T}-1}^{i,\leftarrow}$ Figure 2: The overlap graph of the sets of states
defined in Definition 3.4 for some fixed $i$. Each node represents a set of
states that are pairwise orthogonal. Two nodes share an edge if and only if
their sets contain overlapping states. For different values of $i$, all states
are orthogonal. One can imagine an algorithm starting in the state
${\lvert}\rightarrow\rangle{\lvert}i\rangle{\lvert}0,0\rangle{\lvert}0\rangle$,
which only overlaps $\Psi_{0}^{i,\rightarrow}$. The state of the algorithm
moves through the graph until some part of it is of the form
${\lvert}\leftarrow\rangle
A_{a}{\lvert}i\rangle{\lvert}a,z\rangle{\lvert}t\rangle$, hopefully for
$a=g(i)$, then on that part, it uncomputes to move back down the other side of
the ladder to a state that only overlaps $\Psi_{0}^{i,\leftarrow}$. The length
of the algorithm’s path depends on which “rung” $t$ of the ladder it uses to
move from the $\rightarrow$ to the $\leftarrow$ part, which will depend on the
stopping probabilities at various steps.

######  Lemma 3.3.

For $b\in\\{0,1\\}$, let $\Pi_{\Psi_{b}}$ denote the orthogonal projector onto
the span of $\Psi_{b}$. Then $(2\Pi_{\Psi_{b}}-I)$ can be implemented in
$O(\log{\sf T})$ complexity.

###### Proof.

The basic idea is that for $b\in\\{0,1\\}$, we can implement a unitary $U_{b}$
that acts, for all $i\in{\cal I}$, $a\in\\{0,1\\}$, and $t$ of parity $b$, as:

  1. 1.

${\lvert}\rightarrow\rangle{\lvert}i\rangle{\lvert}a,z,t\rangle\overset{U_{b}}{\mapsto}\propto{\lvert}\psi_{a,z,t}^{i,\rightarrow}\rangle$
for all $z\in{\cal Z}_{>t}$

  2. 2.

${\lvert}\leftarrow\rangle
A{\lvert}i\rangle{\lvert}a,z,t\rangle\overset{U_{b}}{\mapsto}\propto{\lvert}\psi_{a,z,t}^{i,\leftarrow}\rangle$
for all $z\in{\cal Z}_{>t}$

  3. 3.

${\lvert}\leftrightarrow\rangle{\lvert}i\rangle{\lvert}a,z,t\rangle\overset{U_{b}}{\mapsto}\propto{\lvert}\psi_{a,z,t}^{i,\leftrightarrow}\rangle$
for all $z\in{\cal Z}_{t}$

using, respectively:

  1. 1.

The ability to implement $\sum_{t=1}^{\sf
T}{\lvert}t\rangle{\langle}t\rvert\otimes U_{t}$ in unit cost.

  2. 2.

The ability to implement $\sum_{t=1}^{\sf
T}{\lvert}t\rangle{\langle}t\rvert\otimes\tilde{U}_{t}$ in unit cost.

  3. 3.

The ability to implement $\sum_{a\in{\cal
A}}{\lvert}a\rangle{\langle}a\rvert\otimes A_{a}$ in unit cost.

We implement $U_{b}$ in two parts: the first is conditioned on $z\in{\cal
Z}_{>t}$, which will ensure (1) and (2); the second is conditioned on
$z\in{\cal Z}_{t}$, which will ensure condition (3). First, conditioned on
$z\in{\cal Z}_{>t}$, do the following. Append an auxiliary qubit initialized
to ${\lvert}0\rangle$. Controlled on $t$, rotate this qubit to
$\propto\sqrt{\alpha_{t}}{\lvert}0\rangle-\sqrt{\alpha_{t+1}}{\lvert}1\rangle$.
When $z\in{\cal Z}_{>t}$, we only care about the cases where the first qubit
is ${\lvert}\rightarrow\rangle$ or ${\lvert}\leftarrow\rangle$, and in these
cases we now have:

$\displaystyle(\rightarrow)\mbox{-case: }$
$\displaystyle\sqrt{\alpha_{t}}{\lvert}0\rangle{\lvert}\rightarrow\rangle{\lvert}i\rangle{\lvert}a,z,t\rangle-\sqrt{\alpha_{t+1}}{\lvert}1\rangle{\lvert}\rightarrow\rangle{\lvert}i\rangle{\lvert}a,z,t\rangle,$
$\displaystyle(\leftarrow)\mbox{-case: }$
$\displaystyle\sqrt{\alpha_{t}}{\lvert}0\rangle{\lvert}\leftarrow\rangle
A{\lvert}i\rangle{\lvert}a,z,t\rangle-\sqrt{\alpha_{t+1}}{\lvert}1\rangle{\lvert}\leftarrow\rangle
A{\lvert}i\rangle{\lvert}a,z,t\rangle.$

Controlled on the auxiliary qubit being ${\lvert}1\rangle$, increment the last
register, and then (still controlled on ${\lvert}1\rangle$) controlled on
${\lvert}\rightarrow\rangle$, apply $\sum_{t=1}^{\sf
T}{\lvert}t\rangle{\langle}t\rvert\otimes U_{t}$, and controlled on
${\lvert}\leftarrow\rangle$, apply $\sum_{t=1}^{\sf
T}{\lvert}t\rangle{\langle}t\rvert\otimes\tilde{U}_{t}$ to get:

$\displaystyle(\rightarrow)\mbox{-case: }$
$\displaystyle\sqrt{\alpha_{t}}{\lvert}0\rangle{\lvert}\rightarrow\rangle{\lvert}i\rangle{\lvert}a,z,t\rangle-\sqrt{\alpha_{t+1}}{\lvert}1\rangle{\lvert}\rightarrow\rangle{\lvert}i\rangle
U_{t+1}{\lvert}a,z\rangle{\lvert}t+1\rangle,$
$\displaystyle(\leftarrow)\mbox{-case: }$
$\displaystyle\sqrt{\alpha_{t}}{\lvert}0\rangle{\lvert}\leftarrow\rangle
A{\lvert}i\rangle{\lvert}a,z,t\rangle-\sqrt{\alpha_{t+1}}{\lvert}1\rangle{\lvert}\leftarrow\rangle
A{\lvert}i\rangle U_{t+1}{\lvert}a,z\rangle{\lvert}t+1\rangle.$

Since we only care about the action of $U_{b}$ when $t$ has parity $b$, we can
uncompute the auxiliary using the parity of the last register.

Next, conditioned on $z\in{\cal Z}_{t}$, do the following. Map
${\lvert}\leftrightarrow\rangle$ to
$({\lvert}\rightarrow\rangle-{\lvert}\leftarrow\rangle)/\sqrt{2}$, and then
conditioned on ${\lvert}\leftarrow\rangle$, apply
$\sum_{a}{\lvert}a\rangle{\langle}a\rvert\otimes A_{a}$ to get:

$\frac{1}{\sqrt{2}}({\lvert}\rightarrow\rangle{\lvert}i\rangle{\lvert}a,z,t\rangle-{\lvert}\leftarrow\rangle
A_{a}{\lvert}i\rangle{\lvert}a,z,t\rangle)\propto{\lvert}\psi_{a,z,t}^{i,\leftrightarrow}\rangle.$

The map $U_{b}$ can be combined with a reflection $R_{b}$ that checks, for any
state ${\lvert}d\rangle{\lvert}i\rangle{\lvert}a,z\rangle{\lvert}t\rangle$:
$t$ has parity $b$; if $d\in\\{\leftarrow,\rightarrow\\}$, then $z\in{\cal
Z}_{>t}$ and $t<{\sf T}$; and if $d=\leftrightarrow$, then $z\in{\cal Z}_{t}$
and $t>0$. Then $(2\Pi_{\Psi_{b}}-I)=U_{b}R_{b}U_{b}^{\dagger}$. ∎

We now define some states which are essentially positive and negative
witnesses for a phase estimation algorithm defined by $\Psi_{0}$ and
$\Psi_{1}$. When we combine $\Psi_{0}$ and $\Psi_{1}$ with other states to get
more complex phase estimation algorithms in Section 4 and Section 5, these
will be building blocks for the positive and negative witnesses for those
phase estimation algorithms, so we prove several claims analyzing these states
here.

######  Definition 3.4 (Algorithm States).

Fix a reversible variable-time subroutine $U_{1},\dots,U_{\sf T},A$ and some
set of positive weights $\\{\alpha_{t}\\}_{t}$. Let $\Pi_{\geq
t}:=\Pi_{t}+\dots+\Pi_{{\sf T}}$ be the orthogonal projector onto
$H_{t-1}^{\bot}=\overline{H}_{t}\oplus\dots\oplus\overline{H}_{{\sf T}}$.
Define the following _algorithm states_ in $H_{\cal A}\otimes H_{\cal Z}$, for
all $i\in{\cal I}$:

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

The _positive history state_ of the algorithm on input $i\in{\cal I}$ is
defined:

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

The _negative history state_ of the algorithm on input $i\in{\cal I}$ is
defined:

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

We have defined the algorithm states in this way because $\Pi_{\geq
t}{\lvert}w^{t-1}(i)\rangle$ is the part of the algorithm that has not yet
output before we apply $U_{t}^{i}$. The following claim makes clear that
${\lvert}w^{t}(i)\rangle$ consists of two orthogonal parts: the part in
$\overline{H}_{t}$, which is output at this step, and the part in
$H_{t}^{\bot}=\overline{H}_{t+1}\oplus\dots\oplus\overline{H}_{{\sf T}}$,
which has yet to halt.

######  Claim 3.5.

For all $i\in{\cal I}$ and $t\in\\{0,\dots,{\sf T}\\}$,

${\lvert}w^{t}(i)\rangle=\Pi_{\geq t}U_{t}^{i}\Pi_{\geq
t-1}U_{t-1}^{i}\dots\Pi_{\geq 1}U_{1}^{i}{\lvert}0,0\rangle=\Pi_{\geq
t}U_{t}^{i}\dots U_{1}^{i}{\lvert}0,0\rangle.$

###### Proof.

First, note that since $U_{t}^{i}\Pi_{\leq t-1}=\Pi_{\leq t-1}$ (by (15)), we
have:

$U_{t}^{i}\Pi_{\geq t}=U_{t}^{i}(I-\Pi_{\leq t-1})=U_{t}^{i}-\Pi_{\leq
t-1}=(I-\Pi_{\leq t-1})U_{t}^{i}=\Pi_{\geq t}U_{t}^{i},$ (18)

so the first equality follows easily from the definition of
${\lvert}w^{t}(i)\rangle$.

We prove the second equality by induction. For the base step, we have:
${\lvert}w^{0}(i)\rangle={\lvert}0,0\rangle=\Pi_{\geq 0}{\lvert}0,0\rangle.$
For the induction step, assuming ${\lvert}w^{t-1}(i)\rangle=\Pi_{\geq
t-1}U_{t-1}^{i}\dots U_{1}^{i}{\lvert}0,0\rangle$, we have:

$\displaystyle{\lvert}w^{t}(i)\rangle=U_{t}\Pi_{\geq
t}{\lvert}w^{t-1}(i)\rangle$ $\displaystyle=U_{t}\Pi_{\geq t}\Pi_{\geq
t-1}U_{t-1}^{i}\dots U_{1}^{i}{\lvert}0,0\rangle=U_{t}\Pi_{\geq
t}U_{t-1}^{i}\dots U_{1}^{i}{\lvert}0,0\rangle$ $\displaystyle=\Pi_{\geq
t}U_{t}U_{t-1}^{i}\dots U_{1}^{i}{\lvert}0,0\rangle.\qed$

######  Corollary 3.6.

Let $i\in{\cal I}$. Recall the definitions of $\bar{p}_{i}(t)$ and $p_{i}(t)$
((16)). Then we have:

$\left\|\Pi_{t}{\lvert}w^{t}(i)\rangle\right\|^{2}=\bar{p}_{i}(t)\mbox{ and
}\left\|{\lvert}w^{t}(i)\rangle\right\|^{2}=1-p_{i}(t).$

###### Proof.

By Claim 3.5, we have $\Pi_{t}{\lvert}w^{t}(i)\rangle=\Pi_{t}U_{t}^{i}\dots
U_{1}^{i}{\lvert}0,0\rangle$, which is the part of the state after applying
$U_{t}$ that did not already output, but does output in the measurement after
$U_{t}$, so
$\bar{p}_{i}(t)=\left\|\Pi_{t}{\lvert}w^{t}(i)\rangle\right\|^{2}.$ For the
second part, we have

$\left\|{\lvert}w^{t}(i)\rangle\right\|^{2}=\left\|U_{t}^{i}\dots
U_{1}^{i}{\lvert}0,0\rangle\right\|^{2}-\left\|\Pi_{<t}U_{t}^{i}\dots
U_{1}^{i}{\lvert}0,0\rangle\right\|^{2}=1-p_{i}(t),$

since $\Pi_{<t}U_{t}^{i}\dots U_{1}^{i}{\lvert}0,0\rangle$ is the part of the
state that has already halted before $U_{t}$ was applied. ∎

######  Corollary 3.7.

For all $i\in{\cal I}$,

$\displaystyle\left\|{\lvert}w_{-}(i)\rangle\right\|^{2}$
$\displaystyle=2\sum_{t=0}^{{\sf
T}}\alpha_{t}(1-p_{i}(t))=2\mathbb{E}\left[\sum_{t=0}^{T_{i}}\alpha_{t}\right]$
$\displaystyle\mathrm{and}\;\left\|{\lvert}w_{+}(i)\rangle\right\|^{2}$
$\displaystyle=2\sum_{t=0}^{{\sf
T}}\frac{1}{\alpha_{t}}(1-p_{i}(t))=2\mathbb{E}\left[\sum_{t=0}^{T_{i}}\frac{1}{\alpha_{t}}\right].$

###### Proof.

By (16) and the fact that $\sum_{t=1}^{\sf T}\bar{p}_{i}(t)=1$, and letting
$\bar{p}_{i}(0)=0$, we have:

$\displaystyle\left\|{\lvert}w_{-}(i)\rangle\right\|^{2}=\sum_{t=0}^{\sf
T}\alpha_{t}(1-p_{i}(t))$ $\displaystyle=\sum_{t=0}^{\sf
T}\alpha_{t}\sum_{t^{\prime}=t}^{\sf
T}\bar{p}_{i}(t^{\prime})=\sum_{t^{\prime}=0}^{{\sf
T}}\bar{p}_{i}(t^{\prime})\sum_{t=0}^{t^{\prime}}\alpha_{t}=\mathbb{E}\left[\sum_{t=0}^{T_{i}}\alpha_{t}\right].$

A similar computation applies in the positive case. ∎

######  Claim 3.8 (Positive Witness).

Assume ${\sf T}$ is odd. For all $i$, ${\lvert}w_{+}(i)\rangle$ is orthogonal
to all forward and backward transition states, and all reversal states
${\lvert}\psi_{a,z,t}^{i^{\prime},\leftrightarrow}\rangle$ such that
$i^{\prime}\neq i$ or $a^{\prime}\neq g(i)$ (see Definition 3.1). Moreover, if
$\Pi_{\Psi_{b}}$ is the orthogonal projector onto
$\mathrm{span}\\{\Psi_{b}\\}$, then

$\displaystyle\left\|\Pi_{\Psi_{0}}{\lvert}w_{+}(i)\rangle\right\|^{2}$
$\displaystyle\leq 2\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\frac{1}{\alpha_{t}}\bar{p}_{i}(t)\epsilon_{i}^{t}\leq
2\mathbb{E}\left[\frac{\epsilon_{i}^{T_{i}}}{\alpha_{T_{i}}}\right]\text{and}\;\left\|\Pi_{\Psi_{1}}{\lvert}w_{+}(i)\rangle\right\|^{2}\leq
2\sum_{\begin{subarray}{c}t=1\\\ \mathrm{odd}\end{subarray}}^{{\sf
T}}\frac{1}{\alpha_{t}}\bar{p}_{i}(t)\epsilon_{i}^{t}\leq
2\mathbb{E}\left[\frac{\epsilon_{i}^{T_{i}}}{\alpha_{T_{i}}}\right].$

###### Proof.

We start with the forward transition states. We always have
${{\langle}w_{+}(i)|}\psi_{a,z,t}^{i^{\prime},\rightarrow}\rangle=0$ when
$i\neq i^{\prime}$. For all $z\in{\cal Z}_{>t}$, we have:

$\displaystyle{{\langle}\psi_{a,z,t}^{i,\rightarrow}|}w_{+}(i)\rangle={{\langle}a,z|}w^{t}(i)\rangle-{\langle}a,z\rvert(U_{t+1}^{i})^{\dagger}{\lvert}w^{t+1}(i)\rangle={{\langle}a,z|}w^{t}(i)\rangle-{\langle}a,z\rvert(U_{t+1}^{i})^{\dagger}U_{t+1}^{i}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle=0,$

since ${\langle}a,z\rvert\Pi_{\geq t}={\langle}a,z\rvert$ for all $z\in{\cal
Z}_{>t}$. A nearly identical argument holds for the backward transition
states.

Next consider the reversal states. We have

$\displaystyle{{\langle}\psi_{a,z,t}^{i,\leftrightarrow}|}w_{+}(i)\rangle=\left(1-{\langle}i\rvert
A_{a}^{\dagger}A{\lvert}i\rangle\right){{\langle}a,z|}w^{t}(i)\rangle.$ (19)

When $a=g(i)$, so $A_{a}=A_{g(i)}=A$, this is 0, and otherwise we have
$|{{\langle}\psi_{a,z,t}^{i,\leftrightarrow}|}w_{+}(i)\rangle|^{2}\leq
4|{{\langle}a,z|}w^{t}(i)\rangle|^{2}$. Thus:

$\displaystyle\Pi_{\Psi_{0}}{\lvert}w_{+}(i)\rangle$
$\displaystyle=\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf T}-1}\sum_{\begin{subarray}{c}a\in{\cal
A}\setminus\\{g(i)\\}\\\ z\in{\cal
Z}_{t}\end{subarray}}\frac{{\lvert}\psi_{a,z,t}^{i,\leftrightarrow}\rangle{\langle}\psi_{a,z,t}^{i,\leftrightarrow}\rvert}{\left\|{\lvert}\psi_{a,z,t}^{i,\leftrightarrow}\rangle\right\|^{2}}{\lvert}w_{+}(i)\rangle$
$\displaystyle\left\|\Pi_{\Psi_{0}}{\lvert}w_{+}(i)\rangle\right\|^{2}$
$\displaystyle=\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf T}-1}\sum_{\begin{subarray}{c}a\in{\cal
A}\setminus\\{g(i)\\}\\\ z\in{\cal
Z}_{t}\end{subarray}}\frac{|{{\langle}\psi_{a,z,t}^{i,\leftrightarrow}|}w_{+}(i)\rangle|^{2}}{\left\|{\lvert}\psi_{a,z,t}^{i,\leftrightarrow}\rangle\right\|^{2}}\leq\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf T}-1}\sum_{\begin{subarray}{c}a\in{\cal
A}\setminus\\{g(i)\\}\\\ z\in{\cal
Z}_{t}\end{subarray}}\frac{4|{{\langle}a,z|}w^{t}(i)\rangle|^{2}}{2\alpha_{t}}.$

We have, for any $t$,

$\sum_{\begin{subarray}{c}a\in{\cal A}\setminus\\{g(i)\\}\\\ z\in{\cal
Z}_{t}\end{subarray}}|{{\langle}a,z|}w^{t}(i)\rangle|^{2}=\bar{p}_{i}(t)\epsilon_{i}^{t}$

is the probability that the algorithm outputs at time $t$, and the answer is
incorrect (not equal to $g(i)$). Thus:

$\displaystyle\left\|\Pi_{\Psi_{0}}{\lvert}w_{+}(i)\rangle\right\|^{2}$
$\displaystyle\leq 2\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\bar{p}_{i}(t)\frac{1}{\alpha_{t}}\epsilon_{i}^{t}\leq 2\sum_{t=0}^{{\sf
T}}\bar{p}_{i}(t)\frac{1}{\alpha_{t}}\epsilon_{i}^{t}=2\mathbb{E}\left[\frac{\epsilon_{i}^{T_{i}}}{\alpha_{T_{i}}}\right],$

and similarly for $\Psi_{1}$. ∎

######  Claim 3.9 (Negative witness).

Assume ${\sf T}$ is odd. For $i\in{\cal I}$, let ${\lvert}{w}_{-}(i)\rangle$
be the negative history state defined in Definition 3.4. Then, letting
$\Pi_{\Psi_{b}}$ be the orthogonal projector onto
$\mathrm{span}\\{\Psi_{b}\\}$, we have:

$\displaystyle\left\|(I-\Pi_{\Psi_{0}}){\lvert}{w}_{-}(i)\rangle\right\|^{2}$
$\displaystyle\leq 2\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}{\alpha_{t}}\bar{p}_{i}(t)\epsilon^{t}_{i}\leq
2\mathbb{E}\left[\alpha_{T_{i}}\epsilon_{i}^{T_{i}}\right]$
$\displaystyle\text{and}\;\left\|(I-\Pi_{\Psi_{1}})\left({\lvert}{w}_{-}(i)\rangle-({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle){\lvert}0,0\rangle{\lvert}0\rangle\right)\right\|^{2}$
$\displaystyle\leq 2\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf
T}}{\alpha_{t}}\bar{p}_{i}(t)\epsilon^{t}_{i}\leq
2\mathbb{E}\left[\alpha_{T_{i}}\epsilon_{i}^{T_{i}}\right].$

###### Proof.

Recall from Definition 3.4 that

$\displaystyle{\lvert}w_{-}(i)\rangle$
$\displaystyle=\left({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle\right)\sum_{t=0}^{{\sf
T}}\sqrt{\alpha_{t}}(-1)^{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle,$

where ${\lvert}w^{t}(i)\rangle=\Pi_{\geq t}{\lvert}w^{t}(i)\rangle$ by Claim
3.5. We have:

$\displaystyle\sum_{t=0}^{{\sf
T}}\sqrt{\alpha_{t}}(-1)^{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle={}\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\sqrt{\alpha_{t}}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle-\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf
T}}\sqrt{\alpha_{t}}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle$
$\displaystyle={}$ $\displaystyle\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\sqrt{\alpha_{t}}\Pi_{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle+\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf T}-1}\sqrt{\alpha_{t}}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle-\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf T}}\sqrt{\alpha_{t}}\Pi_{\geq
t}U_{t}^{i}{\lvert}w^{t-1}(i)\rangle{\lvert}t\rangle$ $\displaystyle={}$
$\displaystyle\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\sqrt{\alpha_{t}}\Pi_{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle+\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf T}-1}\left(\sqrt{\alpha_{t}}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle-\sqrt{\alpha_{t+1}}U_{t+1}^{i}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t+1\rangle\right)$ $\displaystyle\mbox{by
\hyperref@@ii[eq:U-t-Pi-commute]{(\ref*{eq:U-t-Pi-commute})}}.$

Then since $\Pi_{\geq t+1}{\lvert}w^{t}(i)\rangle$ is supported on states
${\lvert}a,z\rangle$ such that $z\in{\cal Z}_{>t}$, we have:

$\left({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle\right)\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf T}-1}\left(\sqrt{\alpha_{t}}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle-\sqrt{\alpha_{t+1}}U_{t+1}^{i}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t+1\rangle\right)\in\mathrm{span}\\{\Psi_{0}\\}.$

Let $\Xi_{a}$ be the orthogonal projector onto states with $a$ in the answer
register. We can thus see that:

$\begin{split}(I-\Pi_{\Psi_{0}}){\lvert}w_{-}(i)\rangle&=(I-\Pi_{\Psi_{0}})\left({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle\right)\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\sqrt{\alpha_{t}}\Pi_{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle\\\
&\qquad-(I-\Pi_{\Psi_{0}})\underbrace{\left({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A_{g(i)}{\lvert}i\rangle\right)\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\sqrt{\alpha_{t}}\Xi_{g(i)}\Pi_{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle}_{\in\Psi_{0}}\\\
&=(I-\Pi_{\Psi_{0}})\left({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A_{g(i)}{\lvert}i\rangle\right)\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\sqrt{\alpha_{t}}\left(I-\Xi_{g(i)}\right)\Pi_{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle,\end{split}$
(20)

since $A{\lvert}i\rangle=A_{g(i)}{\lvert}i\rangle$. Thus:

$\displaystyle\left\|(I-\Pi_{\Psi_{0}}){\lvert}w_{-}(i)\rangle\right\|^{2}$
$\displaystyle\leq\left\|\left({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A_{g(i)}{\lvert}i\rangle\right)\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\sqrt{\alpha_{t}}\left(I-\Xi_{g(i)}\right)\Pi_{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle\right\|^{2}$
$\displaystyle=2\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}{\alpha_{t}}\left\|\left(I-\Xi_{g(i)}\right)\Pi_{t}{\lvert}w^{t}(i)\rangle\right\|^{2}=2\sum_{\begin{subarray}{c}t=0\\\
\mathrm{even}\end{subarray}}^{{\sf
T}-1}\bar{p}_{i}(t){\alpha_{t}}\epsilon^{t}_{i}\leq
2\mathbb{E}\left[\alpha_{T_{i}}\epsilon_{i}^{T_{i}}\right].$

For the second part of the claim, we note that:

$\displaystyle\sum_{t=0}^{{\sf
T}}\sqrt{\alpha_{t}}(-1)^{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle$
$\displaystyle={}$
$\displaystyle\sqrt{\alpha_{0}}{\lvert}w^{0}(i)\rangle{\lvert}0\rangle-\sqrt{\alpha_{{\sf
T}}}{\lvert}w^{{\sf T}}(i)\rangle{\lvert}{\sf T}\rangle$
$\displaystyle\quad-\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf
T}-2}\sqrt{\alpha_{t}}\Pi_{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle-\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf T}-2}\left(\sqrt{\alpha_{t}}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle-\sqrt{\alpha_{t+1}}U_{t+1}^{i}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t+1\rangle\right)$ $\displaystyle={}$
$\displaystyle{\lvert}0,0\rangle{\lvert}0\rangle-\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf
T}}\sqrt{\alpha_{t}}\Pi_{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle-\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf T}-2}\left(\sqrt{\alpha_{t}}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle-\sqrt{\alpha_{t+1}}U_{t+1}^{i}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t+1\rangle\right),$

since $\alpha_{0}=1$, ${\lvert}w^{0}(i)\rangle={\lvert}0,0\rangle$, and
${\lvert}w^{{\sf T}}(i)\rangle$ is in the support of $\Pi_{\geq{\sf
T}}=\Pi_{{\sf T}}$. Similar to above, we have

$\displaystyle({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle)\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf T}-2}\left(\sqrt{\alpha_{t}}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle-\sqrt{\alpha_{t+1}}U_{t+1}^{i}\Pi_{\geq
t+1}{\lvert}w^{t}(i)\rangle{\lvert}t+1\rangle\right)\in\Psi_{1},$

and just as in (20),

$\displaystyle(I-\Pi_{\Psi_{1}})({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle)\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf
T}}\sqrt{\alpha_{t}}\Pi_{t}{\lvert}w^{t}(i)\rangle{\lvert}t\rangle$
$\displaystyle={}$
$\displaystyle(I-\Pi_{\Psi_{1}})({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle)\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf
T}}\sqrt{\alpha_{t}}\Pi_{t}(I-\Xi_{g(i)}){\lvert}w^{t}(i)\rangle{\lvert}t\rangle.$

Thus, we can see that:

$(I-\Pi_{\Psi_{1}})\left({\lvert}w_{-}(i)\rangle-({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle){\lvert}0,0\rangle{\lvert}0\rangle\right)\\\
=(I-\Pi_{\Psi_{1}})({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle)\left({\lvert}0,0\rangle{\lvert}0\rangle-\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf
T}}\sqrt{\alpha_{t}}\Pi_{t}(I-\Xi_{g(i)}){\lvert}w^{t}(i)\rangle{\lvert}t\rangle-{\lvert}0,0\rangle{\lvert}0\rangle\right)$
$\mbox{so
}\left\|(I-\Pi_{\Psi_{1}})\left({\lvert}w_{-}(i)\rangle-({\lvert}\rightarrow\rangle{\lvert}i\rangle-{\lvert}\leftarrow\rangle
A{\lvert}i\rangle){\lvert}0,0\rangle{\lvert}0\rangle\right)\right\|^{2}\\\
\leq 2\sum_{\begin{subarray}{c}t=1\\\ \mathrm{odd}\end{subarray}}^{{\sf
T}}{\alpha_{t}}\left\|\Pi_{t}(I-\Xi_{g(i)}){\lvert}w^{t}(i)\rangle\right\|^{2}=2\sum_{\begin{subarray}{c}t=1\\\
\mathrm{odd}\end{subarray}}^{{\sf
T}}\bar{p}_{i}(t){\alpha_{t}}\epsilon_{t}^{i}\leq
2\mathbb{E}\left[\alpha_{T_{i}}\epsilon_{i}^{T_{i}}\right].\qed$

##  4 Composition in Quantum Walks

In this section, we state and prove Theorem 4.1, which extends the quantum
walk electric network framework by allowing a variable-time subroutine to
implement the edge transition subroutine. This is similar to [JZ22, Theorem
3.10], with the following differences:

  1. 1.

We require that our transition subroutine be _reversible_ , meaning that the
mapping ${\lvert}u,i\rangle\mapsto{\lvert}v,j\rangle$ must be done by first
computing some auxiliary information $g(u,i)$, from which the transition
becomes easy (see Section 3). This is not required in [JZ22], but it is not a
particularly stringent constraint, and we know of no quantum walk application
where the transition is not done this way.

  2. 2.

[JZ22] does not allow the running time $T_{u,v}$ for some fixed $(u,v)$ to be
a random variable, but instead depends on a parameter ${\sf T}_{u,v}$, which
is an upper bound on the running time on input $(u,v)$, and requires that this
value be efficiently computable from $(u,i)$ and $(v,j)$ (where $f_{u}(i)=v$
and $f_{v}(j)=u$). We do not require $\mathbb{E}[T_{u,v}]$ to be efficiently
computable.

  3. 3.

In [JZ22], there are no parameters $\\{\alpha_{t}\\}_{t}$ (equivalently,
$\alpha_{t}=1$ for all $t$).

  4. 4.

[JZ22] also extends the electric network framework by allowing the use of
_alternative neighbourhoods_. For simplicity, we do not incude this extension
here, but there is no reason it could not be combined with our results.

We first state Theorem 4.1, which is too general to be easily understood.
Immediately afterwards, we discuss some more easily understood consequences of
this theorem, for quantum walks (Corollary 4.2 and Corollary 4.3) and the
special case of black-box search (Corollary 4.4 and Table 1), before proving
the theorem in Section 4.1.

######  Theorem 4.1 (Quantum Walks with Edge Composition).

Fix the following, which may implicitly depend on some input $x$:

  * •

a network $G$ with disjoint sets $V_{0},V_{\sf M}\subset V(G)$ such that for
any vertex, checking if $v\in V_{0}$ (resp. if $v\in V_{\sf M}$) can be done
in unit complexity;

  * •

a reversible variable-time subroutine (see Section 3) that implements the
transition map (see Definition 2.2) with stopping times
$\\{T_{u,v}\\}_{(u,v)\in\overrightarrow{E}(G)}$, which are random variables on
$[{\sf T}]$, and errors
$\\{\epsilon_{u,v}^{t}\\}_{(u,v)\in\overrightarrow{E}(G),t\in[{\sf T}]}$;

  * •

a subset $M\subseteq V_{\sf M}$, and distribution $\sigma$ on $V_{0}$.

Fix some positive real numbers $\\{\alpha_{t}\\}_{t=0}^{{\sf T}}$ such that
$\alpha_{0}=1$; and positive real-valued ${\cal W}$ and ${\cal R}$, that may
scale with $|x|$. Suppose the following conditions hold.

Setup Subroutine:

The state ${\lvert}\sigma\rangle=\sum_{u\in
V_{0}}\sqrt{\sigma(u)}{\lvert}u\rangle$ can be generated in cost ${\sf S}$,
and furthermore, for any $u\in V_{0}$, $\sigma(u)$ can be computed in unit
cost.

Star State Generation Subroutine:

There is a subroutine that generates
$\\{{\lvert}\psi_{\star}^{G}(u)\rangle\\}_{u\in V(G)}$ in unit cost (see
Definition 2.2).

Checking Subroutine:

There is an algorithm that checks, for any $u\in V_{\sf M}$, if $u\in M$, in
unit cost.

Positive Condition:

If $M\neq\emptyset$, then there exists a flow $\theta$ on $G$ (see Definition
2.3) such that:

P1

The boundary of $\theta$ is in $V_{0}\cup M$, and $\sum_{u\in
V_{0}}\theta(u)=1$.666A $\sigma$-$M$-flow always satisfies conditions P1 and
P2. While we do not make it a strict requirement that all sources are in
$V_{0}$ and all sinks in $M$, P1 implies that we do not simply have flow
coming in at $V_{0}$ and then leaving again at $V_{0}$. P2 implies that the
flow in $V_{0}$ is roughly distributed as $\sigma$.

P2

$\frac{1}{3}\leq\sum_{u\in V_{0}}\frac{\theta(u)^{2}}{\sigma(u)}\leq 3$.

P3

$\displaystyle\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{\alpha_{t}}\right]\leq{\cal
R}$.

P4

$\displaystyle\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\frac{\epsilon_{u,v}^{T_{u,v}}}{\alpha_{T_{u,v}}}\right]=o(1/{\cal
W})$;

Negative Condition:

If $M=\emptyset$, then

N1

$\displaystyle\sum_{(u,v)\in\overrightarrow{E}(G)}{\sf
w}_{u,v}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}-1}\alpha_{t}\right]\leq{\cal W}$.

N2

$\displaystyle\sum_{(u,v)\in\overrightarrow{E}(G)}{\sf
w}_{u,v}\mathbb{E}\left[\alpha_{T_{u,v}}\epsilon_{u,v}^{T_{u,v}}\right]=o(1/{\cal
R})$;

Then there is a quantum algorithm that decides if $M=\emptyset$ or not with
bounded error in complexity:

$O\left({\sf S}+\sqrt{{\cal R}{\cal W}}\cdot\log{\sf T}\right).$

We prove Theorem 4.1 in Section 4.1 by defining a phase estimation algorithm
and analysing it using Theorem 2.11. First, we give some less general, easier
to digest, corollaries of Theorem 4.1. One thing that probably makes Theorem
4.1 particularly hard to parse is the parameters $\\{\alpha_{t}\\}_{t=0}^{\sf
T}$, so we mention three cases of special interest. First, if we set
$\alpha_{t}=1$ for all $t$, then we recover a version of [JZ22, Theorem 3.10]:
the resulting complexities are as if we had replaced the graph $G$ with a
graph $G^{\sf T}$, in which each edge $(u,v)$ is replaced by a path of length
$\mathbb{E}[T_{u,v}]+1$ (or an upper bound on $T_{u,v}+1$, in the case of
[JZ22]), but now each transition has unit cost.

We mention two other interesting choices of $\\{\alpha_{t}\\}_{t}$ that lead
to two distinct “variable-time” quantum walk results. First, if we set
$\alpha_{t}=t+1$, we satisfy the requirement $\alpha_{0}=1$, and we get:

$\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{\alpha_{t}}\right]=\mathbb{E}\left[\sum_{t=1}^{T_{u,v}+1}\frac{1}{t}\right]=\Theta(\mathbb{E}[\log
T_{u,v}])\mbox{ and
}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}{\alpha_{t}}\right]=\mathbb{E}\left[\sum_{t=1}^{T_{u,v}+1}t\right]=\Theta(\mathbb{E}[T_{u,v}^{2}]).$

Thus P3 has only a logarithmic dependence on the transition times, whereas we
get a weighted $\ell_{2}$-average in N1. On the other hand, by setting
$\alpha_{t}=\frac{1}{1+t}$, $\mathbb{E}[\log T_{u,v}]$ and
$\mathbb{E}[T_{u,v}^{2}]$ are swapped: now P3 has a (different!) weighted
$\ell_{2}$-average, whereas N1 just has a log factor.

If we additionally know the values $\mathbb{E}[T_{u,v}]$, then we can use
$\alpha_{t}=1$ for all $t$, and scale ${\sf w}_{u,v}$ by a factor of
$\mathbb{E}[T_{u,v}]$ to get:

$\mathbf{P3:}\;\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\leq{\cal
R}\quad\mathbf{N1:}\;\sum_{(u,v)\in\overrightarrow{E}(G)}{\sf
w}_{u,v}\mathbb{E}[T_{u,i}]^{2}\leq{\cal W},$

or alternatively, scaling ${\sf w}_{u,v}$ by $1/\mathbb{E}[T_{u,v}]$ gives:

$\mathbf{P3:}\;\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}[T_{u,i}]^{2}\leq{\cal
R}\quad\mathbf{N1:}\;\sum_{(u,v)\in\overrightarrow{E}(G)}{\sf
w}_{u,v}\leq{\cal W}.$

Thus, when the expected stopping times are known, we can save a log factor,
and also replace $\mathbb{E}[T_{u,v}^{2}]$ with $\mathbb{E}[T_{u,v}]^{2}$,
which is better the higher the variance. We formally state these results for
$\alpha_{t}=t+1$ in the following corollary (the $\alpha_{t}=1/(t+1)$ case can
be worked out from Theorem 4.1, but is less elegantly stated). We simplify
things by only considering flows that are exactly from $\sigma$ to $M$, and
assuming our subroutine has no error, but by Theorem 4.1, it is clear that
some deviation would also be tolerable.777In all the applications discussed in
this section, we assume the subroutine has no error, for simplicity. We
believe it is also interesting to further investigate the different ways the
error can propagate depending on the choice of $\\{\alpha_{t}\\}_{t}$, but we
leave this for future work. It is also possible, as in the case of the results
of Section 5, that our error terms can be improved.

######  Corollary 4.2 (Variable-time quantum walks ($\alpha_{t}=t+1$)).

Fix a network $G$; marked set $M\subset V(G)$, and initial distribution
$\sigma$ on $V(G)$, all of which may implicitly depend on an input $x$,
although for simplicity, we assume ${\cal W}(G)$ only depends on $|x|$. Let
$P$ be the transition matrix for the random walk on $G$, and $\pi$ its
stationary distribution. Let ${\sf S}$ be the cost of generating
${\lvert}\sigma\rangle$, and suppose
$\\{{\lvert}\psi_{\star}^{G}(u)\rangle\\}_{u\in V(G)}$ can be generated in
unit cost. Let ${\cal C}_{\sigma,{\sf M}}$ be an upper bound on ${\cal
R}_{\sigma,M}(G){\cal W}(G)$ (see Definition 2.3) whenever $M\neq\emptyset$.

Suppose there is a variable-time subroutine888A variable-time subroutine that
computes a bit is always reversible. that checks, for any $u\in V(G)$, if
$u\in M$, with stopping times $\\{C_{u}\\}_{u\in V(G)}$, which are random
variables on $[{\sf C}]$, and all errors zero. Fix some (known) _terminal_
distribution $\tau$ on $V(G)$ such that $\tau(M)\geq\varepsilon$ whenever
$M\neq\emptyset$, and let ${\sf C}_{\mathrm{avg}}$ and ${\sf
C}_{\mathrm{avg}}^{\prime}$ be upper bounds such that whenever $M=\emptyset$,

$\sqrt{\sum_{u\in V(G)}\tau(u)\mathbb{E}[C_{u}^{2}]}\leq{\sf
C}_{\mathrm{avg}},\quad\mbox{and}\quad\sqrt{\sum_{u\in
V(G)}\tau(u)\mathbb{E}[C_{u}]^{2}}\leq{\sf C}_{\mathrm{avg}}^{\prime}.$

Suppose there is a reversible variable-time subroutine that implements the
transition map with stopping times
$\\{T_{u,v}\\}_{(u,v)\in\overrightarrow{E}(G)}$, which are random variables on
$[{\sf T}]$, and all errors zero. Let ${\sf T}_{\mathrm{avg}}$ and ${\sf
T}_{\mathrm{avg}}^{\prime}$ be upper bounds such that whenever $M=\emptyset$,

$\sqrt{\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]}\leq{\sf
T}_{\mathrm{avg}},\quad\mbox{and}\quad\sqrt{\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}]^{2}}\leq{\sf
T}_{\mathrm{avg}}^{\prime}.$

_Claim 0:_ Suppose the checking cost is trivial, meaning for all $u\in V(G)$,
$\mathbb{E}[C_{u}]=O(1)$. Then there is a quantum algorithm that detects if
$M=\emptyset$ with bounded error in complexity:

$O\left({\sf S}+\sqrt{{\cal C}_{\sigma,{\sf M}}}{\sf
T}_{\mathrm{avg}}\log^{1.5}{\sf T}\right).$

Suppose in addition that the values $\mathbb{E}[T_{u,v}]=\mathbb{E}[T_{u,i}]$
are computable in the strong sense that for any $u$, we can generate a
superposition proportional to $\sum_{i\in L(u)}\sqrt{{\sf
w}_{u,i}\mathbb{E}[T_{u,i}]}{\lvert}i\rangle$, and we have query access to
${\sf w}_{u}^{\prime}=\sum_{i\in L(u)}{\sf w}_{u,i}\mathbb{E}[T_{u,i}]$. Then
there is a quantum algorithm that detects if $M=\emptyset$ with bounded error
in complexity:

$O\left({\sf S}+\sqrt{{\cal C}_{\sigma,{\sf M}}}{\sf
T}_{\mathrm{avg}}^{\prime}\log{\sf T}\right).$

_Claim I:_ Let ${\cal D}_{{\sf M}}$ be an upper bound such that $\sum_{u\in
M}{\theta(u)^{2}}/{\tau_{M}(u)}\leq{\cal D}_{{\sf M}}$, where $\theta$ is the
unit flow from $\sigma$ to $M$ with minimal energy and
$\tau_{M}(u)=\tau(u)/\tau(M)$ is the normalized restriction of $\tau$ to $M$,
whenever $M\neq\emptyset$. Then there is a quantum algorithm that detects if
$M=\emptyset$ with bounded error in complexity:

$O\left({\sf S}+\left(\sqrt{{\cal C}_{\sigma,{\sf M}}}{\sf
T}_{\mathrm{avg}}+\sqrt{\frac{{\cal D}_{{\sf M}}}{\varepsilon}}{\sf
C}_{\mathrm{avg}}\right)\log^{1.5}({\sf TC})\right).$

Suppose in addition that the values $\mathbb{E}[T_{u,v}]$ are computable in
the same strong sense as Claim 0, and $\mathbb{E}[C_{u}]$ are computable in
the the sense that for any $u\in V(G)$, we can query $\mathbb{E}[C_{u}]$ in
unit cost. Then there is a quantum algorithm that detects in $M=\emptyset$
with bounded error in complexity:

$O\left({\sf S}+\left(\sqrt{{\cal C}_{\sigma,{\sf M}}}{\sf
T}_{\mathrm{avg}}^{\prime}+\sqrt{\frac{{\cal D}_{{\sf M}}}{\varepsilon}}{\sf
C}_{\mathrm{avg}}^{\prime}\right)\log({\sf TC})\right).$

_Claim II:_ Suppose we are promised that either $M=\emptyset$, or $|M|=1$.
Then there is a quantum algorithm that detects if $M=\emptyset$ with bounded
error in complexity:

$O\left({\sf S}+\left(\sqrt{{\cal C}_{\sigma,{\sf M}}}{\sf
T}_{\mathrm{avg}}+\frac{1}{\sqrt{\varepsilon}}{\sf
C}_{\mathrm{avg}}\right)\log^{1.5}({\sf TC})\right).$

Suppose in addition that the values $\mathbb{E}[T_{u,v}]$ and
$\mathbb{E}[C_{u}]$ are computable as in Claim I. Then there is a quantum
algorithm that detects in $M=\emptyset$ with bounded error in complexity:

$O\left({\sf S}+\left(\sqrt{{\cal C}_{\sigma,{\sf M}}}{\sf
T}_{\mathrm{avg}}^{\prime}+\frac{1}{\sqrt{\varepsilon}}{\sf
C}_{\mathrm{avg}}^{\prime}\right)\log({\sf TC})\right).$

_Claim III:_ Let ${\cal C}_{\sigma,\tau}$ be an upper bound on ${\cal
W}(G){\cal R}_{\sigma,\tau_{M}}(G)$ (see Definition 2.3). Then there is a
quantum algorithm that detects if $M=\emptyset$ with bounded error in
complexity:

$O\left({\sf S}+\left(\sqrt{{\cal C}_{\sigma,\tau}}{\sf
T}_{\mathrm{avg}}+\frac{1}{\sqrt{\varepsilon}}{\sf
C}_{\mathrm{avg}}\right)\log^{1.5}{\sf TC}\right).$

Suppose in addition that the values $\mathbb{E}[T_{u,v}]$ and
$\mathbb{E}[C_{u}]$ are computable as in Claim I. Then there is a quantum
algorithm that detects in $M=\emptyset$ with bounded error in complexity:

$O\left({\sf S}+\left(\sqrt{{\cal C}_{\sigma,\tau}}{\sf
T}_{\mathrm{avg}}^{\prime}+\frac{1}{\sqrt{\varepsilon}}{\sf
C}_{\mathrm{avg}}^{\prime}\right)\log{\sf TC}\right).$

###### Proof.

Let $g_{u}=1$ if $u\in M$, and $g_{u}=0$ else. We will make a new graph
$G^{\prime}$, which is obtained from $G$ by adding, for each vertex $u\in
V(G)$, a new vertex $(u,g_{u})$ connected only to $u$ by an edge of weight
${\sf w}_{u,{\sf M}}$, to be defined. That is,

$\displaystyle V(G^{\prime})$
$\displaystyle:=\underbrace{V(G)}_{=:V_{0}}\cup\underbrace{\\{(u,g_{u}):u\in
V(G)\\}}_{=:V_{\sf M}}\mbox{and
}\overrightarrow{E}(G^{\prime}):=\overrightarrow{E}(G)\cup\\{(u,(u,g_{u})):u\in
V(G)\\},$

with ${\sf w}_{u,(u,g_{u})}={\sf w}_{u,{\sf M}}$. Then let
$M^{\prime}=M\times\\{1\\}\subseteq V_{\sf M}$ be the marked set of
$G^{\prime}$. The new edges $(u,(u,g_{u}))$ will have label $0$, in both
directions, so: $f_{u}(0)=(u,g_{u})$ and $f_{(u,g_{u})}(0)=u$. Since we can
generate $\\{{\lvert}\psi_{\star}^{G}(u)\rangle\\}_{u\in V(G)}$ in unit cost,
we can also generate

$\\{{\lvert}\psi_{\star}^{G^{\prime}}(u)\rangle={\lvert}\psi_{\star}^{G}(u)\rangle+\sqrt{{\sf
w}_{u,{\sf M}}}{\lvert}0\rangle\\}_{u\in V(G)}$

in unit cost, assuming ${\sf w}_{u,{\sf M}}$ is chosen so that we can prepare
a state proportional to $\sqrt{{\sf w}_{u}}{\lvert}1\rangle+\sqrt{{\sf
w}_{u,{\sf M}}}{\lvert}0\rangle$. For any $u\in V_{\sf M}$, we can check if
$u\in M^{\prime}$ in unit cost by examining $g_{u}$, and generate
${\lvert}\sigma\rangle$ in cost ${\sf S}$, by assumption. Thus, to apply
Theorem 4.1, we just need to check the positive and negative conditions. P4
and N2 are satisfied because we assume no error, and for the positive
condition, we will always choose $\theta$ to be a $\sigma$-$M^{\prime}$ flow,
so P1 and P2 are automatically satisifed. We thus only need to check P3 and
N1. We will use $\alpha_{t}=t+1$ for the first half of the proof of each
claim, and $\alpha_{t}=1$ for the second half. We note that we immediately
have a variable-time subroutine for the transition map with
$T_{u,(u,g_{u})}=C_{u}$.

Proof of Claim 0: To prove Claim 0, we let ${\sf w}_{u,{\sf M}}:={\sf w}_{u}.$
Note that this makes preparing a state proportional to $\sqrt{{\sf
w}_{u}}{\lvert}0\rangle+\sqrt{{\sf w}_{u,{\sf M}}}{\lvert}1\rangle$ trivial.

P3: Let $\theta$ be the flow from $\sigma$ to $M$ with minimal energy ${\cal
R}_{\sigma,M}(G)$ (see Definition 2.3), and extend it to a flow on
$G^{\prime}$ from $\sigma$ to $M^{\prime}$ by setting
$\theta(u,(u,g_{u}))=\theta(u)$ for all $u\in M$. Then:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{t+1}\right]&=\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{t+1}\right]+\sum_{u\in
M}\frac{\theta(u)^{2}}{{\sf w}_{u,{\sf
M}}}\mathbb{E}\left[\sum_{t=0}^{C_{u}}\frac{1}{t+1}\right]\\\ &\leq{\cal
R}_{\sigma,M}(G)(\ln({\sf T}+1)+1)+\frac{3}{2}\sum_{u\in
M}\frac{\theta(u)^{2}}{{\sf w}_{u}}\end{split}$ (21)

since $C_{u}=1$ for all $u$, by assumption. By Jensen’s inequality, we have:

$\displaystyle\left(\frac{\sum_{v\in\Gamma(u)}{\sf
w}_{u,v}\frac{\theta(u,v)}{{\sf w}_{u,v}}}{\sum_{v\in\Gamma(u)}{\sf
w}_{u,v}}\right)^{2}$ $\displaystyle\leq\frac{\sum_{v\in\Gamma(u)}{\sf
w}_{u,v}\left(\frac{\theta(u,v)}{{\sf
w}_{u,v}}\right)^{2}}{\sum_{v\in\Gamma(u)}{\sf w}_{u,v}}$
$\displaystyle\frac{\left(\sum_{v\in\Gamma(u)}\theta(u,v)\right)^{2}}{\sum_{v\in\Gamma(u)}{\sf
w}_{u,v}}$ $\displaystyle\leq\sum_{v\in\Gamma(u)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}$ $\displaystyle\sum_{u\in M}\frac{\theta(u)^{2}}{{\sf w}_{u}}$
$\displaystyle\leq\sum_{u\in M}\sum_{v\in\Gamma(u)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\leq{\cal R}_{\sigma,M}(G),$

so we can continue from (21), using ${\cal W}(G){\cal
R}_{\sigma,M}(G)\leq{\cal C}_{\sigma,{\sf M}}$:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{t+1}\right]&\leq
4\frac{{\cal C}_{\sigma,{\sf M}}}{{\cal W}(G)}\ln{\sf T}=:{\cal
R}.\end{split}$ (22)

N1: We use $\pi(u)P_{u,v}=\frac{{\sf w}_{u,v}}{2{\cal W}(G)}$ from (13). If
$M=\emptyset$, we have:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}{\sf
w}_{u,v}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}({t+1})\right]&=\sum_{(u,v)\in\overrightarrow{E}(G)}{\sf
w}_{u,v}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}({t+1})\right]+\sum_{u\in
V(G)}{\sf w}_{u,{\sf M}}\mathbb{E}\left[\sum_{t=0}^{C_{u}}({t+1})\right]\\\
&\leq 2{\cal
W}(G)\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]+2\sum_{u\in
V(G)}{\sf w}_{u}\\\ &\leq 2{\cal W}(G){\sf T}_{\mathrm{avg}}^{2}+2{\cal
W}(G)=:{\cal W}.\end{split}$ (23)

To complete the first half of the proof of Claim 0, we apply Theorem 4.1 using
the fact that:

$\displaystyle\sqrt{\cal RW}$ $\displaystyle=O\left(\sqrt{{\cal
C}_{\sigma,{\sf M}}{\sf T}_{\mathrm{avg}}^{2}\log{\sf T}}\right).$

Known $\mathbb{E}[T_{u,v}]$: For the second half of Claim 0, we scale the
weights of $G^{\prime}$ as follows:

$\forall(u,v)\in\overrightarrow{E}(G),\;{\sf w}_{u,v}^{\prime}:={\sf
w}_{u,v}\mathbb{E}[T_{u,v}]\quad\mbox{and}\quad\forall u\in{V}(G),\;{\sf
w}_{u,{\sf M}}^{\prime}:={\sf w}_{u,{\sf M}}={\sf w}_{u}.$

Note that by changing the weights, we have changed the star states, but we can
generate them by first generating a state proportional to $\sum_{i\in
L(u)}\sqrt{{\sf w}_{u,i}\mathbb{E}[T_{u,i}]}{\lvert}i\rangle$, which we assume
can be done in unit cost, and then putting a phase in front of each
${\lvert}i\rangle$ depending on if $i\in L^{+}(u)$ or $i\in L^{-}(u)$. We have
also changed the total weight of each vertex, ${\sf
w}_{u}^{\prime}=\sum_{i}{\sf w}_{u,i}\mathbb{E}[T_{u,i}]$, but we assume we
still have query access to these values.

Then for P3, now using $\alpha_{t}=1$, in place of (21) and (22), we have:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}^{\prime}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}1\right]&=\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}\mathbb{E}[T_{u,v}]}\mathbb{E}\left[T_{u,v}+1\right]+\sum_{u\in
M}\frac{\theta(u)^{2}}{{\sf w}_{u}}\mathbb{E}\left[C_{u}+1\right]\\\ &\leq
2{\cal R}_{\sigma,M}(G)+2{\cal R}_{\sigma,M}(G)\leq 4\frac{{\cal
C}_{\sigma,{\sf M}}}{{\cal W}(G)}=:{\cal R}^{\prime},\end{split}$ (24)

and for N1, in place of (23), we have:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}{\sf
w}_{u,v}^{\prime}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}1\right]&=\sum_{(u,v)\in\overrightarrow{E}(G)}{\sf
w}_{u,v}\mathbb{E}[T_{u,v}]\mathbb{E}\left[T_{u,v}+1\right]+\sum_{u\in
V(G)}{\sf w}_{u}\mathbb{E}\left[{C_{u}}+1\right]\\\ &\leq 4{\cal
W}(G)\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}]^{2}+2{\cal
W}(G)\\\ &\leq 4{\cal W}(G)({\sf T}_{\mathrm{avg}}^{\prime})^{2}+2{\cal
W}(G)=:{\cal W}^{\prime}.\end{split}$ (25)

Then a simple calculation of $\sqrt{{\cal R}^{\prime}{\cal W}^{\prime}}$ shows
that the second part of Claim 0 follows from Theorem 4.1.

Proof of Claim I: For the proof of Claim I, we now let

${\sf w}_{u,{\sf M}}:=\frac{{\cal W}(G){\cal D}_{\sf
M}\tau(u)}{\varepsilon{\cal C}_{\sigma,{\sf M}}}=\frac{{\cal W}(G){\cal
D}_{\sf M}\tau_{M}(u)\tau(M)}{\varepsilon{\cal C}_{\sigma,{\sf M}}}\mbox{ if
}u\in M.$

With this choice of ${\sf w}_{u,{\sf M}}$, preparing a state proportional to
$\sqrt{{\sf w}_{u}}{\lvert}1\rangle+\sqrt{{\sf w}_{u,{\sf
M}}}{\lvert}0\rangle$ can be done using a single qubit rotation that depends
on $\frac{{\cal W}(G){\cal D}_{{\sf M}}}{\varepsilon{\cal C}_{\sigma,{\sf
M}}}\frac{\tau(u)}{{\sf w}_{u}}$.

P3: Let $\theta$ be the flow from $\sigma$ to $M$ with minimal energy ${\cal
R}_{\sigma,M}(G)$ (see Definition 2.3), and extend it to a flow on
$G^{\prime}$ from $\sigma$ to $M^{\prime}$ by setting
$\theta(u,(u,g_{u}))=\theta(u)$ for all $u\in M$. Then we have:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{t+1}\right]&=\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{t+1}\right]+\sum_{u\in
M}\frac{\theta(u)^{2}}{{\sf w}_{u,{\sf
M}}}\mathbb{E}\left[\sum_{t=0}^{C_{u}}\frac{1}{t+1}\right]\\\ &\leq 2{\cal
R}_{\sigma,M}(G)\ln{\sf T}+2\frac{{\cal C}_{\sigma,{\sf M}}}{{\cal W}(G){\cal
D}_{\sf M}}\frac{\varepsilon}{\tau(M)}\sum_{u\in
M}\frac{\theta(u)^{2}}{\tau_{M}(u)}\ln{\sf C}\\\ &\leq 2\frac{{\cal
C}_{\sigma,{\sf M}}}{{\cal W}(G)}\ln{\sf T}+2\frac{{\cal C}_{\sigma,{\sf
M}}}{{\cal W}(G)}\ln{\sf C}=:{\cal R},\end{split}$ (26)

where we used ${\cal W}(G){\cal R}_{\sigma,M}\leq{\cal C}_{\sigma,{\sf M}}$,
$\sum_{u\in M}\theta(u)^{2}/\tau_{M}(u)\leq{\cal D}_{\sf M}$ and
$\varepsilon\leq\tau(M)$.

N1: If $M=\emptyset$, we have:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}{\sf
w}_{u,v}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}({t+1})\right]&=\sum_{(u,v)\in\overrightarrow{E}(G)}{\sf
w}_{u,v}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}({t+1})\right]+\sum_{u\in
V(G)}{\sf w}_{u,{\sf M}}\mathbb{E}\left[\sum_{t=0}^{C_{u}}({t+1})\right]\\\
&\leq 2{\cal
W}(G)\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]+\sum_{u\in
V(G)}\frac{{\cal W}(G){\cal D}_{\sf M}\tau(u)}{\varepsilon{\cal
C}_{\sigma,{\sf M}}}\mathbb{E}[C_{u}^{2}]\\\ &\leq 2{\cal W}(G){\sf
T}_{\mathrm{avg}}^{2}+\frac{{\cal W}(G){\cal D}_{\sf M}}{{\cal C}_{\sigma,{\sf
M}}}\frac{1}{\varepsilon}{\sf C}_{\mathrm{avg}}^{2}=:{\cal W}.\end{split}$
(27)

To complete the first half of the proof of Claim I, we apply Theorem 4.1 using
the fact that:

$\displaystyle\sqrt{\cal RW}$ $\displaystyle=O\left(\sqrt{\left({\cal
C}_{\sigma,{\sf M}}{\sf T}_{\mathrm{avg}}^{2}+\frac{{\cal D}_{\sf
M}}{\varepsilon}{\sf C}_{\mathrm{avg}}^{2}\right)\log{\sf TC}}\right).$

Known $\mathbb{E}[T_{u,v}]$ and $\mathbb{E}[C_{u}]$: For the second half of
Claim I, we scale the weights of $G^{\prime}$ as follows:

$\forall(u,v)\in\overrightarrow{E}(G),\;{\sf w}_{u,v}^{\prime}:={\sf
w}_{u,v}\mathbb{E}[T_{u,v}]\mbox{ and }\forall u\in V(G),\;{\sf w}_{u,{\sf
M}}^{\prime}:={\sf w}_{u,{\sf M}}\mathbb{E}[C_{u}]=\frac{{\cal W}(G){\cal
D}_{{\sf M}}\tau(u)\mathbb{E}[C_{u}]}{\varepsilon{\cal C}_{\sigma,{\sf M}}}.$
(28)

Note that by changing the weights, we have changed the star states, but we can
generate them as follows. Let ${\sf w}_{u}^{\prime}=\sum_{i\in L(u)}{\sf
w}_{u,i}\mathbb{E}[T_{u,i}]$, which we can query, by assumption. Then we first
prepare a state proportional to $\sqrt{{\sf
w}_{u}^{\prime}}{\lvert}1\rangle+\sqrt{{\sf w}_{u,{\sf
M}}\mathbb{E}[C_{u}]}{\lvert}0\rangle$, using a single qubit rotation, and
then map ${\lvert}1\rangle$ to a state proportional to $\sum_{i\in
L(u)}\sqrt{{\sf w}_{u,i}\mathbb{E}[T_{u,i}]}{\lvert}i\rangle$, which we assume
can be done in unit cost. Then all that remains to be done is to put a phase
in front of each ${\lvert}i\rangle$ depending on if $i\in L^{+}(u)$ or $i\in
L^{-}(u)$.

Then for the positive analysis, now using $\alpha_{t}=1$, in place of (26), we
have:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}^{\prime}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}1\right]&=\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}\mathbb{E}[T_{u,v}]}\mathbb{E}\left[T_{u,v}+1\right]+\sum_{u\in
M}\frac{\theta(u)^{2}}{{\sf w}_{u,{\sf
M}}\mathbb{E}[C_{u}]}\mathbb{E}\left[C_{u}+1\right]\\\ &\leq 2{\cal
R}_{\sigma,M}(G)+2\frac{{\cal C}_{\sigma,{\sf M}}}{{\cal W}(G){\cal D}_{\sf
M}}\frac{\varepsilon}{\tau(M)}\sum_{u\in
M}\frac{\theta(u)^{2}}{\tau_{M}(u)}\\\ &\leq 2\frac{{\cal C}_{\sigma,{\sf
M}}}{{\cal W}(G)}+2\frac{{\cal C}_{\sigma,M}}{{\cal W}(G)}=:{\cal
R}^{\prime},\end{split}$ (29)

and for the negative analysis, in place of (27), we have:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}{\sf
w}_{u,v}^{\prime}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}1\right]&=\sum_{(u,v)\in\overrightarrow{E}(G)}{\sf
w}_{u,v}\mathbb{E}[T_{u,v}]\mathbb{E}\left[T_{u,v}+1\right]+\sum_{u\in
V(G)}{\sf w}_{u,{\sf M}}\mathbb{E}[C_{u}]\mathbb{E}\left[{C_{u}}+1\right]\\\
&\leq 4{\cal
W}(G)\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}]^{2}+2\sum_{u\in
V(G)}\frac{{\cal W}(G){\cal D}_{\sf M}}{\varepsilon{\cal C}_{\sigma,{\sf
M}}}\tau(u)\mathbb{E}[C_{u}]^{2}\\\ &\leq 4{\cal W}(G)({\sf
T}_{\mathrm{avg}}^{\prime})^{2}+2\frac{{\cal W}(G){\cal D}_{\sf M}}{{\cal
C}_{\sigma,{\sf M}}}\frac{1}{\varepsilon}({\sf
C}_{\mathrm{avg}}^{\prime})^{2}=:{\cal W}^{\prime}.\end{split}$ (30)

Then a simple calculation of $\sqrt{{\cal R}^{\prime}{\cal W}^{\prime}}$ show
that the second part of Claim I follows from Theorem 4.1.

Proof of Claim II: Next, we consider the special case where there is a unique
marked element if $M\neq\emptyset$. In that case, when $M=\\{m\\}$ is non-
empty, we have, for any $\sigma$-$M$ flow, $\theta(m)=-1$ (all flow leaves at
$m$), so:

$\sum_{u\in
M}\frac{\theta(u)^{2}}{\tau_{M}(u)}=\frac{1}{\tau_{M}(m)}=\frac{\tau(M)}{\tau(m)}=1.$

Thus Claim II follows from applying Claim I with ${\cal D}_{{\sf M}}=1$.

Proof of Claim III: Finally, let $\tau$ be the known distribution described in
Claim III. If such a $\tau$ is known, we can define

${\sf w}_{u,{\sf M}}:=\frac{\tau(u){\cal W}(G)}{\varepsilon{\cal
C}_{\sigma,\tau}}=\frac{\tau_{M}(u)\tau(M){\cal W}(G)}{\varepsilon{\cal
C}_{\sigma,\tau}}\mbox{ when }u\in M.$

With this choice of ${\sf w}_{u,{\sf M}}$, preparing a state proportional to
$\sqrt{{\sf w}_{u}}{\lvert}1\rangle+\sqrt{{\sf w}_{u,{\sf
M}}}{\lvert}0\rangle$ can be done using a single qubit rotation that depends
on $\frac{{\cal W}(G)}{\varepsilon{\cal C}_{\sigma,\tau}}\frac{\tau(u)}{{\sf
w}_{u}}$.

P3: Let $\theta$ be the flow from $\sigma$ to $\tau_{M}$ with minimal energy
${\cal R}_{\sigma,\tau_{M}}(G)$ (see Definition 2.4), and extend it to a flow
on $G^{\prime}$ from $\sigma$ to $M^{\prime}$ by setting
$\theta(u,(u,g_{u}))=\tau_{M}(u)$ for all $u\in M$. Then, similar to (26), we
have:

$\displaystyle\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{t+1}\right]$
$\displaystyle\leq
2\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\ln{\sf T}+2\sum_{u\in M}\frac{\tau_{M}(u)^{2}}{{\sf w}_{u,{\sf
M}}}\ln{\sf C}$ $\displaystyle=2{\cal R}_{\sigma,\tau_{M}}(G)\ln{\sf
T}+2\frac{\varepsilon}{\tau(M)}\frac{{\cal C}_{\sigma,\tau}}{{\cal
W}(G)}\sum_{u\in M}\frac{\tau_{M}(u)^{2}}{\tau_{M}(u)}\ln{\sf C}$
$\displaystyle\leq 2\frac{{\cal C}_{\sigma,\tau}}{{\cal W}(G)}\ln{\sf
T}+2\frac{{\cal C}_{\sigma,\tau}}{{\cal W}(G)}\ln{\sf C}=:{\cal R}.$

N1: If $M=\emptyset$, we have, similar to (27):

$\displaystyle\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}{\sf
w}_{u,v}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}{t+1}\right]$ $\displaystyle\leq
2\sum_{(u,v)\in\overrightarrow{E}(G)}{\sf
w}_{u,v}\mathbb{E}[T_{u,v}^{2}]+2\sum_{u\in V(G)}{\sf w}_{u,{\sf
M}}\mathbb{E}[C_{u}^{2}]$ $\displaystyle\leq 4{\cal W}(G){\sf
T}_{\mathrm{avg}}^{2}+\frac{{\cal W}(G)}{{\cal
C}_{\sigma,\tau}}\frac{1}{\varepsilon}{\sf C}_{\mathrm{avg}}^{2}=:{\cal W}.$

To complete the proof of the first half of Claim III, we apply Theorem 4.1
using the fact that

$\displaystyle\sqrt{\cal RW}$ $\displaystyle=O\left(\left({\cal
C}_{\sigma,\tau}{\sf T}_{\mathrm{avg}}^{2}+\frac{1}{\varepsilon}{\sf
C}_{\mathrm{avg}}^{2}\right)\log{\sf TC}\right).$

The proof of the second half of Claim III proceeds just as in Claim I. ∎

The expressions we achieve in Corollary 4.2 in the case when checking is non-
trivial and $M$ is not restricted to being a singleton are somewhat
complicated. However, in the special case when $\sigma=\pi$, we can get a
bound comparable to the MNRS framework. The following corollary also gives an
alternative proof to the one in [AGJ20] that the MNRS framework is a special
case of the electric network framework (up to $\log{1}/{\pi_{\min}}$ factors,
which we suspect can be removed).

######  Corollary 4.3 (Variable-time MNRS).

Fix a network $G$ and marked set $M\subset V(G)$ that may implicitly depend on
an input $x$. Let $P$ be the transition matrix for the random walk on $G$, and
$\pi$ its stationary distribution. Let ${\sf S}$ be the cost of generating
${\lvert}\pi\rangle$, and suppose
$\\{{\lvert}\psi_{\star}^{G}(u)\rangle\\}_{u\in V(G)}$ can be generated in
unit cost. Let $\delta$ be a lower bound on the spectral gap of $P$, and
$\varepsilon$ a lower bound on $\pi(M)$ whenever $M\neq\emptyset$. Let
$\pi_{\min}=\min_{u\in V(G)}\pi(u)$.

Suppose there is a variable-time subroutine that checks, for any $u\in V(G)$,
if $u\in M$, with stopping times $\\{C_{u}\\}_{u\in V(G)}$, which are random
variables on $[{\sf C}]$, and all errors zero. Let ${\sf C}_{\mathrm{avg}}$
and ${\sf C}_{\mathrm{avg}}^{\prime}$ be upper bounds such that whenever
$M=\emptyset$,

$\sqrt{\sum_{u\in V(G)}\pi(u)\mathbb{E}[C_{u}^{2}]}\leq{\sf
C}_{\mathrm{avg}},\quad\mbox{and}\quad\sqrt{\sum_{u\in
V(G)}\pi(u)\mathbb{E}[C_{u}]^{2}}\leq{\sf C}_{\mathrm{avg}}^{\prime}.$

Suppose there is a reversible variable-time subroutine that implements the
transition map with stopping times
$\\{T_{u,v}\\}_{(u,v)\in\overrightarrow{E}(G)}$, which are random variables on
$[{\sf T}]$, and all errors zero. Let ${\sf T}_{\mathrm{avg}}$ and ${\sf
T}_{\mathrm{avg}}^{\prime}$ be upper bounds such that whenever $M=\emptyset$,

$\sqrt{\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]}\leq{\sf
T}_{\mathrm{avg}},\quad\mbox{and}\quad\sqrt{\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}]^{2}}\leq{\sf
T}_{\mathrm{avg}}^{\prime}.$

Then there is a quantum algorithm that detects if $M=\emptyset$ with bounded
error in complexity:

$O\left({\sf S}+\frac{1}{\sqrt{\varepsilon}}\left(\frac{1}{\sqrt{\delta}}{\sf
T}_{\mathrm{avg}}+{\sf
C}_{\mathrm{avg}}\right)\sqrt{\log\frac{1}{\pi_{\min}}}\log^{1.5}({\sf T}{\sf
C})\right).$

Suppose in addition that the values $\mathbb{E}[T_{u,v}]=\mathbb{E}[T_{u,i}]$
are computable in the strong sense that for any $u$, we can generate a
superposition proportional to $\sum_{i\in L(u)}\sqrt{{\sf
w}_{u,i}\mathbb{E}[T_{u,i}]}{\lvert}i\rangle$, and we have query access to
${\sf w}_{u}^{\prime}=\sum_{i\in L(u)}{\sf w}_{u,i}\mathbb{E}[T_{u,i}]$ and
$\mathbb{E}[C_{u}]$. Then there is a quantum algorithm that decides if
$M=\emptyset$ with bounded error in complexity:

$O\left({\sf S}+\frac{1}{\sqrt{\varepsilon}}\left(\frac{1}{\sqrt{\delta}}{\sf
T}_{\mathrm{avg}}^{\prime}+{\sf
C}_{\mathrm{avg}}^{\prime}\right)\sqrt{\log\frac{1}{\pi_{\min}}}\log({\sf
T}{\sf C})\right).$

###### Proof.

As in the proof of Corollary 4.2, we will apply Theorem 4.1 to a modified
graph $G^{\prime}$ in which we connect each $u\in V(G)$ to a new vertex
$(u,g_{u})$, where $g_{u}=1$ if and only if $u\in M$, by an edge of weight
${\sf w}_{u,{\sf M}}=\delta{\sf w}_{u}$.

We will use the following process – which is similar to a random walk on
$G^{\prime}$ starting from $\pi$ except for the log factor in $p$ – to design
a flow on $G^{\prime}$.

  1. 1.

Sample a vertex $u$ from $\pi$.

  2. 2.

Repeat:

    1. (a)

With probability $p=\frac{\delta}{\log({2}/{\pi_{\min}^{2}})}$, check if $u\in
M$, and if so, halt.

    2. (b)

Take a step to some $v$ according to $P$ (the random walk on $G$) by setting
$u\leftarrow v$.

This process gives rise to a Markov chain $X_{1},\dots,X_{\tau}$ on $V(G)$ for
a random variable $\tau$ with

$\mathbb{E}[\tau]=O\left(\frac{1}{p\pi(M)}\right)=O\left(\frac{\log\frac{1}{\pi_{\min}}}{\varepsilon\delta}\right).$

From this process, we can define a flow on $G$ as follows. Let $[u\rightarrow
v]$ be the number of times the above process moves from $u$ to $v$ and define
for any $\\{u,v\\}\in E(G)$:

$\theta(u,v):=\mathbb{E}[u\rightarrow v]-\mathbb{E}[v\rightarrow u].$

This satisfies $\theta(u,v)=-\theta(v,u)$, and letting $N_{u}^{\rightarrow}$
be the number of times we leave $u$, and $N_{u}^{\leftarrow}$ be the number of
times we enter $u$, we have:

$\theta(u)=\sum_{v}\theta(u,v)=\left(\mathbb{E}[N_{u}^{\rightarrow}]-\mathbb{E}[N_{u}^{\leftarrow}]\right)=\Pr[X_{1}=u]-\Pr[X_{\tau}=u].$

It is clear that $\Pr[X_{1}=u]=\pi(u)$. We also only ever output if $u\in M$,
so $\Pr[X_{\tau}=u]=0$ unless $u\in M$. We can extend this to a flow on
$G^{\prime}$ by setting $\theta(u,(u,1))=\theta(u)$ for all $u\in M$. Let
$\tilde{\pi}$ be the distribution on $M$ defined
$\tilde{\pi}(u)=\pi(u)-\theta(u)$ for all $u\in M$ – in other words,
$\tilde{\pi}(u)$ is the probability that $X_{\tau}=u$. Since there are
$1/p=\frac{1}{\delta}\log\frac{1}{\pi_{\min}^{2}}$ steps between checks, in
expectation, each time we check if $u\in M$, we are distributed according to
some distribution $\pi^{\prime}$ that is expected $\pi_{\min}/2$-close to
$\pi$ [LWP09, Theorem 12.3], meaning that for each $u\in M$

$\mathbb{E}[\pi_{M}^{\prime}(u)]\leq\frac{\pi(u)+\pi_{\min}/2}{\pi(M)-\pi_{\min}/2}\leq\frac{\frac{3}{2}\pi(u)}{\frac{1}{2}\pi(M)}=3\pi_{M}(u)$

and so $\tilde{\pi}(u)\leq 3\pi_{M}(u)$, and thus:

$|\theta(u)|\leq\tilde{\pi}(u)+\pi(u)\leq 3\pi_{M}(u)+\pi(M)\pi_{M}(u)\leq
4\pi_{M}(u).$

Then we have (using $\alpha_{t}=t+1$):

$\displaystyle 2{\cal
W}(G)\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{t+1}\right]$
$\displaystyle\leq\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{\pi(u)P_{u,v}}\mathbb{E}[\log
T_{u,v}]+\sum_{u\in M}\frac{\theta(u)^{2}}{\delta\pi(u)}\mathbb{E}[\log
C_{u}]$
$\displaystyle\leq\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{\pi(u)P_{u,v}}\log{\sf
T}+\frac{16}{\delta\pi(M)^{2}}\sum_{u\in M}{\pi(u)}\log{\sf C}$
$\displaystyle\leq\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{\pi(u)P_{u,v}}\log{\sf
T}+\frac{16}{\delta\varepsilon}\log{\sf C}.$

Above, we used ${\sf w}_{u,v}=\pi(u)P_{u,v}/(2{\cal W}(G))$,
$\theta(u)^{2}\leq 16\pi_{M}(u)^{2}=16\pi(u)^{2}/\pi(M)^{2}$, and
$\varepsilon\leq\pi(M)=\sum_{u\in M}\pi(u)$. We will show that,

$\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{\pi(u)P_{u,v}}\leq\mathbb{E}[\tau]\leq\frac{c\log\frac{1}{\pi_{\min}}}{\varepsilon\delta}$
(31)

for some constant $c$, from which it follows that

$\displaystyle\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}\frac{\theta(u,v)^{2}}{{\sf
w}_{u,v}}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}\frac{1}{t+1}\right]$
$\displaystyle\leq\frac{1}{2{\cal
W}(G)}\frac{1}{\varepsilon\delta}\left(c\log\frac{1}{\pi_{\min}}\log{\sf
T}+16\log{\sf C}\right)=:{\cal R}.$

Then since:

$\displaystyle\sum_{(u,v)\in\overrightarrow{E}(G^{\prime})}{\sf
w}_{u,v}\mathbb{E}\left[\sum_{t=0}^{T_{u,v}}(t+1)\right]$ $\displaystyle\leq
2{\cal
W}(G)\left(\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]+\sum_{u\in
V(G)}\delta\pi(u)\mathbb{E}[C_{u}^{2}]\right)=:{\cal W}$

we have

${\cal
RW}=O\left(\left(\frac{1}{\varepsilon\delta}\sum_{(u,v)\in\overrightarrow{E}(G)}\pi(u)P_{u,v}\mathbb{E}[T_{u,v}^{2}]+\frac{1}{\varepsilon}\sum_{u\in
V(G)}\pi(u)\mathbb{E}[C_{u}^{2}]\right)\log\frac{1}{\pi_{\min}}\log{\sf
TC}\right)$

and so the claim follows from Theorem 4.1. Thus, it remains only to establish
(31), which we now undertake.

Let $[u\rightarrow v]_{t}$ be the event that we move from $u$ to $v$ in the
$t$-th step, and let $E_{t}(u)$ be the event that $X_{t}=u$, and $\tau>t$
(i.e. we don’t stop there). Then:

$\displaystyle\mathbb{E}[u\rightarrow v]$
$\displaystyle=\sum_{t=1}^{\infty}\Pr[[u\rightarrow
v]_{t}]=\sum_{t=1}^{\infty}\Pr[E_{t}(u)]P_{u,v}.$

Then since $\theta(u,v)=\mathbb{E}[u\rightarrow v]-\mathbb{E}[v\rightarrow
u]$, by definition, we have:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{\pi(u)P_{u,v}}&=\frac{1}{2}\sum_{u\in
V(G)}\sum_{v\in\Gamma(u)}\pi(u)P_{u,v}\left(\frac{\mathbb{E}[u\rightarrow
v]}{\pi(u)P_{u,v}}-\frac{\mathbb{E}[v\rightarrow
u]}{\pi(v)P_{v,u}}\right)^{2}\\\ &=\frac{1}{2}\sum_{u\in
V(G)}\sum_{v\in\Gamma(u)}\pi(u)P_{u,v}\left(\frac{1}{\pi(u)}\sum_{t=1}^{\infty}\Pr[E_{t}(u)]-\frac{1}{\pi(v)}\sum_{t=1}^{\infty}\Pr[E_{t}(v)]\right)^{2}\\\
&=\frac{1}{2}\sum_{u\in
V(G)}\sum_{v\in\Gamma(u)}\pi(u)P_{u,v}\left(\frac{\mathbb{E}[N_{u}^{\rightarrow}]}{\pi(u)}-\frac{\mathbb{E}[N_{v}^{\rightarrow}]}{\pi(v)}\right)^{2}.\end{split}$
(32)

From (32) and the detailed balance condition $\pi(u)P_{u,v}=\pi(v)P_{v,u}$, it
follows that:

$\begin{split}\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{\pi(u)P_{u,v}}&=\frac{1}{2}\sum_{u\in
V(G)}\sum_{v\in\Gamma(u)}\pi(u)P_{u,v}\left(\frac{\mathbb{E}[N_{u}^{\rightarrow}]^{2}}{\pi(u)^{2}}+\frac{\mathbb{E}[N_{v}^{\rightarrow}]^{2}}{\pi(v)^{2}}-2\frac{\mathbb{E}[N_{u}^{\rightarrow}]}{\pi(u)}\frac{\mathbb{E}[N_{v}^{\rightarrow}]}{\pi(v)}\right)\\\
&=\sum_{u\in
V(G)}\sum_{v\in\Gamma(u)}\pi(u)P_{u,v}\frac{\mathbb{E}[N_{u}^{\rightarrow}]^{2}}{\pi(u)^{2}}-\sum_{u\in
V(G)}\sum_{v\in\Gamma(u)}\pi(u)P_{u,v}\frac{\mathbb{E}[N_{u}^{\rightarrow}]}{\pi(u)}\frac{\mathbb{E}[N_{v}^{\rightarrow}]}{\pi(v)}\\\
&=\sum_{u\in
V(G)}\sum_{v\in\Gamma(u)}P_{u,v}{\mathbb{E}[N_{u}^{\rightarrow}]}\left(\frac{\mathbb{E}[N_{u}^{\rightarrow}]}{\pi(u)}-\frac{\mathbb{E}[N_{v}^{\rightarrow}]}{\pi(v)}\right).\end{split}$
(33)

The number of visits to $u$ depends on if it is visited at step 1, which
happens with probability $\pi(u)$, as well as the number of visits to its
neighbours. Every time we leave a neighbour $v$ of $u$, we visit $u$ next with
probability $P_{v,u}$. Thus, the expected number of visits to $u$ is:

$\displaystyle\pi(u)+\sum_{v\in\Gamma(u)}P_{v,u}\mathbb{E}[N_{v}^{\rightarrow}].$

Then since we leave $u$ if we visit and don’t halt, the expected number of
times we leave $u\in\overline{M}$ is

$\mathbb{E}[N_{u}^{\rightarrow}]=\pi(u)+\sum_{v\in\Gamma(u)}P_{v,u}\mathbb{E}[N_{v}^{\rightarrow}],$
(34)

since we never halt on $u\in\overline{M}$; and for $u\in M$, since every
visits ends in halting with probability $\delta$,

$\displaystyle\mathbb{E}[N_{u}^{\rightarrow}]$
$\displaystyle=(1-\delta)\pi(u)+(1-\delta)\sum_{v\in\Gamma(u)}P_{v,u}\mathbb{E}[N_{v}^{\rightarrow}]$
$\displaystyle\mbox{so
}\mathbb{E}[N_{u}^{\rightarrow}]-\sum_{v\in\Gamma(u)}P_{v,u}\mathbb{E}[N_{v}^{\rightarrow}]$
$\displaystyle=\pi(u)-\frac{\delta}{1-\delta}\mathbb{E}[N_{u}^{\rightarrow}].$
(35)

Thus:

$\displaystyle\sum_{v\in\Gamma(u)}P_{u,v}\left(\frac{\mathbb{E}[N_{u}^{\rightarrow}]}{\pi(u)}-\frac{\mathbb{E}[N_{v}^{\rightarrow}]}{\pi(v)}\right)$
$\displaystyle=\frac{\mathbb{E}[N_{u}^{\rightarrow}]}{\pi(u)}-\sum_{v\in\Gamma(u)}P_{u,v}\frac{\mathbb{E}[N_{v}^{\rightarrow}]}{\pi(v)}$
$\displaystyle=\frac{1}{\pi(u)}\left(\mathbb{E}[N_{u}^{\rightarrow}]-\sum_{v\in\Gamma(u)}P_{v,u}\mathbb{E}[N_{v}^{\rightarrow}]\right)$
$\displaystyle\mbox{since }\frac{P_{u,v}}{\pi(v)}=\frac{P_{v,u}}{\pi(u)}$
$\displaystyle=\left\\{\begin{array}[]{ll}1&\mbox{if }u\in\overline{M},\mbox{
by \hyperref@@ii[eq:N-leave-notM]{(\ref*{eq:N-leave-notM})}}\\\
1-\frac{\delta}{1-\delta}\frac{\mathbb{E}[N_{u}^{\rightarrow}]}{\pi(u)}&\mbox{if
}u\in M,\mbox{ by
\hyperref@@ii[eq:N-leave-M]{(\ref*{eq:N-leave-M})}}.\end{array}\right.$

Thus, continuing from (33), we have

$\displaystyle\sum_{(u,v)\in\overrightarrow{E}(G)}\frac{\theta(u,v)^{2}}{\pi(u)P_{u,v}}$
$\displaystyle=\sum_{u\in\overline{M}}\mathbb{E}[N_{u}^{\rightarrow}]+\sum_{u\in
M}\mathbb{E}[N_{u}^{\rightarrow}]\left(1-\frac{\delta}{1-\delta}\frac{\mathbb{E}[N_{u}^{\rightarrow}]}{\pi(u)}\right)$
$\displaystyle\leq\sum_{u\in
V(G)}\mathbb{E}[N_{u}^{\rightarrow}]=\mathbb{E}[\tau],$

establishing (31). ∎

We now turn to the special case of search, where we have the following
corollary, again assuming, for simplicity, that there are no errors:

######  Corollary 4.4 (Variable-time Search ($\alpha_{t}=t+1$)).

Fix a search space $[n]$ and a distribution $\pi$ on $[n]$ such that we can
generate ${\lvert}\pi\rangle$ in unit cost. Suppose we have a variable-time
subroutine that computes, for any $i\in[n]$, a bit $g(i)$, in time $T_{i}$,
which is a random variable on $[{\sf T}]$. Assume all errors are 0. Suppose
$\varepsilon>0$ is a lower bound on $\sum_{i:g(i)=1}\pi(i)$ whenever
$\bigvee_{i\in[n]}g(i)=1$, and ${\sf T}_{\mathrm{avg}}$ and ${\sf
T}_{\mathrm{avg}}^{\prime}$ are upper bounds such that whenever
$\bigvee_{i\in[n]}g(i)=0$:

$\sqrt{\sum_{i\in[n]}\pi(i)\mathbb{E}[T_{i}^{2}]}\leq{\sf
T}_{\mathrm{avg}}\;\mbox{ and
}\;\sqrt{\sum_{i\in[n]}\pi(i)\mathbb{E}[T_{i}]^{2}}\leq{\sf
T}_{\mathrm{avg}}^{\prime}.$

Then there is a quantum algorithm that decides $\bigvee_{i\in[n]}g(i)$ with
bounded error in complexity:

$O\left(\frac{1}{\sqrt{\varepsilon}}{\sf T}_{\mathrm{avg}}\log^{1.5}{\sf
T}\right).$

If, in addition, we assume the values $\mathbb{E}[T_{i}]$ are known, in the
strong sense that we can generate a superposition proportional to
$\sum_{i\in[n]}\sqrt{\pi(i)\mathbb{E}[T_{i}]}{\lvert}i\rangle$ in unit cost,
there is a quantum algorithm that decides $\bigvee_{i\in[n]}g(i)$ with bounded
error in complexity:

$O\left(\frac{1}{\sqrt{\varepsilon}}{\sf T}_{\mathrm{avg}}^{\prime}\log{\sf
T}\right).$

###### Proof.

First note that, letting $A{\lvert}i\rangle=(-1)^{g(i)}$, a variable-time
algorithm for $g$ is trivially a reversible variable-time algorithm (just use
$\tilde{U}_{t}=U_{t}$). We will define a graph $G$ as follows. Let
$V(G)=\\{u_{0},\dots,u_{n}\\}$, where $u_{0}=(0,0)$ and for all $i\in[n]$,
$u_{i}=(i,g(i))$. Let $V_{0}=\\{u_{0}\\}$, so $\sigma$ is just a point
function, and $M=\\{u_{i}:g(i)=1\\}$. The graph will be a star with $u_{0}$
the centre, connected to each $u_{i}$ by an edge of weight $\pi(i)$. Define
label sets $L(u_{0})=L^{+}(u_{0})=[n]$, and for all $i\in[n]$,