tcb@breakable

# Multidimensional Electrical Networks and their Application to Exponential
Speedups for Graph Problems

Jianqiang Li Sebastian Zur Department of Computer Science and Engineering,
Pennsylvania State University, PA, USA<EMAIL_ADDRESS>& QuSoft, the
Netherlands<EMAIL_ADDRESS>
###### Abstract

Recently, Apers and Piddock [TQC ’23] strengthened the natural connection
between quantum walks and electrical networks by considering Kirchhoff’s Law
and Ohm’s Law. In this work, we develop the multidimensional electrical
network by defining Kirchhoff’s Alternative Law and Ohm’s Alternative Law
based on the novel multidimensional quantum walk framework by Jeffery and Zur
[STOC ’23]. This multidimensional electrical network allows us to sample from
the electrical flow obtained via a multidimensional quantum walk algorithm and
achieve exponential quantum-classical separations for certain graph problems.

We first use this framework to find a marked vertex in one-dimensional random
hierarchical graphs as defined by Balasubramanian, Li, and Harrow [arXiv ’23].
In this work, they generalised the well known exponential quantum-classical
separation of the welded tree problem by Childs, Cleve, Deotto, Farhi,
Gutmann, and Spielman [STOC ’03] to random hierarchical graphs. Our result
partially recovers their results with an arguably simpler analysis.
Furthermore, by constructing a $3$-regular graph based on welded trees, this
framework also allows us to show an exponential speedup for the pathfinding
problem. This solves one of the open problems by Li [arXiv ’23], where they
construct a non-regular graph and use the degree information to achieve a
similar speedup.

In analogy to the connection between the (edge-vertex) incidence matrix of a
graph and Kirchhoff’s Law and Ohm’s Law in an electrical network, we also
rebuild the connection between the alternative incidence matrix and
Kirchhoff’s Alternative Law and Ohm’s Alternative Law. By establishing this
connection, we expect that the multidimensional electrical network could have
more applications beyond quantum walks.

##  1 Introduction

The duality between electrical networks and graph theory is of great
significance in multiple aspects of theoretical computer science. On the one
hand, graph theory plays an important role in analysing large electrical
networks (circuits) using high-speed computers [Deo17]. On the other hand, the
concepts of effective resistance and electrical flow used in electrical
networks play an important role in the design of new graph algorithms, such as
graph sparsification via effective resistances, computing max flow via
electrical flow, and many more [Vis13]. Furthermore, the connection between
random walks (or more general Markov chains) on undirected graphs and
electrical networks plays an important role in analysing the behavior of
random walks, such as their hitting time and cover time [DS84, Lov96].

Quantum computation has been shown to provide various speedups for many graph
problems, ranging from polynomial speedups for detecting (or finding) a marked
vertex [HK17, Bel13, AGJK20, AGJ20], computing the effective resistance in an
electrical network [Wan17], connectivity problems [JJKP18, IJ19], pathfinding
problems [DHHM06, JKP23] and graph property testing [ACL11, AS19], to even
superpolynomial speedups when traversing certain graphs [CCD+03, BDCG+20,
BLH23, JZ23, Li23]. Most of these quantum algorithms are based on different
types of quantum walks on graphs, including discrete quantum walks, continuous
quantum walks, and the more recent multidimensional quantum walks.

The connection between (discrete) quantum walks and electrical networks was
first established by [Bel13], where this implicit connection was used to
derive and analyse a phase estimation algorithm with the goal of detecting the
existence of a marked vertex in a graph. Later, [Wan17] provided several
quantum algorithms, based on quantum walks and the HHL algorithm, and
exhibited a quantum speedup in the analysis of large electrical networks, such
as computing their electrical flow and effective resistance. More recently,
[Pid19, AP22] have shown that for the quantum walk operator based on the
electrical network framework, if the phase value returned by the phase
estimation algorithm from [Bel13] is “$0$”, indicating that there is a marked
vertex, then the resulting state is actually a quantum state representing the
electrical flow between the starting vertex and the marked vertex. By sampling
from this flow state, one can infer additional information, such as the random
walk arrival distribution and the possibility of finding marked vertices
instead of only detecting their existence, but this approach provides only at
most a quadratic speedup compared to what classical random walks can achieve.

In addition to algebraic problems [Sho97, Sim97], one of the most well known
examples that exhibits an exponential separation between quantum and classical
algorithms is the welded tree problem [CCD+03]. A welded tree graph consists
of two full binary trees of depth $h$ and the leaves of both trees are
connected via two disjoint perfect matchings. Given an adjacency list oracle
$O_{G}$ to the welded tree graphs $G$ and the name of one of the roots $s$,
the goal of the welded tree problem is to output the name of the other root
$t$. More recently, [BLH23] generalised this exponential separation to one-
dimensional random hierarchical graphs where the goal is once more to find
some special vertex $t$ given an initial vertex $s$. Instead of finding a
marked vertex, [Li23] showed that there is an exponential separation when it
comes to finding a path for certain types of graphs constructed from welded
tree graphs. However, all these quantum algorithms are based on the continuous
quantum walk subroutine, in which they do not generate a specific quantum
state implicitly.

Other than the continuous quantum walk approach, the multidimensional quantum
walk framework [JZ23] solves the welded tree problem by applying phase
estimation of a more general quantum walk operator and checks whether the
returned phase value is “$0$”, indicating that the root $t$ is “marked”, which
allows them to infer the name of $t$. This provides a new way to achieve an
exponential separation between quantum and classical algorithms. Many big open
problems in the field of quantum computing can be reduced to the task of
generating a specific type of quantum state, such as the graph isomorphism
problem [AT07], lattice-related problems [EH22], and the problem of computing
the ground state of local Hamiltonians [GHL+15]. However, limited progress has
been made on how to generate those quantum states and exhibit exponential
speedup on these types of problems. Alternatively, an equally important
direction is to design new quantum algorithms to generate certain types of
quantum states and use those states to exhibit, hopefully superpolynomial,
speedups for some other problems. An open problem is whether we can build a
connection between multidimensional quantum walks and electrical networks to
obtain some notion of a quantum “electrical flow” state, such that by
generating and sampling from such a state we can solve certain problems
exponentially faster compared to classical algorithms. Hopefully this new flow
state generation technique may also shed some light on those big open problems
related to quantum state generation.

##### Multidimensional electrical networks:

In this work, we take the first steps in building this connection by
constructing the multidimensional electrical network framework through
generalising Kirchhoff’s Law as Kirchhoff’s Alternative Law and Ohm’s Law as
Ohm’s Alternative Law based on the multidimensional quantum walk framework
from [JZ23]. Roughly speaking, for each vertex other than the source and sink,
Kirchhoff’s Law forces the electrical flow to be orthogonal to a vector,
whereas Kirchhoff’s Alternative Law forces the electrical flow to be
orthogonal to a potentially larger subspace that encompasses the previous
vector. Moreover, instead of associating each vertex with a single potential
value for each vertex as in Ohm’s Law, we associate (possibly distinct)
potential values ${\sf p}_{(u,v)}$, ${\sf p}_{(v,u)}$ to each edge $(u,v)$ in
Ohm’s Alternative Law, which states that ${\sf p}_{u,v}-{\sf
p}_{v,u}=\theta_{u,v}/{\sf w}_{u,v}$, whereas Ohm’s Law states ${\sf
p}_{u}-{\sf p}_{v}=\theta_{u,v}/{\sf w}_{u,v}$.

The definitions of these two alternative laws are derived from the quantum
walk based on an electrical network [Bel13, Pid19, AP22] and the alternative
neighbourhood technique introduced by the multidimensional quantum walk
[JZ23]. We can model any graph $G=(V,E,{\sf w})$ as an electrical network with
each edge assigned a positive weight ${\sf w}_{u,v}$, i.e. the conductance.
This weight assignment gives rise to a weighted superposition of neighbours of
any vertex $u$, known as the star state of $u$:

$\ket{\psi_{u}}=\frac{1}{\sqrt{{\sf w}_{u}}}\sum_{v}\sqrt{{\sf
w}_{u,v}}\ket{u,v},$

where ${\sf w}_{u}$ is a normalization factor. This can be thought of as a
quantum encoding of the probability to move from a vertex $u$ to each
neighbour $v$. The $s$-$t$ electrical flow $\theta$, which is the “smallest”
$s$-$t$ flow by some metric, gives rise to an electrical flow state
$\ket{\theta}$. Kirchhoff’s Law states that this $s$-$t$ electrical flow is
conserved at every vertex $u\in V\backslash\\{s,t\\}$, meaning that the amount
of flow $\theta$ coming into $u$ is equal to the amount of flow existing $u$.
This law can be equivalently read in terms of $\ket{\psi_{u}}$ and
$\ket{\theta}$, in which case it states that for every vertex $u\in
V\backslash\\{s,t\\}$ we require

$\mbox{$\langle\psi_{u}|\theta\rangle$}=0.$

The quantum walk operator $U_{\cal AB}=(2\Pi_{\cal A}-I)(2\Pi_{\cal B}-I)$ in
[Bel13] consists of a reflection around two spaces: the antisymmetric subspace
${\cal A}$ and the span of (almost all) star states:

${\cal B}:=\mathrm{span}\\{\ket{\psi_{u}}:u\in V\backslash\\{s,t\\}\\}.$

The $s$-$t$ electrical flow $\theta$ is special with regards to this quantum
walk operator $U_{\cal AB}$, as its flow state $\ket{\theta}$ lives in the
$+1$-eigenspace of $U$. Moreover, it can also be written as a linear
combination of projected star states $(I-\Pi_{\cal A})\ket{\psi_{u}}$ for
$u\in V$. The coefficients in this linear combination are precisely the
potentials ${\sf p}_{u}$ given by the potential vector ${\sf p}$ corresponding
to the $s$-$t$ electrical flow $\theta$ such that together they satisfy Ohm’s
Law: ${\sf p}_{u}-{\sf p}_{v}=\theta_{u,v}/{\sf w}_{u,v}$. By combining all
these properties, [Pid19, AP22] showed that with the use of phase estimation
on the quantum walk operator $U_{\cal AB}$, one can approximate
$\ket{\theta}$, allowing one to (approximately) sample from the $s$-$t$
electrical flow $\theta$.

The cost of calling $U_{\cal AB}$, and hence the cost of this phase estimation
procedure, relies on the cost of generating $\ket{\psi_{u}}$. In [JZ23], the
authors deal with the case where it might be computationally costly to
generate $\ket{\psi_{u}}$, but where the algorithm knows that $\ket{\psi_{u}}$
is one of a small set of easily preparable states
$\Psi_{\star}(u)=\\{\ket{\psi_{u,1}},\ket{\psi_{u,2}},\dots\\}$, known as the
alternative neighbourhoods for $u$. They then run phase estimation on the
modified quantum walk operator $U_{{\cal A}{\cal B}^{\sf alt}}$, which
reflects around the larger space that contains ${{\cal B}}$:

${{\cal B}^{\sf alt}}:=\mathrm{span}\\{\mathrm{span}(\Psi_{\star}(u)):u\in
V\backslash\\{s,t\\}\\}.$

To make sure that the same analysis as before still works on this new quantum
walk operator $U_{{\cal A}{\cal B}^{\sf alt}}$, we introduce the $s$-$t$
alternative electrical flow $\theta^{\sf alt}$. This is again the “smallest”
$s$-$t$ flow that satisfies Kirchhoff’s Alternative Law, which requires
$\ket{\theta^{\sf alt}}$ to be orthogonal to all of
$\mathrm{span}(\Psi_{\star}(u))$ instead of only to
$\ket{\psi_{u}}\in\Psi_{\star}(u)$, ensuring that $\ket{\theta^{\sf alt}}$
lives in the $+1$-eigenspace of $U_{{\cal A}{\cal B}^{\sf alt}}$. This
$\ket{\theta^{\sf alt}}$ can also be written as a linear combination of
projected star states $(I-\Pi_{\cal A})\ket{\psi_{u,i}}$ for $u\in V$ and
$\ket{\psi_{u,i}}\in\Psi_{\star}(u)$. This will again result in a collection
of linear coefficients, which gives rise to an alternative potential vector
${\sf p}^{\sf alt}$ acting not on vertices, but on edges. This ${\sf p}^{\sf
alt}$ is related to $\theta^{\sf alt}$ through Ohm’s Alternative Law, which
states that ${\sf p}_{u,v}-{\sf p}_{v,u}=\theta_{u,v}/{\sf w}_{u,v}$. By a
similar analysis as in regular electrical networks, we show that with phase
estimation on the quantum walk operator $U_{{\cal A}{\cal B}^{\sf alt}}$ we
can approximate $\ket{\theta^{\sf alt}}$, allowing one to (approximately)
sample from the $s$-$t$ alternative electrical flow $\theta^{\sf alt}$.

These laws and definitions may seem constructed in an ad-hoc fashion to fit
with the analysis in [Pid19, AP22], but we give proof that these are in fact
natural definitions. It is well known in electrical network theory [Vis13]
that both Kirchhoff’s Law as well as Ohm’s Law can be phrased as linear
equations involving the edge-vertex incidence matrix $B$, whose entries
contain the square root of the weights ${\sf w}_{u,v}$. These linear relations
are useful to show important physical properties of the $s$-$t$ electrical
flow $\theta$ and its potential vector ${\sf p}$, such as their existence and
the fact that ${\sf p}_{s}$ is equal to the energy of $\theta$, also known as
the effective resistance ${\cal R}_{s,t}$. By extending this $B$ in a natural
fashion to also incorporate the alternative neighbourhoods $\Psi_{\star}(u)$,
we obtain the alternative incidence matrix $B_{{\sf alt}}$. This matrix
$B_{{\sf alt}}$ can be substituted into the previously mentioned linear
equations to recover Kirchhoff’s Alternative Law as well as Ohm’s Alternative
Law. We then use these linear equations to show the existence of the $s$-$t$
alternative electrical flow $\theta^{\sf alt}$ and its alternative potential
vector ${\sf p}^{\sf alt}$, as well as the fact that the potential ${\sf
p}_{s,u}$ along each adjacent to $s$ is equal to the energy of $\theta^{\sf
alt}$, which we call the alternative effective resistance ${\cal R}^{{\sf
alt}}_{s,t}$.

##### Applications:

We first apply this multidimensional quantum electrical network framework to
one-dimensional random hierarchical graphs with nodes
$S_{0},S_{1},\cdots,S_{n}$ as defined in [BLH23]. Given the initial vertex
$s$, which is the unique element in $S_{0}$, the goal is to transverse the
exponentially large one-dimensional random hierarchical graph to find the
vertex $t$, the unique element in $S_{n}$. It has been shown that the
continuous quantum walk approach can provide an exponential speedup (in $n$)
in solving this problem compared to any classical algorithm with some
additional assumptions on the structures of the one-dimensional random
hierarchical graph. In this paper, imposing slightly different assumptions on
the structure, we show that the multidimensional quantum walk also solves this
problem in polynomial time by sampling from the quantum electrical flow state.
Interestingly, in this one-dimensional setting, the electrical flow with
respect to the multidimensional quantum walk operator on some weighted one-
dimensional random hierarchical graph matches the real electrical flow.
Compared to the technical analysis [BLH23] used for the continuous quantum
walk approach, our analysis is much simpler and more suited to a computer
science audience. We then apply this to the welded tree graph, which is an
example of a one-dimensional random hierarchy graph, to provide an alternative
quantum algorithm that solves the problem in polynomial time, recovering the
exponential separation from [CCD+03].

Additionally, we apply this multidimensional quantum electrical network
framework to the pathfinding problem. Here, given a graph $G=(V,E)$ and
$s,t\in V$, the algorithm is tasked with finding an $s$-$t$ path. Under the
adjacency list oracle model, [Li23] recently constructed a graph by
associating $n$ different welded tree graphs with an $s$-$t$ path of length
$n$, hereby exhibiting an exponential quantum-classical separation in the
context of pathfinding problems. This quantum algorithm uses the polynomial-
time continuous quantum walk algorithm from [CCD+03] as a subroutine to output
the $s$-$t$ path and the constructed algorithm relies heavily on the
constructed graph being non-regular. This degree information in some way
propagates the algorithm into the direction of $t$, which makes this technique
infeasible for less structured graphs, such as isogeny graphs [JDF11]. On the
other hand, as indicated in [HL], by generating the electrical flow using the
HHL algorithm [HHL09], there seems to be a possibility of exhibiting a
superpolynomial speedup as well in the context of pathfinding problems, but
currently their analysis provides a quadratic speedup compared with existing
approaches. However, we should emphasise that their failed attempt of using
the quantum electrical flow to show a superpolynomial speedup for the
pathfinding problem provided the starting point for this work. Under the
adjacency matrix model, [JKP23] suggest a new way to generate a quantum
electrical flow state based on span programs. This approach can be used to
sample an $s$-$t$ path, which improves the query complexity of the previous
quantum algorithm by [DHHM06] for some types of graphs, but the resulting
complexities scale at least linearly with the number of vertices, which poses
a problem when dealing with exponentially large graphs.

In this work, we construct a $3$-regular graph, except for the start and end
vertices $s$ and $t$, which contains welded tree graphs of depth $n$ as
subgraphs, meaning this graph has exponentially many vertices. We then tackle
the pathfinding for $G$ and $s,t$ using the adjacency list oracle model using
the multidimensional quantum electrical network framework. This allows us to
sample from the electrical flow between $s$ and $t$. We then exhibit an
explicit $s$-$t$ path, whose overlap with the electrical flow is at least
inverse polynomial. This allows us to obtain this $s$-$t$ path using only a
polynomial amount of queries to the adjacency list oracle. We also give a
classical lower bound on solving this specific pathfinding problem, which
states that any classical algorithm will have to make an exponential number of
queries to adjacency list oracle to output any $s$-$t$ path, under the
folklore assumption that $s$-$t$ pathfinding is classically hard on welded
tree graphs. In both of these applications, the way that ${\cal B}^{\sf alt}$
is extended is fairly natural, as it will be constructed from Fourier basis
states.

Although our work involves pathfinding and welded tree graphs, the
multidimensional quantum electrical network framework does not directly hint
at a solution to the $s$-$t$ pathfinding problem on welded tree graphs
[CCG22], which currently poses a large open-problem in the field of quantum
algorithms [Aar21]. This is due to the fact that any $s$-$t$ path on the
welded tree graph of polynomial length will have a negligible overlap with the
(alternative) $s$-$t$ electrical flow.

##### Organization:

The remainder of this article is organised as follows. In Section 2, we give
preliminaries on graph theory, electrical networks and quantum walks. In
Section 3 we show how the concepts related to electrical flow can be
generalised to the multidimensional electrical network under the
multidimensional quantum walk framework. This results in our new Kirchhoff’s
Alternative Law and Ohm’s Alternative Law. In Section 4, we apply the
multidimensional electrical network to one-dimensional random hierarchical
graphs and show how the framework allows us to sample exponentially faster
from the quantum electrical flow state than any classical algorithm can. In
Section 5, using the multidimensional electrical network, we construct a
pathfinding problem where we show that quantum walks can exhibit exponential
speedups when it comes to pathfinding problems. Finally in Section 6, we
rebuild the connection between the alternative incidence matrix and
Kirchhoff’s Alternative Law and Ohm’s Alternative Law, showing that our new
laws seem to be natural definitions and that they generalise known results
regarding electrical networks.

##  2 Preliminaries

###  2.1 Graph theory and electrical networks

In this section, we define graph-theoretic concepts and basic knowledge of
electrical networks following [Vis13, JZ23]. Although experienced readers will
be familiar with these notions, we encourage the reader not to skip these
definitions, as some of them are not completely standard compared to other
works on quantum walks.

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

A network is a connected weighted graph $G=(V,E,{\sf w})$ with a vertex set
$V$, an (undirected) edge set $E$ and some weight function ${\sf
w}:E\rightarrow\mathbb{R}_{>0}$. Since edges are undirected, we can
equivalently describe the edges by some set $\overrightarrow{E}$ such that for
all $(u,v)\in E$, exactly one of $(u,v)$ or $(v,u)$ is in
$\overrightarrow{E}$. The choice of edge directions is arbitrary. Then we can
view the weights as a function ${\sf
w}:\overrightarrow{E}\rightarrow\mathbb{R}_{>0}$, and for all
$(u,v)\in\overrightarrow{E}$, 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$. For an implicit network $G$, and $u\in V$, we will let
$\Gamma(u)$ denote the _neighbourhood_ of $u$:

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

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

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

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

A _flow_ on a network $G=(V,E,{\sf w})$ is a real-valued function
$\theta:\overrightarrow{E}\rightarrow\mathbb{R}$, extended to edges in both
directions by $\theta_{u,v}=-\theta_{v,u}$ for all
$(u,v)\in\overrightarrow{E}$. For any flow $\theta$ on $G$, vertex $u\in V$,
and subset $A\subseteq V$ 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_. A flow with a unique
source $s$ and unique sink $t$ (satisfying $\theta(s)=-\theta(t)=-1$) is
called an _(unit) $s$-$t$ flow_. The _energy_ of any flow $\theta$ is

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

The _effective resistance ${\cal R}_{s,t}$_ is given by the minimal energy
${\cal E}(\theta)$ over all unit flows $\theta$ from $s$ to $t$. The $s$-$t$
_electrical flow_ is the unique unit $s$-$t$ flow that achieves this minimal
energy.

######  Definition 2.3 (Potential).

A _potential vector_ (also known as potential function) on a network
$G=(V,E,{\sf w})$ is a real-valued function ${\sf p}:V\rightarrow\mathbb{R}$
that assigns a potential ${\sf p}_{u}$ to each vertex $u\in V$.

######  Definition 2.4 (Electrical Network).

Given a network $G=(V,E,{\sf w})$ with a weight function ${\sf w}$, we can
interpret every edge $(u,v)\in E$ as a resistor with resistance $1/{\sf
w}_{u,v}$. This allows $G$ to be modeled as an _electrical network_.

Two fundamental laws related to electrical networks are Kirchhoff’s Law (also
known as Kirchhoff’s Node Law) and Ohm’s Law. The former states the definition
of a $s$-$t$ flow, as in Definition 2.2:

######  Definition 2.5 (Kirchhoff’s Law).

For any $s$-$t$ flow on an electrical network $G=(V,E,{\sf w})$ with $s,t\in
V$, the amount of electrical flow that enters any $u\in V\backslash\\{s,t\\}$
is equal to the amount of flow that exits $u$, that is,
$\sum_{v\in\Gamma(u)}\theta_{u,v}=0$.

The latter states that if we inject a unit of current into $s$ and extract it
from $t$ in the electrical network $G$, then there is an induced potential
vector ${\sf p}$ which relates to the $s$-$t$ electrical flow $\theta$:

######  Definition 2.6 (Ohm’s Law).

Let $\theta$ be the $s$-$t$ electrical flow on an electrical network
$G=(V,E,{\sf w})$ with $s,t\in V$. Then there exists a potential vector ${\sf
p}$ such that the potential difference between the two endpoints of any edge
$(u,v)\in E$ is equal to the amount of electrical flow $\theta_{u,v}$ along
this edge multiplied with the resistance $1/{\sf w}_{u,v}$, that is, ${\sf
p}_{u}-{\sf p}_{v}=\theta_{u,v}/{\sf w}_{u,v}$.

The potential ${\sf p}$ induced by an $s$-$t$ electrical flow $\theta$ in
Ohm’s Law is not unique and it is therefore convention to consider the
potential ${\sf p}$ that assigns ${\sf p}_{t}=0$, in which case ${\sf
p}_{s}={\cal R}_{s,t}$.

###  2.2 Quantum walks and electrical flow

There is a direct relationship between the analysis of random walks and
electrical networks, see for example [LP16]. The relationship between quantum
walks and electrical networks was built for the first time by [Bel13], where
electrical network theory was used to construct and analyse a phase estimation
algorithm to detect whether a given graph contained a marked element.
Recently, [Pid19, AP22] have shown that the resulting state after running this
phase estimation is actually a quantum state representing the electrical flow
between a starting vertex and the marked vertices. For a network $G=(V,E,{\sf
w})$ and vertices $s,t\in V$, let

$\mathcal{H}=\mathrm{span}\\{\ket{u,v}|(u,v)\in E\\}$

be the associated vector space of its edges. For each vertex $u\in V$, we let
${\sf w}_{u}=\sum_{v\in\Gamma(u)}{\sf w}_{u,v}$ be the weighted degree of $u$.
We use it to define the (normalised) star state of $u$ as

$\ket{\psi_{u}}=\frac{1}{\sqrt{{\sf w}_{u}}}\sum_{v\in\Gamma^{+}(u)}\sqrt{{\sf
w}_{u,v}}\ket{u,v}-\sum_{v\in\Gamma^{-}(u)}\sqrt{{\sf
w}_{u,v}}\ket{u,v}=\frac{1}{\sqrt{{\sf
w}_{u}}}\sum_{v\in\Gamma(u)}(-1)^{\Delta_{u,v}}\sqrt{{\sf w}_{u,v}}\ket{u,v}.$

Here for any $(u,v)\in E$, the quantity $\Delta_{u,v}$ is equal to $0$ if
$(u,v)\in\overrightarrow{E}$ and $1$ if $(v,u)\in\overrightarrow{E}$. This
definition of a star state is slightly different from most of the literature,
where there is usually no sign-difference depending on whether $(u,v)$ is part
of the directed edge set, but this will be necessary later on when working
with the multidimensional quantum walk framework from [JZ23]. Now consider the
following two subspaces of ${\cal H}$. Let

${\cal A}:=\mathrm{span}\\{\ket{\psi}\in{\cal H}:\mbox{$\langle
u,v|\psi\rangle$}=-\mbox{$\langle
v,u|\psi\rangle$}~{}~{}\forall\ket{u,v}\in{\cal H}\\}$

be the antisymmetric subspace of ${\cal H}$. Moreover, let ${\cal
B}:=\mathrm{span}\\{\ket{\psi_{u}}:u\in V\backslash\\{s,t\\}\\}$ be the star
space of ${\cal H}$. Then the quantum walk operator $U_{{\cal AB}}$ is defined
as

$U_{{\cal AB}}:=(2\Pi_{{\cal A}}-I)(2\Pi_{{\cal B}}-I),$ (2)

where $\Pi_{\cal A}$ and $\Pi_{\cal B}$ are orthogonal projectors onto ${\cal
A}$ and ${\cal B}$ respectively. Note that

$\displaystyle 2\Pi_{{\cal A}}-I=-{\sf SWAP},$ $\displaystyle 2\Pi_{{\cal
B}}-I=2\sum_{u\in V\backslash\\{s,t\\}}\ket{\psi_{u}}\bra{\psi_{u}}-I,$

where ${\sf SWAP}$ acts as ${\sf SWAP}\ket{u,v}=\ket{v,u}$ for any
$\ket{u,v}\in{\cal H}$. For any star state $\ket{\psi_{u}}$, we write

$\ket{\psi_{u}^{+}}:=\sqrt{2}(I-\Pi_{\cal A})\ket{\psi_{u}}=\frac{I+{\sf
SWAP}}{\sqrt{2}}\ket{\psi_{u}}$

for its normalised projection onto ${\cal A}^{\perp}$, which is also known as
the symmetric subspace of ${\cal H}$. For any flow $\theta$, we define its
associated (normalised) flow state in ${\cal H}$ as

$\ket{\theta}:=\frac{1}{\sqrt{2{\cal
E}(\theta)}}\sum_{(u,v)\in\overrightarrow{E}}\frac{\theta_{u,v}}{\sqrt{{\sf
w}_{u,v}}}\left(\ket{u,v}+\ket{v,u}\right).$ (3)

In the case where $\theta$ is the $s$-$t$ electrical flow, we define the
(unnormalised) state associated with the induced potential vector ${\sf p}$
(with the convention that ${\sf p}_{t}=0$) as

$\ket{{\sf p}}=\sqrt{\frac{2}{{\cal R}_{s,t}}}\sum_{u\in
V\backslash\\{s\\}}{\sf p}_{u}\sqrt{{\sf w}_{u}}\ket{\psi_{u}}.$ (4)

In [Pid19, AP22], this potential state $\ket{{\sf p}}$ is used to exhibit that
by running phase estimation on the quantum walk operator $U_{\cal AB}$, we can
obtain a close approximation to the flow state $\ket{\theta}$. The precision
required in this phase estimation algorithm scales with a quantity in [AP22]
is defined as the escape time $\mathsf{ET}_{s}$:

$\mathsf{ET}_{s}:=\frac{1}{2}\left\|\ket{{\sf p}}\right\|^{2}=\frac{1}{{\cal
R}_{s,t}}\sum_{u\in V}{\sf p}_{u}^{2}{\sf w}_{u}.$

Since we will not be using the operational meaning of $\mathsf{ET}_{s}$ in
this work, we will omit $\mathsf{ET}_{s}$ in the rest of this work and instead
work with $\left\|\ket{{\sf p}}\right\|$.

######  Lemma 2.7 (Modified Lemma 8 in [Pid19] and Lemma 10 in [AP22]).

Define the unitary $U_{\cal AB}=(2\Pi_{\cal A}-1)(2\Pi_{\cal B}-1)$ acting on
a Hilbert space ${\cal H}$ for projectors $\Pi_{\cal A},\Pi_{\cal B}$ onto
some subspaces ${\cal A}$ and ${\cal B}$ of ${\cal H}$ respectively. Let
$\ket{\psi}=\sqrt{p}\ket{\varphi}+(I-\Pi_{\cal A})\ket{\phi}$ be a normalised
quantum state such that $U\ket{\varphi}=\ket{\varphi}$ and $\ket{\phi}$ is a
(unnormalised) vector satisfying $\Pi_{\cal B}\ket{\phi}=\ket{\phi}$. Then
performing phase estimation on the state $\ket{\psi}$ with operator $U$ and
precision $\delta$ outputs “$0$” with probability
$p^{\prime}\in[\frac{4}{\pi^{2}}p,p+\frac{17\pi^{2}\left\|\ket{\phi}\right\|}{16T}]$,
leaving a state $\ket{\psi^{\prime}}$ satisfying

$\frac{1}{2}\left\|\ket{\psi^{\prime}}\bra{\psi^{\prime}}-\ket{\varphi}\bra{\varphi}\right\|_{1}\leq\sqrt{\frac{17\pi^{4}\delta\left\|\ket{\phi}\right\|}{64p}}.$

Consequently, when the precision is
$O\left(\frac{p\epsilon^{2}}{\left\|\ket{\phi}\right\|}\right)$, the resulting
state $\ket{\psi^{\prime}}$ satisfies

$\frac{1}{2}\left\|\ket{\psi^{\prime}}\bra{\psi^{\prime}}-\ket{\varphi}\bra{\varphi}\right\|_{1}\leq\epsilon.$

###### Proof.

See Appendix A. ∎

This lemma is almost equivalent to Lemma 8 in [Pid19] and Lemma 10 in [AP22],
but we have modified it slightly as we were unable to verify the constants in
[Pid19, AP22] and the scaling with the precision in [AP22]. The theory of
electrical networks tells us if we consider the $s$-$t$ electrical flow
$\theta$, then we can apply Lemma 2.7 to approximate the $s$-$t$ electrical
flow state $\ket{\theta}$.

######  Corollary 2.8.

Let $U_{\cal AB}$ be the quantum walk operator as defined in (2). Then by
performing phase estimation on the initial state $\ket{\psi_{s}^{+}}$ with the
operator $U_{\cal AB}$ and precision $O\left(\frac{\epsilon^{2}}{{\cal
R}_{s,t}{\sf w}_{s}\left\|{\sf p}\right\|}\right)$, the phase estimation
algorithm outputs “$0$” with probability $\Theta\left(\frac{1}{{\cal
R}_{s,t}{\sf w}_{s}}\right)$, leaving a state $\ket{\theta^{\prime}}$
satisfying

$\frac{1}{2}\left\|\ket{\theta^{\prime}}\bra{\theta^{\prime}}-\ket{\theta}\bra{\theta}\right\|_{1}\leq\epsilon.$

Before we provide the proof of Corollary 2.8, which can also be found in
[Pid19, AP22], we remark that it is possible to modify the network $G$ to
ensure that ${\cal R}_{s,t}{\sf w}_{s}=\Theta(1)$, which is a standard tool
used in quantum electrical networks [Bel13].

###### Proof.

Firstly, by Kirchhoff’s Law (see Definition 2.5), we know the $s$-$t$
electrical flow $\theta$ is conserved at each vertex $u\in
V\setminus\\{s,t\\}$, which shows that $\Pi_{\cal B}\ket{\theta}=0$:

$\begin{split}\langle\psi_{u}|\theta\rangle&=\frac{1}{\sqrt{2{\cal
R}_{s,t}}}\sum_{v\in\Gamma(u)}(-1)^{\Delta_{u,v}}\sqrt{{\sf
w}_{u,v}}\bra{u,v}\sum_{(u,v)\in\overrightarrow{E}}\frac{\theta_{u,v}}{\sqrt{{\sf
w}_{u,v}}}(\ket{u,v}+\ket{v,u})\\\ &=\frac{1}{\sqrt{2{\cal
R}_{s,t}}}\left(\sum_{v\in\Gamma^{+}(u)}\theta_{u,v}+\sum_{v\in\Gamma^{-}(u)}-\theta_{v,u}\right)=\frac{1}{\sqrt{2{\cal
R}_{s,t}}}\sum_{v\in\Gamma(u)}\theta_{u,v}=0.\end{split}$ (5)

By Ohm’s Law (see Definition 2.6), we know that there exists a potential ${\sf
p}$, with ${\sf p}_{t}=0$, such that for each edge $(u,v)\in E$ we have ${\sf
p}_{u}-{\sf p}_{v}=\frac{\theta_{u,v}}{{\sf w}_{u,v}}$. This shows that
$\Pi_{\cal A}\ket{\theta}=0$, which combined with the fact that $\Pi_{\cal
B}\ket{\theta}=0$ shows that $\ket{\theta}$ is indeed a normalised
$+1$-eigenvector of $U_{\cal AB}$:

$\begin{split}\ket{\theta}&=\frac{1}{\sqrt{2{\cal
R}_{s,t}}}\sum_{(u,v)\in\overrightarrow{E}}\frac{\theta_{u,v}}{\sqrt{{\sf
w}_{u,v}}}(\ket{u,v}+\ket{v,u})\\\ &=\frac{1}{\sqrt{2{\cal
R}_{s,t}}}\sum_{(u,v)\in\overrightarrow{E}}\left(\sqrt{{\sf w}_{u,v}}({\sf
p}_{u}-{\sf p}_{v})\ket{u,v}+({\sf p}_{u}-{\sf p}_{v})\sqrt{{\sf
w}_{u,v}}\ket{v,u}\right)\\\ &=\frac{1}{\sqrt{2{\cal
R}_{s,t}}}\left(\sum_{u\in V}{\sf
p}_{u}\sum_{v\in\Gamma(u)}(-1)^{\Delta_{u,v}}\sqrt{{\sf
w}_{u,v}}\ket{u,v}+{\sf SWAP}\sum_{u\in V}{\sf
p}_{u}\sum_{v\in\Gamma(u)}(-1)^{\Delta_{u,v}}\sqrt{{\sf
w}_{u,v}}\ket{u,v}\right)\\\ &=(I-\Pi_{\cal A})\sqrt{\frac{2}{{\cal
R}_{s,t}}}\sum_{u\in V}{\sf p}_{u}\sqrt{{\sf
w}_{u}}\ket{\psi_{u}}.\end{split}$ (6)

Not only does (6) tells us that $\Pi_{\cal A}\ket{\theta}=0$, it also
immediately shows us how to decompose $\ket{\theta}$ to obtain the factor
$\ket{{\sf p}}$, where we make use of the fact that ${\sf p}_{s}={\cal
R}_{s,t}$:

$\displaystyle\ket{\theta}$ $\displaystyle=(I-\Pi_{\cal
A})\sqrt{\frac{2}{{\cal R}_{s,t}}}(\sum_{u\in V}{\sf p}_{u}\sqrt{{\sf
w}_{u}}\ket{\psi_{u}}=(I-\Pi_{\cal A})\ket{{\sf p}}+(I-\Pi_{\cal
A})\sqrt{\frac{2}{{\cal R}_{s,t}}}{\sf p}_{s}\sqrt{{\sf w}_{s}}\ket{\psi_{u}}$
$\displaystyle=(I-\Pi_{\cal A})\ket{{\sf p}}+\sqrt{{\cal R}_{s,t}{\sf
w}_{s}}\ket{\psi_{s}^{+}},$

which we can rewrite to

$\ket{\psi_{s}^{+}}=\frac{1}{\sqrt{{\cal R}_{s,t}{\sf
w}_{s}}}\ket{\theta}-(I-\Pi_{\cal A})\frac{1}{\sqrt{{\cal R}_{s,t}{\sf
w}_{s}}}\ket{{\sf p}}.$ (7)

Lastly, since ${\sf p}_{t}=0$, we immediately have by its definition in (4)
that $\ket{{\sf p}}\in{\cal B}$, meaning $\Pi_{\cal B}\ket{{\sf p}}=\ket{{\sf
p}}$. Hence by applying Lemma 2.7 with the parameters
$\ket{\psi}=\ket{\psi_{s}^{+}}$, $\ket{\varphi}=\ket{\theta}$,
$\ket{\phi}=-\frac{1}{\sqrt{{\cal R}_{s,t}{\sf w}_{s}}}\ket{{\sf p}}$ and
$p=\frac{1}{{\cal R}_{s,t}{\sf w}_{s}}$, we find that the resulting state
after running phase estimation on the quantum walk operator $U_{\cal AB}$ with
initial state $\ket{\psi_{s}^{+}}$ is approximately the $s$-$t$ electrical
flow state.

∎

##  3 Multidimensional electrical networks

In this section, based on the multidimensional quantum walk framework [JZ23],
we extend the electrical network to the multidimensional electrical network by
generalising Kirchhoff’s Law and Ohm’s Law as Kirchhoff’s Alternative Law and
Ohm’s Alternative Law, respectively. One of the key techniques used in the
multidimensional quantum walk framework is the introduction of alternative
neighbourhoods, where each vertex is associated with a subspace instead of a
single vector (its star state) as was the case in Section 2.2.

###  3.1 Alternative neighbourhoods

######  Definition 3.1 (Alternative Neighbourhoods).

For a network $G=(V,E,{\sf w})$ and for each vertex $u\in V$, a set of
_alternative neighbourhoods_ is a collection of states $\Psi_{\star}(u)$ such
that $\ket{\psi_{u}}\in\Psi_{\star}(u)$ and

$\Psi_{\star}=\\{\Psi_{\star}(u)\subset\mathrm{span}\\{\lambda_{u,v}\ket{u,v}:v\in\Gamma(u),\lambda_{u,v}\in\mathbb{R}\\}:u\in
V\\}$

We view the states of $\Psi_{\star}(u)$ as different possibilities for
$\ket{\psi_{u}}$, only one of which is “correct”. We say we can _generate
$\Psi_{\star}$ in complexity ${\sf A}_{\star}$_ if there is a map $U_{\star}$
that can be implemented with complexity ${\sf A}_{\star}$ and for each $u\in
V$, an orthonormal basis
$\overline{\Psi}(u)=\\{\ket{{\psi}_{u,0}},\dots,\ket{{\psi}_{u,a_{u}-1}}\\}$
of size $a_{u}<\left|\Gamma(u)\right|$ for
$\mathrm{span}\\{\Psi_{\star}(u)\\}$, such that for all
$i\in\\{0,\dots,a_{u}-1\\}$, $U_{\star}\ket{u,i}=\ket{\psi_{u,i}}.$

In Definition 3.1 we never exclude the possibility that the dimension $a_{u}$
of the alternative neighbourhood $\Psi_{\star}(u)$ is equal to one, in which
case $\Psi_{\star}(u)=\\{\ket{\psi_{u,0}}\\}=\\{\ket{\psi_{u}}\\}$. If that is
the case, we will say that $u$ has no additional alternative neighbourhoods.
These alternative neighbourhoods were introduced in [JZ23] to tackle the case
where it might be computationally easier to generate $\Psi_{\star}(u)$ instead
of $\ket{\psi_{u}}$. By modifying the quantum walk operator $U_{\cal AB}$ to
reflect around the span of $\Psi_{\star}$ instead of the span of all star
states $\ket{\psi_{u}}$, this reduces the cost of applying the walk operator
$U_{\cal AB}$. As a result, one can reduce the precision needed in the phase
estimation algorithm by reducing the weight of the graph, which directly
reduces $\left\|{\sf p}^{\sf alt}\right\|$, at the cost of increasing the
effective resistance ${\cal R}_{s,t}$, without incurring an additional cost in
calling $U_{\cal AB}$.

The addition of these alternative neighbourhoods in $\Psi_{\star}$ modifies
the quantum walk operator $U_{{\cal A}{\cal B}^{\sf alt}}$, by increasing the
star space ${\cal B}$:

${\cal B}^{\sf alt}=\mathrm{span}\\{\ket{\psi_{u,i}}:u\in
V\backslash\\{s,t\\},i\in\\{0,\dots,a_{u}-1\\}\\}.$

Through this modification, the quantum walk operator $U_{{\cal AB}}$ with
respect to $\Psi_{\star}$ is altered to

$U_{{\cal A}{\cal B}^{\sf alt}}=(2\Pi_{{\cal A}}-I)(2\Pi_{{\cal B}^{\sf
alt}}-I),$ (8)

where $\Pi_{\cal A}$ and $\Pi_{{\cal B}^{\sf alt}}$ are orthogonal projectors
onto ${\cal A}$ and ${\cal B}^{\sf alt}$ respectively, meaning

$\displaystyle 2\Pi_{{\cal A}}-I=-{\sf SWAP},$ $\displaystyle 2\Pi_{{\cal
B}^{\sf alt}}-I=2\sum_{u\in
V\backslash\\{s,t\\}}\sum_{i=0}^{a_{u}-1}\ket{\psi_{u,i}}\bra{\psi_{u,i}}-I.$

We would like to be able to apply Lemma 2.7 to this more general walk operator
as well, meaning we want to find an alternative unit $s$-$t$ flow $\theta^{\sf
alt}$, an (unnormalised) state $\ket{{\sf p}^{\sf alt}}$ and (normalised)
state $\ket{\psi}$ such that the following conditions are satisfied:

  1. 1.

$U\ket{\theta^{\sf alt}}=\ket{\theta^{\sf alt}}$.

  2. 2.

$(I-\Pi_{\cal A})\ket{{\sf p}^{\sf alt}}+\sqrt{\frac{2}{\cal E(\theta^{\sf
alt})}}\ket{\psi}=\ket{\theta^{\sf alt}}$.

  3. 3.

$\Pi_{\cal B}\ket{{\sf p}^{\sf alt}}=\ket{{\sf p}^{\sf alt}}$.

For simplicity we will assume in the rest of this work that $s$ and $t$ do not
contain any additional alternative neighbourhoods, as it greatly simplifies
notation and intuition. In our applications in Section 4 and Section 5 these
simplifying assumptions will also hold.

###  3.2 Kirchhoff’s Alternative Law

Recall the definition of a flow state from (3) for any flow $\theta$. By
construction, $\ket{\theta}$ lives in the symmetric subspace ${\cal
A}^{\perp}$, since

$\Pi_{\cal A}\left(\ket{u,v}+\ket{v,u}\right)=\frac{I-{\sf
SWAP}}{2}\left(\ket{u,v}+\ket{v,u}\right)=0.$

Hence any $s$-$t$ flow $\theta$ that we select will satisfy $\Pi_{\cal
A}\ket{\theta}=0$. For the flow state $\ket{\theta}$ to live in the
$+1$-eigenspace of $U$, it rests us to find some $\theta$ such that $\Pi_{\cal
B}\ket{\theta}=0$. In (5), we used Kirchhoff’s Law for this goal, which showed
that for any $s$-$t$ -flow $\theta$ and vertex $u\in V\backslash\\{s,t\\}$, we
have $\mbox{$\langle\psi_{u}|\theta\rangle$}=0$. However, in the
multidimensional electrical network, it must be orthogonal to all states in
${\cal B}^{\sf alt}$ instead of ${\cal B}$. That is, the state
$\ket{\theta^{\sf alt}}$ must be orthogonal to all of
$\mathrm{span}(\Psi_{\star}(u))$ for every $u\in V\backslash\\{s,t\\}$. We
therefore modify Kirchhoff’s Law to be Kirchhoff’s Alternative Law.

######  Definition 3.2 (Kirchhoff’s Alternative Law).

For any $s$-$t$ alternative flow $\theta^{\sf alt}$ with respect to a
collection of alternative neighbourhoods $\Psi_{\star}$ on an electrical
network $G=(V,E,{\sf w})$ with $s,t\in V$, the corresponding flow state
$\ket{\theta^{\sf alt}}$ is orthogonal to $\mathrm{span}(\Psi_{\star}(u))$ for
every $u\in V\backslash\\{s,t\\}$, that is,
$\langle{\psi}_{u,i}|\theta\rangle=0$ for each $i\in\\{0,1,\cdots,a_{u}-1\\}$.

We refer to any unit $s$-$t$ flow satisfying Kirchhoff’s Alternative Law as an
alternative unit $s$-$t$ flow. Similarly as in Definition 2.2, we define the
$s$-$t$ alternative electrical flow with respect to $\Psi_{\star}$ as the
alternative unit $s$-$t$ flow achieving minimal energy:

######  Definition 3.3 (Alternative Electrical Flow).

For a collection of alternative neighbourhoods $\Psi_{\star}$ on an electrical
network $G=(V,E,{\sf w})$ with $s,t\in V$, the _$s$ -$t$ alternative
electrical flow_ is the alternative unit $s$-$t$ flow with minimal energy
${\cal E}(\theta^{\sf alt})$. We call this minimal energy the _alternative
effective resistance_ ${\cal R}_{s,t}^{{\sf alt}}$.

Right now it might seem as this is ill-defined, as at first glance there could
very well be multiple alternative unit $s$-$t$ flows that achieve the minimal
energy ${\cal R}_{s,t}^{{\sf alt}}$, but we prove in Theorem 6.8 that the
$s$-$t$ alternative electrical flow is indeed unique (as long as any
alternative unit $s$-$t$ flow exists at all). It might be that the $s$-$t$
electrical flow also satisfies Kirchhoff’s Alternative Law, meaning that it
coincides with the $s$-$t$ alternative electrical flow. We show an example of
this in Section 4 and this allows us to apply Lemma 2.7 directly using similar
parameters as in Corollary 2.8. The other side of the spectrum is that there
might not be any $s$-$t$ flow at all that satisfies Kirchhoff’s Alternative
Law, in which case the $s$-$t$ alternative electrical flow does not exist. We
show an example of this shortly. The most likely scenario however is that we
are right in the middle where the $s$-$t$ electrical flow and $s$-$t$
alternative electrical flow do not coincide, meaning we can not rely on Ohm’s
Law.

###  3.3 Ohm’s Alternative Law

To apply Lemma 2.7, we still need to find an (unnormalised) state $\ket{{\sf
p}^{\sf alt}}$ and (normalised) state $\ket{\psi}$ such that

  1. 1.

$(I-\Pi_{\cal A})\ket{{\sf p}^{\sf alt}}+\sqrt{\frac{2}{\cal E(\theta^{\sf
alt})}}\ket{\psi}=\ket{\theta^{\sf alt}}$.

  2. 2.

$\Pi_{\cal B}\ket{{\sf p}^{\sf alt}}=\ket{{\sf p}^{\sf alt}}$.

In the case that the $s$-$t$ alternative electrical flow $\theta^{\sf alt}$
does not overlap with the $s$-$t$ electrical flow, we will not be able to find
a potential vector ${\sf p}$ defined on the vertices $V$ satisfying Ohm’s Law.
So instead we will be looking for a potential vector ${\sf p}^{\sf alt}$ on
the edges $E$, meaning it assigns a potential ${\sf p}^{\sf alt}_{u,v}$ to
each edge $(u,v)\in E$.

######  Definition 3.4 (Alternative Potential).

An _alternative potential vector_ (or alternative potential function) on a
network $G=(V,E,{\sf w})$ is a real-valued function ${\sf p}^{\sf
alt}:E\rightarrow\mathbb{R}$ that assigns a potential ${\sf p}_{u,v}$ to each
ordered pair $(u,v)\in E$.

Similarly to how the potential vector satisfied ${\sf p}_{s}={\cal R}_{s,t}$
and ${\sf p}_{t}=0$, we require the alternative potential vector ${\sf p}^{\sf
alt}$ to satisfy ${\sf p}^{\sf alt}_{s,v}={\cal R}_{s,t}^{{\sf alt}}$ and
${\sf p}^{\sf alt}_{t,v}=0$ for every $v\in\Gamma(s)$ (resp. $v\in\Gamma(t)$).
We then define its corresponding state in ${\cal H}$ as

$\ket{{\sf p}^{\sf alt}}=\sqrt{\frac{2}{{\cal R}(\theta^{\sf
alt})}}\sum_{(u,v)\in\overrightarrow{E}:s\notin(u,v)}\sqrt{{\sf w}_{u,v}}({\sf
p}^{\sf alt}_{u,v}\ket{u,v}-{\sf p}^{\sf alt}_{v,u}\ket{v,u}).$ (9)

######  Definition 3.5 (Ohm’s Alternative Law).

Let $\theta^{\sf alt}$ be the $s$-$t$ alternative electrical flow with respect
to a collection of alternative neighbourhoods $\Psi_{\star}$ on an electrical
network $G=(V,E,{\sf w})$ with $s,t\in V$. Then there exists an alternative
potential vector ${\sf p}^{\sf alt}$ that assigns a potential ${\sf p}^{\sf
alt}_{u,v}$ on each edge $(u,v)\in E$ such that the associated state
$\ket{{\sf p}^{\sf alt}}$ (see (9)) satisfies $\Pi_{\cal B}\ket{{\sf p}^{\sf
alt}}=\ket{{\sf p}^{\sf alt}}$ and the potential difference between $(u,v)$
and $(v,u)$ is equal to the amount of electrical flow $\theta^{\sf alt}_{u,v}$
along $(u,v)$ multiplied with the resistance $1/{\sf w}_{u,v}$, that is, ${\sf
p}^{\sf alt}_{u,v}-{\sf p}^{\sf alt}_{v,u}=\theta^{\sf alt}_{u,v}/{\sf
w}_{u,v}$.

We have not yet introduced the necessarily tools to show that there always
exists a potential vector ${\sf p}^{\sf alt}$ satisfying Ohm’s Alternative
Law, we will do this in Theorem 6.10. In the following examples and
applications, we therefore show existence by explicitly constructing
$\ket{{\sf p}^{\sf alt}}$. If the potential vector ${\sf p}^{\sf alt}$
satisfies Ohm’s Alternative Law, then $\ket{{\sf p}^{\sf alt}}$ is precisely
the state we need to apply Lemma 2.7:

$\displaystyle\ket{\theta^{\sf alt}}$ $\displaystyle=\frac{1}{\sqrt{2{\cal
R}_{s,t}^{{\sf
alt}}}}\sum_{(u,v)\in\overrightarrow{E}}\frac{\theta_{u,v}}{\sqrt{w_{u,v}}}(\ket{u,v}+\ket{v,u})$
$\displaystyle=\frac{1}{\sqrt{2{\cal R}_{s,t}^{{\sf
alt}}}}\sum_{(u,v)\in\overrightarrow{E}}\left(\sqrt{{\sf w}_{u,v}}({\sf
p}^{\sf alt}_{u,v}-{\sf p}^{\sf alt}_{v,u})\ket{u,v}+\sqrt{{\sf w}_{u,v}}({\sf
p}^{\sf alt}_{u,v}-{\sf p}^{\sf alt}_{v,u})\ket{v,u}\right)$
$\displaystyle=\frac{1}{\sqrt{2{\cal R}_{s,t}^{{\sf
alt}}}}\left(\sum_{(u,v)\in\overrightarrow{E}}\sqrt{{\sf w}_{u,v}}({\sf
p}^{\sf alt}_{u,v}\ket{u,v}-{\sf p}^{\sf alt}_{v,u}\ket{v,u})+{\sf
SWAP}\sum_{(u,v)\in\overrightarrow{E}}\sqrt{{\sf w}_{u,v}}({\sf p}^{\sf
alt}_{u,v}\ket{u,v}-{\sf p}^{\sf alt}_{v,u}\ket{v,u})\right)$
$\displaystyle=(I-\Pi_{\cal A})\sqrt{\frac{2}{{\cal R}_{s,t}^{{\sf
alt}}}}\sum_{(u,v)\in\overrightarrow{E}}\sqrt{{\sf w}_{u,v}}({\sf p}^{\sf
alt}_{u,v}\ket{u,v}-{\sf p}^{\sf alt}_{v,u}\ket{v,u})$
$\displaystyle=(I-\Pi_{\cal A})\ket{{\sf p}^{\sf alt}}+(I-\Pi_{\cal
A})\sqrt{\frac{2}{{\cal R}_{s,t}^{{\sf
alt}}}}\sum_{v\in\Gamma(s)}(-1)^{\Delta_{s,v}}{\sf p}^{\sf
alt}_{s,v}\sqrt{{\sf w}_{s,v}}\ket{s,v}$ $\displaystyle=(I-\Pi_{\cal
A})\ket{{\sf p}^{\sf alt}}+\sqrt{{{\cal R}_{s,t}^{{\sf alt}}}{\sf
w}_{s}}\ket{\psi_{s}^{+}}.$

In the following examples and applications where we explicitly construct the
state $\ket{{\sf p}^{\sf alt}}$, we need to verify that it satisfies
$\Pi_{\cal B}\ket{{\sf p}^{\sf alt}}=\ket{{\sf p}^{\sf alt}}$. To assist in
this verification, we introduce the states $\ket{{\sf p}^{\sf
alt}_{|u}}=(\ket{u}\bra{u}\otimes I)\ket{{\sf p}^{\sf alt}}$ for $u\in V$. To
verify whether $\Pi_{\cal B}\ket{{\sf p}^{\sf alt}}=\ket{{\sf p}^{\sf alt}}$,
it will be sufficient to verify whether each $\ket{{\sf p}^{\sf alt}_{|u}}$
lies in $\mathrm{span}\\{\Psi_{\star}(u)\\}$, since we can decompose
$\ket{{\sf p}^{\sf alt}}$ as

$\begin{split}\ket{{\sf p}^{\sf alt}}&=\sqrt{\frac{2}{{\cal R}(\theta^{\sf
alt})}}\sum_{(u,v)\in\overrightarrow{E}:s\notin(u,v)}\sqrt{{\sf w}_{u,v}}({\sf
p}^{\sf alt}_{u,v}\ket{u,v}-{\sf p}^{\sf alt}_{v,u}\ket{v,u})\\\
&=\sqrt{\frac{2}{{\cal R}(\theta^{\sf alt})}}\sum_{u\in
V}\sum_{v\in\Gamma(u)}(-1)^{\Delta_{u,v}}{\sf p}^{\sf alt}_{u,v}\sqrt{{\sf
w}_{u,v}}\ket{u,v}\\\ &=\sqrt{\frac{2}{{\cal R}(\theta^{\sf alt})}}\sum_{u\in
V}\ket{{\sf p}^{\sf alt}_{|u}}.\end{split}$ (10)

In the special case where $u$ has no additional alternative neighbourhoods,
for $\ket{{\sf p}^{\sf alt}_{|u}}$ to lay in
$\mathrm{span}\\{\Psi_{\star}(u)\\}=\mathrm{span}\\{\ket{\psi_{u}}\\}$, the
edge potentials ${\sf p}_{u,v}$ must be the same for each $v\in\Gamma(u)$.

###  3.4 Examples

Having rebuilt the connection between the alternative potential vector and
$s$-$t$ alternative electrical flow in the multidimensional quantum electrical
network framework, we now provide some intuition for these new definitions by
providing a few examples.

Consider the network $G=(V,E,{\sf w})$ with the vertex set $V=\\{s,x,y,t\\}$
and directed edge set $\overrightarrow{E}=\\{(s,x),(x,y),(x,t),(y,t)\\}$,
where each edge $(u,v)\in\overrightarrow{E}$ has weight ${\sf w}_{u,v}=1/4$,
except for the edge $(s,x)$, which has weight ${\sf w}_{s,x}=1$. This is
visualised in Figure 1. These directions and weight assignments give rise to
the following star states for each of our $4$ vertices:

$\displaystyle\ket{\psi_{s}}=\ket{s,x},$
$\displaystyle\ket{\psi_{x}}=\sqrt{\frac{2}{3}}\left(-\ket{x,s}+\frac{1}{2}\ket{x,y}+\frac{1}{2}\ket{x,t}\right),$
$\displaystyle\ket{\psi_{y}}=\sqrt{2}\left(-\frac{1}{2}\ket{y,x}+\frac{1}{2}\ket{y,t}\right),$
$\displaystyle\ket{\psi_{t}}=\sqrt{2}\left(-\frac{1}{2}\ket{t,x}-\frac{1}{2}\ket{t,y}\right).$

In Figure 1 we show the $s$-$t$ electrical flow $\theta$ on $G$ and the
corresponding potential vector ${\sf p}$. It is straightforward to verify that
$\theta$ and ${\sf p}$ satisfy Ohm’s Law, meaning ${\sf p}_{u}-{\sf
p}_{v}=\frac{\theta_{u,v}}{{\sf w}_{u,v}}$.

$s$$x$$y$$t$$1$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$${\sf w}_{u,v}$ for each
$(u,v)\in\overrightarrow{E}$$s$$x$$y$$t$$1$$\frac{2}{3}$$\frac{1}{3}$$\frac{1}{3}$$\theta_{u,v}$
for each
$(u,v)\in\overrightarrow{E}$$s$$x$$y$$t$$\frac{11}{3}$$\frac{8}{3}$$\frac{4}{3}$$0$${\sf
p}_{u}$ for each $u\in V$ Figure 1: Graph $G$ with its $s$-$t$ electrical flow
$\theta$ and corresponding potential ${\sf p}$ at each vertex.
$s$$x$$y$$t$$1$$\frac{1}{2}$$\frac{1}{2}$$\frac{1}{2}$$\theta^{\sf alt}_{u,v}$
for each $(u,v)\in\overrightarrow{E}$$s$$x$$y$$t$$4$$2$$2$$4$${\sf p}^{\sf
alt}_{u,v}$ for each $(u,v)\in\overrightarrow{E}$$s$$x$$y$$t$$3$$0$$0$$2$${\sf
p}^{\sf alt}_{u,v}$ for each $(v,u)\in\overrightarrow{E}$ Figure 2: Graph $G$
where the blue vertex $x$ has an additional alternative neighbourhood. The
$s$-$t$ alternative electrical flow $\theta^{\sf alt}$ be with respect to this
extra alternative neighbourhood is displayed, as well as the corresponding
potential vector ${\sf p}^{\sf alt}$.

We now consider the case where only the vertex $x\in V$ contains an additional
alternative neighbourhood: let
$\Psi_{\star}(x)=\\{\ket{\psi_{x}},\ket{\psi_{x}^{{\sf alt}}}\\}$ where

$\ket{\psi_{x}^{{\sf
alt}}}=\sqrt{\frac{2}{3}}(\frac{1}{2}\ket{s,x}-\ket{x,y}+\frac{1}{2}\ket{x,t}),$

visualised in Figure 2. Kirchhoff’s Alternative Law states that the flow state
$\ket{\theta^{\sf alt}}$ of any unit $s$-$t$ flow $\theta^{\sf alt}$ must
additionally be orthogonal to $\ket{\psi_{x}^{\textrm{alt}}}$. Together with
being orthogonal to all the star states, meaning that the flow $\theta^{\sf
alt}$ is conserved at the vertices $x$ and $y$, this leaves us with only a
single option for $\theta^{\sf alt}$. This flow is visualised in Figure 2 and
the corresponding flow vector is given by

$\displaystyle\ket{\theta^{\sf alt}}$ $\displaystyle=\frac{1}{\sqrt{2{\cal
R}_{s,t}^{{\sf
alt}}}}\sum_{(u,v)\in\overrightarrow{E}}\frac{\theta_{u,v}}{\sqrt{{\sf
w}_{u,v}}}\left(\ket{u,v}+\ket{v,u}\right)$
$\displaystyle=\frac{1}{\sqrt{8}}\left(\frac{1}{1}\left(\ket{s,x}+\ket{x,s}\right)+\frac{1/2}{1/2}\left(\ket{x,y}+\ket{y,x}\right)+\frac{1/2}{1/2}\left(\ket{x,t}+\ket{y,t}\right)+\frac{1/2}{1/2}\left(\ket{y,t}+\ket{t,y}\right)\right)$
$\displaystyle=\frac{1}{\sqrt{8}}\left(\ket{s,x}+\ket{x,s}+\ket{x,y}+\ket{y,x}+\ket{x,t}+\ket{t,x}+\ket{y,t}+\ket{t,y}\right)$

Since this $\theta^{\sf alt}$ is the only unit $s$-$t$ flow satisfying
Kirchhoff’s Alternative Law, it is by default the $s$-$t$ alternative
electrical flow. For its alternative potential vector ${\sf p}^{\sf alt}$, we
construct $\ket{{\sf p}^{\sf alt}}$ from the bottom up by creating the states
from (10):

$\displaystyle\ket{{\sf p}^{\sf alt}_{|s}}=4\ket{s,u},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|x}}=-3\ket{x,s}+4\sqrt{\frac{1}{4}}\ket{x,y}+2\sqrt{\frac{1}{4}}\ket{x,t}),$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|y}}=-2\sqrt{\frac{1}{4}}\ket{y,x}+2\sqrt{\frac{1}{4}}\ket{y,t},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|t}}=-0\sqrt{\frac{1}{4}}\ket{t,x}-0\sqrt{\frac{1}{4}}\ket{t,y}.$

Each such $\ket{{\sf p}^{\sf alt}_{|u}}$ lies in
$\mathrm{span}\\{\Psi_{\star}(u)\\}$ respectively. The alternative potential
${\sf p}^{\sf alt}$ (see Figure 2 for all the edge potentials) satisfies ${\sf
p}^{\sf alt}_{s,x}={\cal R}_{s,t}^{{\sf alt}}=4$ and ${\sf p}^{\sf
alt}_{t,x}={\sf p}^{\sf alt}_{t,y}=0$, as well as Ohm’s Alternative Law,
meaning that each $(u,v)\in E)$ satisfies ${\sf p}^{\sf alt}_{u,v}-{\sf
p}^{\sf alt}_{v,u}=\theta^{\sf alt}_{u,v}/{\sf w}_{u,v}$. We have therefore
found the alternative potential vector ${\sf p}^{\sf alt}$ whose associated
state $\ket{{\sf p}^{\sf alt}}$ satisfies $\Pi_{\cal B}\ket{{\sf p}^{\sf
alt}}=\ket{{\sf p}^{\sf alt}}$:

$\displaystyle\ket{{\sf p}^{\sf alt}}$ $\displaystyle=\sqrt{\frac{2}{{\cal
R}(\theta^{\sf alt})}}\sum_{(u,v)\in\overrightarrow{E}:s\notin(u,v)}\sqrt{{\sf
w}_{u,v}}({\sf p}^{\sf alt}_{u,v}\ket{u,v}-{\sf p}^{\sf alt}_{v,u}\ket{v,u})$
$\displaystyle=4\ket{s,x}-3\ket{x,s}+2\ket{x,y}+\ket{x,t}-\ket{y,x}+\ket{y,t}$
$\displaystyle=4\ket{\psi_{s}}+\sqrt{\frac{3}{2}}\left(\frac{8}{3}\ket{\psi_{x}}+\frac{2}{3}\ket{\psi_{x}^{{\sf
alt}}}\right)+\sqrt{2}\ket{\psi_{y}}+0\ket{\psi_{t}}.$

As mentioned in Section 3.2, depending on the alternative neighbourhoods in
$\Psi_{\star}$, the $s$-$t$ alternative electrical flow might not exist, which
is in contrast with regular electrical networks. As such a counterexample, we
modify $G$ once more, this time removing the edge $(y,t)$ from
$\overrightarrow{E}$. It is clear that any unit $s$-$t$ flow $\theta^{\sf
alt}$ must satisfy $\theta^{\sf alt}_{s,x}=\theta^{\sf alt}_{x,t}=1$ and
$\theta^{\sf alt}_{x,y}=0$, but in doing so, it will not satisfy Kirchhoff’s
Alternative Law, as the associated state $\ket{\theta^{\sf alt}}$ is not
orthogonal to $\ket{\psi_{x}^{{\sf alt}}}$:

$\mbox{$\langle\psi_{x}^{{\sf alt}}|\theta^{\sf
alt}\rangle$}=\sqrt{\frac{2}{3}}.$

$s$$x$$y$$t$$1$$\frac{1}{4}$$\frac{1}{4}$${\sf w}_{u,v}$ for each
$(u,v)\in\overrightarrow{E}$$s$$u$$v$$t$$1$$\frac{1}{2}$$\frac{1}{2}$$\theta^{\sf
alt}_{u,v}$ for each $(u,v)\in\overrightarrow{E}$ Figure 3: Graph $G$ where
the blue vertex $x$ has an additional alternative neighbourhood
$\ket{\psi_{x}^{\textrm{alt}}}$. There is no unit flow from $s$ to $t$
satisfying Kirchhoff’s Alternative Law possible in this graph.

##  4 Electrical flow sampling on one-dimensional random hierarchical graphs

Recently, [BLH23] have shown that there is an exponential separation between
quantum and classical algorithms in finding a marked vertex in one-dimensional
random hierarchical graphs, which is a generalization of the result of the
welded tree problem [CCD+03]. In this section, we show that for one-
dimensional random hierarchical graphs, we can efficiently generate a set of
alternative neighbourhoods $\Psi_{\star}$ such that the resulting $s$-$t$
alternative electrical flow matches the $s$-$t$ electrical flow, meaning it
satisfies Ohm’s Law. We show that this allows us to invoke Lemma 2.7 with
similar parameters as in Corollary 2.8, allowing us to efficiently approximate
the $s$-$t$ electrical flow and sample from it to find a marked vertex,
recovering some of the results from [BLH23].

Following [BLH23], we now define the one-dimensional random hierarchical graph
model with nodes $S_{0},S_{1},\dots,S_{n}$.

######  Definition 4.1 (Hierarchical graph on a line supergraph
$\mathcal{G}$).

A _hierarchical graph on a line supergraph_
$\mathcal{G}=(\mathcal{V}=\\{0,\dots,n\\},\mathcal{E})$ of length $n$ is
defined by a set of nodes $S_{v}$ for each $v\in\mathcal{V}$ and a set of
edges $E_{u,v}$ for each $(u,v)\in\mathcal{E}$ such that $s_{v}=|S_{v}|$ and
$e_{(u,v)}=|E_{u,v}|$. There are two special start and exit nodes
$S_{0}=\\{s\\}$ and $S_{n}=\\{t\\}$, meaning $s_{0}=s_{n}=1$. Define
$V=\bigcup_{v\in\mathcal{V}}S_{v},E=\bigcup_{(u,v)\in\mathcal{E}}E_{u,v}$ and
$G=(V,E)$. For each $(u,v)\in E(G)$, the edge set $E_{u,v}$ denotes the set of
edges between the nodes between $S_{u}$ and $S_{v}$.

$S_{0}$${\sf w}_{1}$$S_{1}$${\sf w}_{2}$$S_{2}$${\sf w}_{3}$$S_{3}$${\sf
w}_{4}$$S_{4}$${\sf w}_{5}$$S_{5}$${\sf w}_{6}$$S_{6}$ Figure 4: A line
supergraph $\mathcal{G}$ with nodes $S_{0},S_{1},\dots,S_{6}$. The black nodes
are subsets of $V_{\mathrm{even}}$, where the edge directions are reversed and
where all adjacent edges have the same weight and direction.

######  Definition 4.2 (Balanced hierarchical graph).

A hierarchical graph on a supergraph $G$ is said to be _balanced_ if for every
$(u,v)\in E(G)$, the number of edges connecting a fixed node $\alpha\in S_{u}$
to nodes in $S_{v}$ is the same for each $\alpha$.

######  Definition 4.3 (Edge-edge ratio).

Consider a hierarchical graph on the line supergraph $G$ which has nodes
$S_{0},S_{1},\dots,S_{n}$ where each node $S_{i}$ contains
$s_{0},s_{1},\dots,s_{n}$ many vertices. Let $e_{k}$ and $\mathcal{E}_{k}$
denote the number of edges and the set of edges between the nodes $S_{k-1}$
and $S_{k}$ respectively. Then the _edge ratios_ $r_{k}$ for
$k\in\\{0,\dots,n-1\\}$ are defined as

$r_{k}=\frac{e_{k+1}}{e_{k}}.$

######  Definition 4.4 (Edge-vertex ratio).

A hierarchical graph on the line supergraph $G=(V,E)$ which has nodes
$S_{0},S_{1},\dots,S_{n}$ possesses _edge-vertex ratios_
$\kappa_{0},\kappa_{1},\dots,\kappa_{n}$ given by

$\kappa_{j}=\frac{e_{j}}{s_{j}}.$ (11)

For a $D$-regular random balanced hierarchical graph on a line supergraph
$G=(V,E)$, we have
$e_{i}+e_{i+1}=e_{i}+r_{i}e_{i}=\kappa_{i}s_{i}+r_{i}\kappa_{i}s_{i}=Ds_{i}$
and $\kappa_{i}(1+r_{i})=D.$ Let $\ell=\Theta(n)$ be an integer such that
$2^{\ell}\gg|V|$, where $|V|$ is the number of vertices in the one-dimensional
random hierarchical graph $G$. This does impose the restriction that $|V|$ can
be at most exponential in $n$. To each vertex in $V$, we assign a random name
from the set $\\{0,1\\}^{\ell}$. To access the neighbours of a particular
vertex, we are given quantum access to an adjacency list oracle $O_{G}$ for
the graph $G$. Given an $\ell$-bit string $\sigma\in\\{0,1\\}^{\ell}$
corresponding to a vertex $u\in V$, the adjacency list oracle $O_{G}$ provides
the bit strings of the neighbouring vertices in $\Gamma(u)$. If $\sigma$ does
not correspond to any vertex, which will most often be the case than not since
$2^{\ell}\gg|V$, the oracle instead returns $\perp$. This oracle structure
effectively forces any algorithm to start in $s$ and traverse the graph $G$
from there, as it is infeasible to try and guess the name of any other vertex
in $V$.

######  Problem 4.5 (One-dimensional random hierarchical graph problem).

We are given an adjacency list oracle $O_{G}$ to the one-dimensional random
hierarchical graph $G$ ($D$-regular) on the line supergraph of length $n$ and
the possibility to check whether any vertex $u$ is equal to $t$. Given the
$\ell$-bit string associated to the starting vertex $s\in\\{0,1\\}^{\ell}$,
the goal is to output the $\ell$-bit string corresponding to the other root
$t$.

Before we can use Lemma 2.7 to tackle this problem, we must turn $G$ into an
electrical network (see Definition 2.4), meaning we have to assign a weight
and direction to each of its edges. We assign all edges in $E_{k}$ the same
weight for $k\in\\{1,2,\dots,n\\}$ and the weight ${\sf w}_{k}$ changes every
two layers. Without loss of generality, we assume that $n$ is an even number
and set ${\sf w}_{1}=1$ and

${\sf w}_{k}=\prod_{i=1}^{\lfloor
k/2\rfloor}\left(\frac{1}{r_{2i-1}}\right)^{2}.$ (12)

For each vertex $u\in S_{i}$ where $i\in\\{0,1,\dots,2n\\}$, we find that
${\sf w}_{u}=\sum_{v\in\Gamma(u)}{\sf w}_{u,v}=\kappa_{i}{\sf
w}_{k}+(D-\kappa_{i}){\sf w}_{k+1}$. We define the set of directed edges as
follows:

$\overrightarrow{E}=\bigcup_{k\text{ mod }4\in\\{0,1\\}}\\{(u,v):u\in
S_{k-1},v\in S_{k}\\}\cup\bigcup_{k\text{ mod }4\in\\{2,3\\}}\\{(u,v):v\in
S_{k-1},u\in S_{k}\\}.$ (13)

See Figure 4 for an example of a line supergraph where this edge orientation
and weight assignments is visualised. By viewing $G$ as an electrical network,
it is straightforward to directly compute the effective resistance ${\cal
R}_{s,t}$ via the resistance laws for electrical circuits in series and
parallel [Sie86]. As a result we find for the weight assignment from (12) that

${\cal R}_{s,t}=\frac{1}{D}+\sum_{k=2}^{n}\frac{1}{e_{k}{\sf w}_{k}}.$ (14)

Since one-dimensional random hierarchical graphs generalise the welded tree
graph, it should come as no surprise that we will use a collection of
alternative neighbourhood that generalises the one used in [JZ23] to traverse
the welded tree graph:

######  Definition 4.6 (Alternative Fourier Neighbourhood).

Let $G$ be a network. For any vertex $u\in V(G)$ with neighbours
$\Gamma(u)=\\{v_{0},v_{1},\dots v_{D-1}\\}$. Let $\omega_{D}=\exp(2\pi i/D)$
be the $D$-th root of unity. Then for each $j\in\\{0,1,2,\dots,D-1\\}$, the
$j$’th Fourier basis state is given by:

$\ket{\hat{\psi}^{j}_{u}}:=\frac{1}{\sqrt{D}}\sum_{i=0}^{D-1}\omega_{D}^{i\cdot
j}\ket{u,v_{i}}$

We define the _alternative Fourier neighbourhood of dimension $D$_ of the
vertex $u$ as

$\hat{\Psi}_{\star}(u)=\\{\ket{\hat{\psi}^{1}_{u}},\ket{\hat{\psi}^{2}_{u}},\dots\ket{\hat{\psi}^{D-1}_{u}}\\}.$

Recall that we defined the weights in (12) and the edge directions in (13) in
an alternating fashion. This induces a partition of $V$ into
$V_{\mathrm{even}}=\bigcup_{v\in\mathcal{V}:v\text{ is even }}S_{v}$ and
$V_{\mathrm{odd}}=\bigcup_{v\in\mathcal{V}:v\text{ is odd }}S_{v}$. We can
assume without loss of generality that we know for any $u\in V$ whether it
belongs to $V_{\mathrm{even}}$ or $V_{\mathrm{odd}}$ by keeping track of the
parity of the distance from $s$ that is initially 0, and flips every time the
algorithm takes a step. For a more detailed argument why this assumption is
without loss of generality, we refer the reader to the end of Section 4 in
[JZ23]. Note that at each vertex in $V_{\mathrm{even}}$ the edge directions
are reversed and all adjacent edges have the same weight (see Figure 4). It is
therefore straightforward to generate the star state $\ket{\psi_{u}}$ for each
$u\in V_{\mathrm{even}}$, since
$\ket{\psi_{u}}\propto\ket{\hat{\psi}^{0}(u)}$. For these vertices, we
therefore do not consider any additional alternative neighbourhoods, meaning
$\Psi_{\star}(u)=\\{\ket{\psi_{u}}\\}$. For $u\in S_{i}\subseteq
V_{\mathrm{odd}}\backslash\\{t\\}$, we let the set of alternative
neighbourhoods for any $u\in V_{\mathrm{odd}}$ be the alternative Fourier
neighbourhood (see Definition 4.6): $\Psi_{\star}(u)=\hat{\Psi}_{\star}(u).$

######  Lemma 4.7.

The quantum walk operator $U_{{\cal A}{\cal B}^{\sf alt}}$ as defined in (8)
can be implemented in $O(1)$ queries to $O_{G}$ and $O(nD)$ elementary
operations.

###### Proof.

The unitary $U_{{\cal A}{\cal B}^{\sf alt}}$ consists of the two reflections
$2\Pi_{\cal A}-1$ and $2\Pi_{{\cal B}^{\sf alt}}-1$. Since the former is (up
to a sign difference) equal to the ${\sf SWAP}$ operator on two registers,
each containing bit strings of length $\ell=\Theta(n)$, it can be implemented
in $0$ queries and $O(n)$ elementary operations. The cost of implementing
$2\Pi_{{\cal B}^{\sf alt}}-1$ follows almost directly from the proof of Lemma
4.4 in [JZ23], which proves the $D=3$ case. By considering general $D$ in
their proof, it still holds that we only need $O(1)$ queries to $O_{G}$ to
apply $2\Pi_{{\cal B}^{\sf alt}}-1$. The number of elementary operations
needed in their proof is in the general case dominated by the cost of the
following operation (needed to generate the state $\ket{\hat{\psi}^{j}_{u}}$),
which for each $j\in\\{0,\dots,D-1\\}$ applies the map

$\ket{j}\left(\sum_{i=0}^{D-1}\omega_{D}^{i\cdot
j}\ket{i,0}\right)\ket{v_{0},v_{1},\dots
v_{D-1}}\mapsto\ket{j}\left(\sum_{i=0}^{D-1}\omega_{D}^{i\cdot
j}\ket{i,v_{i}}\right)\ket{v_{0},v_{1},\dots v_{D-1}}.$

By conditioning on the value $i$, we can copy over the $i$’th value in the
$\ket{v_{0},v_{1},\dots v_{D-1}}$ register, but this will require $O(nD)$
elementary operations. This far exceeds the complexity of implementing the
Quantum Fourier Transform $F_{D}$, which requires $O(\log(D)\log\log(D))$
elementary operations [HH00]. ∎

We now show how to apply Lemma 2.7 with the quantum walk operator $U_{{\cal
A}{\cal B}^{\sf alt}}$, where ${\cal B}^{\sf
alt}=\mathrm{span}\\{\mathrm{span}(\Psi_{\star}(u)):u\in
V\backslash\\{s,t\\}\\}$. We choose the same parameters as in Corollary 2.8.
This means that for $\ket{\theta}$ we choose the state corresponding to the
$s$-$t$ electrical flow $\theta$ on $G$, which sends one unit of flow from $s$
to $t$ by evenly distributing the one unit of flow available at each layer
$S_{i}$ to the next layer $S_{i+1}$ for each layer $i\in\\{0,\dots,n-1\\}$. By
(3) we obtain that

$\ket{\theta}=\frac{1}{\sqrt{{2\cal
R}_{s,t}}}\sum_{(u,v)\in\overrightarrow{E}}\frac{\theta_{u,v}}{\sqrt{{\sf
w}_{u,v}}}(\ket{u,v}+\ket{v,u})=\frac{1}{\sqrt{{2\cal
R}_{s,t}}}\sum_{k=0}^{n-1}\sum_{(u,v)\in\overrightarrow{E}_{k}}(-1)^{\Delta_{u,v}}\frac{1}{e_{k}\sqrt{{\sf
w}_{k}}}(\ket{u,v}+\ket{v,u}),$ (15)

and it is straightforward to verify that $\ket{\theta}$ is normalised using
(14), confirming that $\theta$ is in indeed the $s$-$t$ electrical flow. By
(7) we know that for its corresponding potential vector ${\sf p}$ and with
potential state $\ket{{\sf p}}\in{\cal B}\subseteq{\cal B}^{\sf alt}$ (see
(4)) we have

$\ket{\psi_{s}^{+}}=\frac{1}{\sqrt{{\cal R}_{s,t}D}}\ket{\theta}-(I-\Pi_{\cal
A})\frac{1}{\sqrt{{\cal R}_{s,t}D}}\ket{{\sf p}}.$

Hence we can apply Lemma 2.7 by choosing $\ket{\psi}=\ket{\psi_{s}^{+}}$,
$\ket{\phi}=-\frac{1}{\sqrt{{\cal R}_{s,t}Ds}}\ket{{\sf p}}$ and
$p=\frac{1}{{\cal R}_{s,t}D}$ for the remaining parameters, if we manage to
show that $\Pi_{{\cal B}^{\sf alt}}\ket{\theta}=0$. We achieve this with the
following claim.

######  Claim 4.8.

For any $u\in V$, define $\ket{\theta_{u}}=(\ket{u}\bra{u}\otimes
I)\ket{\theta}$. If $u\in V_{\mathrm{even}}$, then
$\ket{\theta_{u}}\propto\ket{\hat{\psi}^{0}(u)}$. If $u\in V_{\mathrm{odd}}$,
then $\ket{\theta_{u}}\propto\sum_{v\in\Gamma(u)}\theta_{u,v}\ket{u,v}$. As a
consequence, for every $u\in V$ and $\ket{\psi_{\star}}\in\Psi_{\star}(u)$ the
state $\ket{\theta_{u}}$ satisfies
$\mbox{$\langle\psi_{\star}|\theta_{u}\rangle$}=0$.

###### Proof.

By construction of $\ket{\theta}$ (see (15)), we see for any $u\in V$ that the
state $\ket{\theta_{u}}$ is equal to

$\ket{\theta_{u}}=\frac{1}{\sqrt{{2\cal
R}_{s,t}}}\sum_{v\in\Gamma(u)}\frac{\theta_{u,v}}{\sqrt{{\sf
w}_{u,v}}}\ket{u,v}.$

Let $k$ such that $u\in S_{k}$ and let
$v_{1},v_{2},\dots,v_{l}\in\Gamma(u)\cap S_{k-1}$ be the neighbours of $u$
that lay in the node $S_{k-1}$ and similarly let
$v_{l+1},\dots,v_{D}\in\Gamma(u)\cap S_{k+1}$ be the neighbours of $u$ that
lay in the node $S_{k+1}$, where $l=D/(1+r_{k})$, which is in fact an integer.
This means that $\theta_{u,v_{i}}=(-1)^{\Delta_{u,v_{i}}}/e_{k}$ for $i\in[l]$
and $\theta_{u,v_{i}}=(-1)^{\Delta_{u,v_{i}}}/e_{k+1}$ for
$i\in[D]\backslash[l]$. If $u\in V_{\mathrm{even}}$, then the weights (see
(12)) satisfy

$\sqrt{\frac{{\sf w}_{k+1}}{{\sf
w}_{k}}}=\frac{e_{k}}{e_{k+1}}=\frac{1}{r_{k}},$

meaning

$\frac{1}{e_{k}\sqrt{w_{k}}}=\frac{1}{e_{k+1}\sqrt{w_{k+1}}}.$

Additionally, since $u\in V_{\mathrm{even}}$, it holds that
$(-1)^{\Delta_{u,v_{i}}}(-1)^{\Delta_{u,v_{j}}}=-1$ for any $i\in[\ell]$ and
$j\in[D]\backslash[\ell]$, meaning
$\ket{\theta_{u}}\propto\ket{\hat{\psi}^{0}(u)}$. Since for $u\in
V_{\mathrm{even}}$ we defined $\Psi_{\star}(u)$ to be the alternative Fourier
neighbourhood (see Definition 4.6) and the Fourier basis states form an
orthonormal basis, it follows that
$\mbox{$\langle\psi_{\star}|\theta_{u}\rangle$}=0$.

Now if instead $u\in V_{\mathrm{odd}}$, then we know that ${\sf w}_{k}={\sf
w}_{k+1}$ and $(-1)^{\Delta_{u,v_{i}}}(-1)^{\Delta_{u,v_{j}}}=1$ for any
$i\in[\ell]$ and $j\in[D]\backslash[\ell]$. So
$\ket{\theta_{u}}\propto\sum_{v\in\Gamma(u)}\theta_{u,v}\ket{u,v}$. Since for
$u\in V_{\mathrm{odd}}$ we defined
$\Psi_{\star}(u)=\\{\ket{\psi_{u}}=\ket{\hat{\psi}^{0}(u)}\\}$, it follows by
the conservation of the flow $\theta$ that
$\mbox{$\langle\psi_{u}|\theta_{u}\rangle$}=\sum_{v\in\Gamma(u)}\theta_{u,v}=0$.
∎

Knowing that we can apply Lemma 2.7 for our multidimensional electrical
network, we now show how to use this information to solve Problem 4.5.

###  4.1 The algorithm

In this section, we provide a quantum algorithm that approximates the $s$-$t$
electrical flow state and samples from it to find the ending vertex $t\in V$
in a one-dimensional random hierarchical graph. As an example of such a one-
dimensional random hierarchical graph, we then apply our algorithm to the
welded tree graph.

Algorithm 1 Solving the one-dimensional random hierarchical graph problem

0: One-dimensional random hierarchical graph $G=(V,E)$ with adjacency list
oracle $O_{G}$, the $\ell$-bit string corresponding to the starting vertex
$s\in V$, a success probability parameter $\delta$.

0: The $\ell$-bit string corresponding to the ending vertex $t\in V$.

  1. 1.

Set $i=1$, $T_{1}=\Theta(\log({\cal R}_{s,t}D{\sf w}_{n}))$ and
$T_{2}=\Theta({\cal R}_{s,t}D{\sf w}_{n}\log(1/\delta))$.

  2. 2.

For $j=0$ to $T_{1}$, run phase estimation on the multidimensional quantum
walk operator $U_{{\cal A}{\cal B}^{\sf alt}}$ and state $\ket{\psi_{s}^{+}}$
to precision $O(\frac{\epsilon^{2}}{{\cal R}_{s,t}{\sf w}_{s}\left\|\ket{{\sf
p}}\right\|})$, where $\epsilon=\frac{1}{2{\cal R}_{s,t}D{\sf w}_{n}}$, and
measure the phase register. If the output is “$0$”, return the resulting state
$\ket{\theta^{\prime}}$ and immediately continue to Step $3$.

  3. 3.

Measure $\ket{\theta^{\prime}}$ to obtain an outcome $\ket{u,v}$, representing
the edge $(u,v)\in E$. Check if $u$ or $v$ is equal to $t$ and if this is the
case, return the $\ell$-bit string corresponding to $t$. Otherwise, if
$i<T_{2}$, increment $i$ by $1$ and return to Step $2$.

######  Theorem 4.9.

Let $G$ be a $D$-regular one-dimensional random hierarchical graph on the line
supergraph of length $n$ with edge ratios $r_{0},\dots,r_{n-1}$. Let ${\sf
w}_{n}=\prod_{k=1}^{\lfloor n/2\rfloor}(\frac{1}{r_{2k-1}})^{2}$ and let each
vertex in $G$ be identified by an $\ell$-bit string where $\ell=\Theta(n)$.
Given access to an adjacency list oracle $O_{G}$ to the graph $G$, there
exists a quantum algorithm that solves Problem 4.5 with success probability
$1-O(\delta)$ and cost

$\displaystyle O\left(\left\|\ket{{\sf p}}\right\|{\cal R}_{s,t}^{4}D^{4}{\sf
w}_{n}^{3}\log({\cal R}_{s,t}D{\sf w}_{n})\log(1/\delta)\right)\text{
queries},$ $\displaystyle O\left(n\left\|\ket{{\sf p}}\right\|{\cal
R}_{s,t}^{4}D^{5}{\sf w}_{n}^{3}\log({\cal R}_{s,t}D{\sf
w}_{n})\log(1/\delta)\right)\text{ time}.$

###### Proof.

The proof consists of a cost and success probability analysis of Algorithm 1.
By Lemma 2.7, each run of phase estimation in Step $2$ succeeds with
probability at least $\Theta\left(\frac{1}{{\cal R}_{s,t}D}\right)$. Hence the
probability that at least a single out of the $T_{1}=\Theta(\log({\cal
R}_{s,t}D{\sf w}_{n}))$ runs succeed is constant.

Suppose that we had a perfect copy of $\ket{\theta}$, then after measuring it
we would obtain an edge $(u,v)\in E$ containing the vertex $t$ with
probability

$\frac{1}{{\cal R}_{s,t}}\sum_{u\in\Gamma(t)}\frac{\theta_{u,t}^{2}}{{\sf
w}_{u,t}}=\frac{1}{{\cal R}_{s,t}D{\sf w}_{n}}.$

Instead, we have access to a state $\ket{\theta^{\prime}}$, which by Lemma 2.7
satisfies

$\frac{1}{2}\left\|\ket{\theta^{\prime}}\bra{\theta^{\prime}}-\ket{\theta}\bra{\theta}\right\|_{1}\leq\epsilon=\frac{1}{2{\cal
R}_{s,t}D{\sf w}_{n}}.$

Hence by measuring $\ket{\theta^{\prime}}$, we obtain an edge $(u,v)\in E$
that contains the vertex $t$ with probability at least
$\Theta\left(\frac{1}{{\cal R}_{s,t}D{\sf w}_{n}}\right)$. The probability
that a single out of the at most $T_{2}=\Theta({\cal R}_{s,t}D{\sf
w}_{n}\log(1/\delta))$ repetitions succeeds in returning the vertex $t$ is
therefore at least

$1-\left(1-O\left(\frac{1}{{\cal R}_{s,t}D{\sf
w}_{n}}\right)\right)^{T_{2}}\geq 1-O(\delta).$

For the cost of Step $2$, each iteration of the phase estimation requires

$O\left(\frac{\left\|\ket{{\sf p}}\right\|{\cal
R}_{s,t}D}{\epsilon^{2}}\right)=O(\left\|\ket{{\sf p}}\right\|{\cal
R}_{s,t}^{3}D^{3}{\sf w}_{n}^{2})$

calls to $U_{{\cal A}{\cal B}^{\sf alt}}$. By Lemma 4.7, each such call has a
cost of $O(1)$ queries and $O(nD)$ elementary operations. Since we can set up
the initial state $\ket{\psi_{s}}$ in the same cost and we run at most
$T_{1}\cdot T_{2}$ iterations of phase estimation, we find that the total
contribution of Step $2$ to the cost is

$\displaystyle O\left(\left\|\ket{{\sf p}}\right\|{\cal R}_{s,t}^{4}D^{4}{\sf
w}_{n}^{3}\log({\cal R}_{s,t}D{\sf w}_{n})\log(1/\delta)\right)\text{
queries},$ $\displaystyle O\left(n\left\|\ket{{\sf p}}\right\|{\cal
R}_{s,t}^{4}D^{5}{\sf w}_{n}^{3}\log({\cal R}_{s,t}D{\sf
w}_{n})\log(1/\delta)\right)\text{ time}.$

For the cost of Step $3$, we must only verify whether $u$ or $v$ is equal to
$t$, which can be done in zero queries and $O(\ell)=O(n)$ elementary
operations. So the cost of Step $2$ dominates the total cost of the algorithm.
∎

####  4.1.1 Welded tree Problem

As an example to show the power of this electrical flow sampling approach, we
show that Algorithm 1 can be used to solve the welded tree problem in
polynomial time, thus achieving an exponential speedup compared to any
classical algorithms, which was originally shown in [CCD+03].

A welded tree graph consists of two full binary trees of depth $h$ and
contains $2^{h+2}-2$ vertices. See Figure 5 for an example of such a graph.
The leaves of both trees are connected via two disjoint perfect matchings.
This makes it a one-dimensional random hierarchical graph on the line
supergraph of length $n=2h+1$. For each $k\in\\{0,\dots,2h+1\\}$, every node
$S_{k}$ contains

$s_{k}=\left\\{\begin{array}[]{ll}2^{k}&\mbox{if }k\in\\{0,\dots,h\\}\\\
2^{2h+1-k}&\mbox{if }k\in\\{h+1,\dots,2h+1\\},\end{array}\right.$

vertices, meaning that its edge ratios are equal to

$r_{k}=\left\\{\begin{array}[]{ll}2&\mbox{if }k\in\\{1,\dots,h\\}\\\
\frac{1}{2}&\mbox{if }k\in\\{h+1,\dots,2h+1\\}.\end{array}\right.$

Since $V=2^{h+2}-2$, we find that $\ell=2h$ satisfies $2^{\ell}\gg|V|$,
meaning each vertex is assigned a $2h$-bit string as an identifier.

######  Problem 4.10 (The welded tree problem).

Given an adjacency list oracle $O_{G}$ for the welded tree graph $G$ of depth
$h$ and the $2h$-bit string associated to the starting vertex
$s\in\\{0,1\\}^{2h}$, the goal is to output the $2h$-bit string associated to
the other root $t$.

Before we apply Theorem 4.9 to the welded tree graph, we first obtain a little
more insight about its weights ${\sf w}_{k}$. Our weight assignment from (12)
will in this example match the weight assignment from [JZ23] (see Equation 31
in their work):

${\sf w}_{k}=\left\\{\begin{array}[]{ll}2^{-2\lceil k/2\rceil}&\mbox{if
}k\in\\{1,\dots,h+1\\}\\\ 2^{-2(h+1-\lceil k/2\rceil)}&\mbox{if
}k\in\\{h+2,\dots,2h+1\\}.\end{array}\right.$ (16)

######  Theorem 4.11.

Given an adjacency list oracle $O_{G}$ to the welded tree graph $G$, there
exists a quantum algorithm that solves Problem 4.10 with success probability
$1-O(\delta)$ and cost

$\displaystyle O\left(n^{5}\log(n)\log(1/\delta)\right)\text{ queries},$
$\displaystyle O\left(n^{6}\log(n)\log(1/\delta)\right)\text{ time}.$

###### Proof.

The theorem can be derived by bounding the quantities ${\cal R}_{s,t},D,{\sf
w}_{n}$ and $\left\|\ket{{\sf p}}\right\|$ in Theorem 4.9. From (16) we see
that ${\sf w}_{n}=1/2$. Additionally, the effective resistance from (14) can
be computed to find that ${\cal R}_{s,t}=\Theta(n)$. Since $D=3$ and ${\sf
p}_{s}={\cal R}_{s,t}$ is the largest potential value, we only need to bound
$\left\|\ket{{\sf p}}\right\|$:

$\left\|\ket{{\sf p}}\right\|^{2}=\frac{2}{{\cal
R}_{s,t}}\sum_{k=0}^{n}\sum_{u\in S_{k}}{\sf p}_{u}^{2}{\sf w}_{u}\leq{\cal
R}_{s,t}\sum_{k=0}^{n}s_{k}{\sf w}_{u}=O(n^{2}).$

∎

The result of Theorem 4.9 is worse than the state of the art algorithm for the
welded trees problem by [JZ23], which has cost $O(n)$ queries and $O(n^{2})$
time, but it exemplifies how sampling from the electrical flow can provide an
exponential speedup.

$s$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{16}$$\frac{1}{16}$$t$$1$$\frac{1}{4}$$\frac{1}{4}$
Figure 5: The welded tree graph with depth $h=3$: the black vertices are the
vertices in $V_{\mathrm{even}}$, where the edge directions are reversed and
where all adjacent edges have the same weight and direction.

##  5 An exponential speedup for pathfinding using alternative electrical flow
sampling

In this section, we show that the quantum electrical flow in a
multidimensional electrical network can also be used to show an exponential
quantum-classical separation for the pathfinding problem relative to an
oracle. We achieve this by constructing, and sampling from the $s$-$t$
alternative electrical flow that we defined in Definition 3.3, which is the
flow achieving minimal energy out of all unit $s$-$t$ flows satisfying
Kirchhoff’s Alternative law, and we show that it also satisfies Ohm’s
Alternative Law through explicitly constructing the alternative potential
${\sf p}^{\sf alt}$. In all of this section we assume that the parameter $n$
is odd for readability, but the everything can be slightly modified to also
hold for even $n$.

###  5.1 Example graph $G_{1}$

Since the graph that we will try to find an $s$-$t$ path for is quite large,
we start by analysing the $s$-$t$ alternative flow and alternative potential
for smaller graphs that will form the building blocks for the larger graph. We
start with a network $G_{1}=(V,E,{\sf w})$, whose vertex set is given by
$V=\\{s,v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7},v_{8},t\\}$. We have
visualised $G_{1}$, with its directed edge set and weights in Figure 6. These
directions and weights give rise to the star states $\ket{\psi_{u}}$ for each
$u\in V$, but we will also consider additional the following additional
alternative neighbourhoods for the vertices $v_{2},v_{3},v_{8}\in V$:

$\begin{split}\ket{\psi_{v_{2}}^{\textrm{alt}}}&=\sqrt{\frac{2}{3}}\left(-\ket{v_{2},v_{4}}+\frac{1}{2}\ket{v_{2},s}+\frac{1}{2}\ket{v_{2},v_{5}}\right),\\\
\ket{\psi_{v_{3}}^{\textrm{alt}}}&=\sqrt{\frac{2}{3}}\left(\frac{1}{2}\ket{v_{3},v_{1}}-\ket{v_{3},v_{6}}+\frac{1}{2}\ket{v_{3},v_{7}}\right),\\\
\ket{\psi_{v_{8}}^{\textrm{alt}}}&=\sqrt{\frac{2}{3}}\left(\frac{1}{2}\ket{v_{8},t}-\ket{v_{8},v_{5}}+\frac{1}{2}\ket{v_{8},v_{6}}\right).\end{split}$
(17)

Any $s$-$t$ alternative unit flow $\theta^{\sf alt}$ must be conserved at
every vertex and satisfy $\theta^{\sf alt}_{s,v_{1}}=x$, $\theta^{\sf
alt}_{s,v_{2}}=y$ for some $x,y\in[0,1]$ such that $x+y=1$. For $\theta^{\sf
alt}$ to also satisfy Kirchhoff’s Alternative Law (see Definition 3.2), the
flow coming into any vertex $v_{2},v_{3},v_{8}$ through the edge with the
highest weight, must evenly be distributed along the other two neighbours.
This is visualised in Figure 6 and we end up with a single parameter $x$
(because $y=1-x$) that parametrises all possible $s$-$t$ alternative unit
flows $\theta^{\sf alt}$ on $G_{1}$. The energy of each such $\theta^{\sf
alt}$ can be explicitly calculated to see that ${\cal E}(\theta^{\sf
alt})=5y^{2}+4x^{2}+3$, and the energy is therefore minimised for $x=5/9$,
resulting in the alternative effective resistance to be ${\cal R}_{s,t}^{{\sf
alt}}=47/9$.

We now explicitly construct the alternative potential ${\sf p}^{\sf alt}$
corresponding to this $s$-$t$ alternative electrical flow, that satisfies
${\sf p}^{\sf alt}_{s,v_{1}}={\sf p}^{\sf alt}_{s,v_{2}}={\cal R}_{s,t}^{{\sf
alt}}=47/9$, ${\sf p}^{\sf alt}_{t,v_{8}}=0$ and Ohm’s Alternative Law (see
Definition 3.5). We do this by constructing the states $\ket{{\sf p}^{\sf
alt}_{|u}}\in\mathrm{span}\\{\Psi_{\star}(u)\\}$ from (10):

$\displaystyle\ket{{\sf p}^{\sf
alt}_{|s}}=\frac{47}{9}\ket{s,v_{1}}+\frac{47}{9}\ket{s,v_{2}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{1}}}=-\frac{43}{9}\ket{v_{1},s}+\frac{43}{9}\ket{v_{1},v_{3}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{2}}}=-\frac{42}{9}\ket{v_{2},s}+\frac{38}{9}\sqrt{\frac{1}{4}}\ket{v_{2},v_{4}}+\frac{46}{9}\sqrt{\frac{1}{4}}\ket{v_{2},v_{5}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{3}}}=-\frac{39}{9}\ket{v_{3},v_{1}}+\frac{52}{9}\sqrt{\frac{1}{4}}\ket{v_{3},v_{7}}+\frac{26}{9}\sqrt{\frac{1}{4}}\ket{v_{3},v_{6}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{4}}}=-2\sqrt{\frac{1}{4}}\ket{v,u}+2\sqrt{\frac{1}{4}}\ket{v,t},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{5}}}=-4\sqrt{\frac{1}{4}}\ket{v_{5},v_{8}}-4\sqrt{\frac{1}{4}}\ket{v_{5},v_{7}}-4\sqrt{\frac{1}{4}}\ket{v_{5},v_{2}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{6}}}=-2\sqrt{\frac{1}{4}}\ket{v_{6},v_{8}}-2\sqrt{\frac{1}{4}}\ket{v_{6},v_{4}}-2\sqrt{\frac{1}{4}}\ket{v_{6},v_{3}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{7}}}=-\frac{44}{9}\sqrt{\frac{1}{4}}\ket{v_{7},v_{3}}+\frac{44}{9}\sqrt{\frac{1}{4}}\ket{v_{7},v_{5}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{8}}}=-\ket{v_{8},t}+0\sqrt{\frac{1}{4}}\ket{v_{8},v_{6}})+2\sqrt{\frac{1}{4}}\ket{v_{8},v_{5}},$
$\displaystyle\ket{{\sf p}^{\sf alt}_{|t}}=0\ket{t,v_{8}}.$

It is straightforward to verify that these states indeed satisfy Ohm’s
Alternative Law as well as the equations ${\sf p}^{\sf alt}_{s,v_{1}}={\sf
p}^{\sf alt}_{s,v_{2}}=47/9$, ${\sf p}^{\sf alt}_{t,v_{8}}=0$. It is also
clear that $\ket{{\sf p}^{\sf alt}_{|u}}\in\mathrm{span}\\{\Psi_{\star}(u)\\}$
for every $u$ without additional alternative neighbourhoods, i.e.
$u\in\\{s,v_{1},v_{4},v_{5},v_{6},v_{7},t\\}$, since all edge potentials are
the same. For $u\in\\{v_{2},v_{3},v_{8}\\}$, we can confirm that $\ket{{\sf
p}^{\sf alt}_{|u}}\in\mathrm{span}\\{\Psi_{\star}(u)\\}$ by calculating that
all the amplitudes of $\ket{{\sf p}^{\sf alt}_{|u}}$ sum to $0$.

###  5.2 Example graph $G_{2}$

The second example graph $G_{2}=(V,E,{\sf w})$ (see Figure 7) is build by
combining the graph $G_{1}$ (see Figure 6) with three welded tree graph
$W_{1},W_{2},W_{3}$ (see Figure 5). The “starting” root of these three welded
tree graphs are $w_{1},w_{4}$ and $w_{6}$ respectively. In the next section we
will compose our final graph for the pathfinding example from multiple such
$G_{2}$ graphs.

As discussed in Section 4.1.1, the welded tree graph is an example of a one-
dimensional random hierarchical graph with nodes
$\\{S_{0},S_{1},\cdots,S_{n}\\}$. We additionally saw that for the weight
assignments, edge directions and alternative neighbourhoods in Section 4.1.1,
we ended up with an $s$-$t$ electrical flow that matched the $s$-$t$
alternative electrical flow, as it also satisfied Kirchhoff’s Alternative Law.
From the perspective of electrical networks, we can therefore interpret each
welded tree graph $W_{i}$ can as an edge of resistance ${\cal R}_{i}$, but we
will formalise this intuition shortly. The weights and directions of $W_{1}$
in $G_{2}$ match those from Section 4.1.1, so ${\cal R}_{i}={\cal R}$, where
${\cal R}$ is the effective resistance of a welded tree graph of depth $n$
(see (14)). The weights of $W_{2}$ and $W_{3}$ have been multiplied by a
factor of $1/4$, and their edge directions are reversed (because their
respective roots are $w_{4}$ and $w_{6}$, so we have ${\cal R}_{2}={\cal
R}_{3}=4{\cal R}$.

In $G_{2}$, the motivation for the alternative neighbourhoods, edge directions
and weight assignments in the network $G_{1}$ become clear. Just like for the
one-dimensional random hierarchical graphs in Section 4, these assignments
induces a partition of $V$ into $V_{\mathrm{even}}$ and $V_{\mathrm{odd}}$
(visualised by blue vertices in Figure 7). For each vertex $u\in
V_{\mathrm{even}}$, all adjacent edges have the same weight and direction,
allowing us to easily generate the star state $\ket{\psi_{u}}$. For each $u\in
V_{\mathrm{odd}}\backslash\\{s,t\\}$, we have
$\ket{\psi_{u}}\in\Psi_{\star}(u)=\hat{\Psi}_{\star}(u)$. Like in Section 4,
we can assume without loss of generality that we know for any $u\in V$ whether
it belongs to $V_{\mathrm{even}}$ or $V_{\mathrm{odd}}$ by keeping track of
the parity of the distance from $s$ that is initially 0, and flips every time
the algorithm takes a step.

Since the welded tree graph sends through all flow coming into one root to the
other, any $s$-$t$ alternative unit flow on $G_{2}$ is equivalent to a $s$-$t$
alternative unit flow on $G_{1}$, with the addition that we also have flow
running through each welded tree graph. By Figure 6 and Figure 7 we therefore
see that the energy of a $s$-$t$ alternative unit flow $\theta^{\sf alt}$ can
be decomposed by the energy in $G_{1}$ in addition with the energy on these
welded tree graphs and is hence given by

${\cal E}(\theta^{\sf alt})=5y^{2}+4x^{2}+3+{\cal R}_{1}y^{2}+{\cal
R}_{2}\left(\frac{x}{2}\right)^{2}+{\cal
R}_{3}\left(\frac{y}{2}\right)^{2}=(2+5{\cal R})y^{2}+(4+{\cal R})x^{2}+3.$

This is minimised by taking $x=(2{\cal R}+5)/(3{\cal R}+9)$, meaning
$y=1-x=({\cal R}+4)/(3{\cal R}+9)$. For readability, we actually keep $x$ in
the resulting alternative effective resistance, but simplify it slightly by
making use of that for these values of $x$ and $y$ we have $(2+5{\cal
R})y=(4+{\cal R})x$:

${\cal R}_{s,t}^{{\sf alt}}=(2+5{\cal R})y^{2}+(4+{\cal R})x^{2}+3=(4+{\cal
R})(x^{2}+xy)+3=(4+{\cal R})x+3.$

We now explicitly construct the alternative potential ${\sf p}^{\sf alt}$
corresponding to this $s$-$t$ alternative electrical flow, that satisfies
${\sf p}^{\sf alt}_{s,w_{1}}={\sf p}^{\sf alt}_{s,v_{2}}={\cal R}_{s,t}^{{\sf
alt}}=(4+{\cal R})x+3$, ${\sf p}^{\sf alt}_{t,v_{5}}=0$ and Ohm’s Alternative
Law. We do this by constructing the states $\ket{{\sf p}^{\sf
alt}_{|u}}\in\mathrm{span}\\{\Psi_{\star}(u)\\}$ from (10). We slightly abuse
notation however and only show the edges visible in Figure 7, meaning we will
not explicitly write down the amplitudes and basis states for edges inside the
welded tree graphs:

$\displaystyle\ket{{\sf p}^{\sf alt}_{|s}}=(3+5y+2{\cal
R}y)\ket{s,w_{1}}+(3+4x+{\cal R}x)\ket{s,v_{2}},$ $\displaystyle\ket{{\sf
p}^{\sf alt}_{|w_{1}}}=-(3+4y+2{\cal R}y)\ket{w_{1},s},$
$\displaystyle\ket{{\sf p}^{\sf alt}_{|w_{2}}}=(3+4y+{\cal
R}y)\ket{w_{2},v_{1}},$ $\displaystyle\ket{{\sf p}^{\sf
alt}_{|w_{3}}}=-(2+2x+2{\cal R}x)\sqrt{\frac{1}{4}}\ket{w_{3},v_{2}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|w_{4}}}=-(2+2x)\sqrt{\frac{1}{4}}\ket{w_{4},v_{3}},$
$\displaystyle\ket{{\sf p}^{\sf alt}_{|w_{5}}}=-(4+2y+2{\cal
R}y)\ket{w_{5},v_{1}},$ $\displaystyle\ket{{\sf p}^{\sf
alt}_{|w_{6}}}=(4+2y)\ket{w_{6},v_{4}},$ $\displaystyle\ket{{\sf p}^{\sf
alt}_{|t}}=0\ket{t,v_{5}},$ $\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{1}}}=-(3+3y+{\cal R}y)\ket{v_{1},w_{2}}+(4+4y+2{\cal
R}y)\sqrt{\frac{1}{4}}(\ket{v_{1},w_{5}}+(2+2y))\sqrt{\frac{1}{4}}\ket{v_{1},v_{3}},$
$\displaystyle\ket{{\sf p}^{\sf alt}_{|v_{2}}}=(2+4x+2{\cal
R}x)\sqrt{\frac{1}{4}}\ket{v_{2},w_{3}}+(4+2x)\sqrt{\frac{1}{4}}\ket{v_{2},v_{4}}-(3+3x+{\cal
R}x)\ket{v_{2},s},$ $\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{3}}}=-2\sqrt{\frac{1}{4}}\ket{v_{3},v_{5}}-2\sqrt{\frac{1}{4}}\ket{v_{3},w_{4}}-2\sqrt{\frac{1}{4}}\ket{v_{3},v_{1}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{4}}}=-4\sqrt{\frac{1}{4}}\ket{v_{4},v_{5}}-4\sqrt{\frac{1}{4}}\ket{v_{4},v_{2}}-4\sqrt{\frac{1}{4}}\ket{v_{4},w_{6}},$
$\displaystyle\ket{{\sf p}^{\sf
alt}_{|v_{5}}}=-\ket{v_{5},t}+0\sqrt{\frac{1}{4}}\ket{v_{5},v_{3}})+2\sqrt{\frac{1}{4}}\ket{v_{5},v_{4}}.$

It is straightforward to verify that these states indeed satisfy Ohm’s
Alternative Law for all edges outside the welded tree graphs as well as the
equations ${\sf p}^{\sf alt}_{s,w_{1}}={\sf p}^{\sf alt}_{s,v_{2}}={\cal
R}_{s,t}^{{\sf alt}}$, since $(2+5{\cal R})y=(4+{\cal R})x$ and that ${\sf
p}^{\sf alt}_{t,v_{5}}=0$. It is also clear that $\ket{{\sf p}^{\sf
alt}_{|u}}\in\mathrm{span}\\{\Psi_{\star}(u)\\}$ for every
$u\in\\{s,v_{3},v_{4},t\\}$, since all edge potentials. For
$u\in\\{v_{1},v_{2},v_{5}\\}$, we can confirm that $\ket{{\sf p}^{\sf
alt}_{|u}}\in\mathrm{span}\\{\Psi_{\star}(u)\\}$ by calculating that all the
amplitudes of $\ket{{\sf p}^{\sf alt}_{|u}}$ sum to $0$. For the edges in the
welded tree graphs, we have seen in Section 4.1.1 that the $s$-$t$ alternative
electrical flow through each welded tree graph satisfies Ohm’s Law. This means
there exist potential values for all vertices (and hence edges), that are
smaller than the potential at the root where the flows enters, in at each
welded tree graph that satisfy Ohm’s Alternative Law. These are consistent
with our potential ${\sf p}^{\sf alt}$ since

$({\sf p}^{\sf alt}_{w_{1},s}-{\sf p}^{\sf
alt}_{w_{2},v_{1}})\frac{1}{y}=({\sf p}^{\sf alt}_{w_{3},v_{2}}-{\sf p}^{\sf
alt}_{w_{4},v_{3}})\frac{1}{x}=\left({\sf p}^{\sf alt}_{w_{5},v_{1}}-{\sf
p}^{\sf alt}_{w_{6},v_{4}}\right)\frac{1}{y}={\cal R}.$

Recall from the proof of Theorem 4.11 that for a welded tree graph of depth
$n$ we have ${\cal R}=\Theta(n)$, meaning that ${\cal R}_{s,t}^{{\sf
alt}}=\Theta(n)$. For the alternative potential, since for each edge potential
we have ${\sf p}^{\sf alt}_{u,v}=O(n)$, we find by (10) that

$||\ket{{\sf p}^{\sf alt}}||^{2}=\frac{2}{{\cal R}_{s,t}^{{\sf
alt}}}\sum_{(u,v)\in E}({\sf p}^{\sf alt}_{u,v})^{2}{\sf
w}_{u,v}=O(n)\sum_{(u,v)\in E}{\sf w}_{u,v}=O(n^{2}).$

$s$$v_{2}$$v_{5}$$v_{3}$$v_{6}$$v_{8}$$t$$v_{1}$$v_{4}$$v_{7}$$1$ $x$$1$
$y$$\frac{1}{4}$ $\frac{x}{2}$$\frac{1}{4}$ $\frac{x}{2}$$\frac{1}{4}$
$\frac{1}{2}$$1$ $y$$\frac{1}{4}$ $\frac{x}{2}$$\frac{1}{4}$
$\frac{y}{2}$$\frac{1}{4}$ $\frac{y}{2}$$\frac{1}{4}$ $\frac{1}{2}$$1$
$1$$\frac{1}{4}$ $\frac{y}{2}$ Figure 6: The graph $G_{1}$ with corresponding
edge directions where the blue vertices have an additional alternative
neighbour as defined in (17). For each $(u,v)\in\overrightarrow{E}$, the
weights ${\sf w}_{u,v}$ are denoted in black and the flow values $\theta^{\sf
alt}_{u,v}$ in red for any possible unit $s$-$t$ alternative flow parametrised
by $x$ and $y=1-x$.
$s$$v_{2}$$v_{4}$$v_{1}$$v_{3}$$v_{5}$$t$$W_{1}$$W_{2}$$W_{3}$$w_{1}$$w_{3}$$w_{2}$$w_{4}$$w_{6}$$w_{5}$$1$
$x$$1$ $y$$\frac{1}{4}$ $\frac{x}{2}$$\frac{1}{4}$ $\frac{x}{2}$$\frac{1}{4}$
$\frac{1}{2}$$1$ $y$$\frac{1}{4}$ $\frac{x}{2}$$\frac{1}{4}$
$\frac{y}{2}$$\frac{1}{4}$ $\frac{y}{2}$$\frac{1}{4}$ $\frac{1}{2}$$1$
$1$$\frac{1}{4}$ $\frac{y}{2}$ Figure 7: The graph $G_{2}$ with corresponding
edge directions where the blue vertices are the vertices in $V_{\mathrm{odd}}$
and have the alternative neighbourhoods
$\Psi_{\star}(u)=\hat{\Psi}_{\star}(u)$ (see Definition 4.6). Each diamond,
indexed by $i\in[3]$ represents a welded tree graph of depth $n$. For each
$(u,v)\in\overrightarrow{E}$, the weights ${\sf w}_{u,v}$ are denoted in black
and the flow values $\theta^{\sf alt}_{u,v}$ in red for any possible unit
$s$-$t$ alternative flow parametrised by $x$ and $y=1-x$. The black vertices
are the vertices in $V_{\mathrm{even}}$, where the edge directions are swapped
and where adjacent edges have the same weight and direction.

We could now apply Lemma 2.7 with parameters to obtain
$\ket{\psi}=\ket{\psi_{s}^{+}}$, $\ket{\varphi}=\ket{\theta^{\sf alt}}$,
$\ket{\phi}=-\frac{1}{\sqrt{2{\cal R}_{s,t}^{{\sf alt}}}}\ket{{\sf p}^{\sf
alt}}$ and $p=\frac{1}{2{\cal R}_{s,t}^{{\sf alt}}}$ to approximate the state
$\ket{\theta^{\sf alt}}$. Since the energy along the $s$-$t$ path
$(s,v_{2}),(v_{2},v_{4}),(v_{4},v_{5}),(v_{5},t)$ contains a constant fraction
of the energy ${\cal R}_{s,t}^{{\sf alt}}$, we could then sample from this
state to recover a $s$-$t$ path. However, since this path is of constant
length, any classical algorithm can also recover this path by an exhaustive
search of its neighbours in constant time.

###  5.3 The total graph $G$

In this section, we construct a graph $G$ by connecting $n$ graphs isomorphic
to $G_{2}$ from Section 5.2 (see Figure 7) as a path as indicated in Figure 9
and define a pathfinding problem for this type of graph.

Each layer contains three welded tree graphs $W_{1},W_{2},W_{3}$ and the
following $7$ vertices

$\displaystyle V_{p,i}:=\\{v_{p,i,j}:j\in[7]\\}.$

These layers are connected through the fact that $v_{p,i,7}=v_{p,(i+1),2}$ for
every $i\in[n-1]$. The welded tree graphs structure is shown in Figure 8 for
$j=1$ (the edge directions are simply reversed for $j\in\\{2,3\\}$) and the
weight assignment and edge directions for these welded tree graphs, as well as
for the remaining edges, are the same as for the graph $G_{2}$ in Figure 7.
The complete graph $G$ is shown in Figure 9. Due to this construction, each
vertex have degree $3$ except for the vertices $s=v_{p,1,1}$ and
$t=v_{p,n,7}$. It therefore induces the same partition of $V$ into
$V_{\mathrm{even}}$ and $V_{\mathrm{odd}}$ as in $G_{2}$ (visualised by blue
vertices in Figure 9). For each vertex $u\in V_{\mathrm{even}}$, all adjacent
edges have the same weight and direction, allowing us to easily generate the
star state $\ket{\psi_{u}}$. For each $u\in
V_{\mathrm{odd}}\backslash\\{s,t\\}$, we have
$\ket{\psi_{u}}\in\Psi_{\star}(u)=\hat{\Psi}_{\star}(u)$.

$v_{p,i,1}$$1$$v_{w,i,1,0}$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{16}$$\frac{1}{2^{n}}$$v_{p,i,6}$$1$$v_{w,i,1,2n+1}$$1$$\frac{1}{4}$$\frac{1}{4}$
Figure 8: The $1$st welded tree graph in the $i$’th layer. For $j\in\\{2,3\\}$
the edge directions are simply reversed. The black vertices are the vertices
in $V_{\mathrm{even}}$, where the edge directions are reversed and where
adjacent edges have the same weight and direction.
$i=1$$s=v_{p,1,1}$$v_{p,1,2}$$v_{p,1,3}$$v_{p,1,6}$$v_{p,1,5}$$v_{p,1,4}$$W_{1}$$W_{2}$$W_{3}$$v_{w,1,1,0}$$v_{w,1,2,2n+1}$$v_{w,1,1,2n+1}$$v_{w,1,2,0}$$v_{w,1,3,0}$$v_{w,1,3,2n+1}$$1$$1$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$$1$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$$1$$\frac{1}{4}$$i=2$$v_{p,2,6}$$v_{p,2,5}$$v_{p,2,4}$$v_{p,2,1}$$v_{p,2,2}$$v_{p,2,3}$$W_{1}$$W_{2}$$W_{3}$$v_{w,2,1,2n+1}$$v_{w,2,2,0}$$v_{w,2,1,0}$$v_{w,2,2,2n+1}$$v_{w,2,3,2n+1}$$v_{w,2,3,0}$$\frac{1}{4}$$1$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$$1$$\frac{1}{4}$$\frac{1}{4}$$1$$\frac{1}{4}$$1$$\frac{1}{4}$$\cdots\cdots$$i=n$$v_{p,n,1}$$v_{p,n,2}$$v_{p,n,3}$$v_{p,n,6}$$v_{p,n,5}$$v_{p,n,4}$$t=v_{p,n,7}$$1$$W_{1}$$W_{2}$$W_{3}$$v_{w,n,1,0}$$v_{w,n,2,2n+1}$$v_{w,n,1,2n+1}$$v_{w,n,2,0}$$v_{w,n,3,0}$$v_{w,n,3,2n+1}$$1$$1$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$$1$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$$\frac{1}{4}$$1$$\frac{1}{4}$$\cdots\cdots$
Figure 9: The total graph $G$ showing all edge directions and edge weights.
The blue vertices are the vertices in $V_{\mathrm{odd}}$ and have the
alternative neighbourhoods $\Psi_{\star}(u)=\hat{\Psi}_{\star}(u)$ (see
Definition 4.6). The black vertices are the vertices in $V_{\mathrm{even}}$,
where the edge directions are swapped and where adjacent edges have the same
weight and direction. Each diamond, indexed by $j\in[3]$ represents the
$j^{\prime}$-th welded tree graph in that layer. See Figure 8 for a detailed
overview of the welded tree graph’s structure.

All these names $v_{a,b,c}$ to refer to vertices are simply for notation
purposes to properly define the graph. Similar to the setting in Section 4, we
assign a random name from the set $\\{0,1\\}^{3n}$ to each vertex $u\in V$. To
access the neighbours of a particular vertex, we are given quantum access to
an adjacency list oracle $O_{G}$ for the graph $G$. Given an $3n$-bit string
$\sigma\in\\{0,1\\}^{3n}$ corresponding to a vertex $u\in V$, the adjacency
list oracle $O_{G}$ provides the bit strings of the neighbouring vertices in
$\Gamma(u)$. If $\sigma$ does not correspond to any vertex, which will most
often be the case than not since $2^{3n}\gg|V|$, the oracle instead returns
$\perp$.

As the graph $G$ consists of $n$ identical subgraphs isomorphic to $G_{2}$,
the flow and potential vector analysis almost directly follows from Section
5.2. Starting with the $s$-$t$ alternative electrical flow $\theta^{\sf alt}$,
we can obtain this flow by simply connecting $n$ $s$-$t$ alternative
electrical flows on each copy of $G_{2}$. This results in an alternative
effective resistance ${\cal R}_{s,t}^{{\sf alt}}=\Theta(n^{2})$. The
alternative potential ${\sf p}^{\sf alt}$ can also be obtained directly from
combining all the alternative potentials from each copy of $G_{2}$, where we
add $((4+{\cal R})x+3)(n-i)$ to each edge potential obtained from the copy of
$G_{2}$ in the $i$’th layer. This way we ensure that for every $i\in[n-1]$

$\displaystyle\ket{{\sf p}^{\sf alt}_{v_{p,i+1,1}}}=((4+{\cal
R})x+3)(n-i)\ket{\psi_{v_{p,i+1,1}}},$

meaning $||\ket{{\sf p}^{\sf alt}}||=O(n^{2}).$ We now consider the following
problem on the graph $G$, for which we exhibit a quantum algorithm that can
solve the given problem in exponentially faster than any classical algorithm
can.

######  Problem 5.1 (The pathfinding problem on a graph $G$).

Given an adjacency list oracle $O_{G}$ to the graph $G$ (as defined in Section
5.3) and the names of the starting vertex $s=0^{3n}$, the goal is to output
the names of vertices of an $s$-$t$ path.

###  5.4 The algorithm

In this section, we provide a quantum algorithm that can find the $s$-$t$
shortest path in $G$ and hence solves Problem 5.1 in polynomial time.

Algorithm 2 Quantum algorithm for solving Problem 5.1

0: Graph $G$ as defined in Section 5.3, the starting vertex $s=0^{3n}$, a
success probability parameter $\delta>0$.

0: The labels of an $s$-$t$ path on $G$.

  1. 1.

Set $i=1$, $S=\emptyset$, $T_{1}=\Theta(\log(n))$ and
$T_{2}=\Theta(n^{2}\log(n/\delta))$.

  2. 2.

For $j=0$ to $T_{1}$, run phase estimation on the multidimensional quantum
walk operator $U_{{\cal A}{\cal B}^{\sf alt}}$ and state $\ket{\psi_{s}^{+}}$
to precision $O(\epsilon^{2}/n^{2})$, where $\epsilon=O(1/n^{2})$, and measure
the phase register. If the output is “$0$”, return the resulting state
$\ket{\theta^{\prime}}$ and immediately continue to Step $3$.

  3. 3.

Measure $\ket{\theta^{\prime}}$ to obtain an outcome $\ket{u,v}$, representing
the edge $(u,v)\in E$, and add it to $S$. If $i<T_{2}$, increment $i$ by $1$
and return to Step $2$.

  4. 4.

Search through $S$ using Breadth First Search for an $s$-$t$ path and output
the path if it is found.

######  Theorem 5.2.

Let the graph $G$ be defined as in Section 5.3. Given an adjacency list oracle
$O_{G}$ to the graph $G$, there exists a quantum algorithm that solves Problem
5.1 with success probability $1-O(\delta)$ and cost

$\displaystyle O\left(n^{10}\log(n)\log(n/\delta)\right)\text{ queries},$
$\displaystyle O\left(n^{11}\log(n)\log(n/\delta)\right)\text{ time}.$

###### Proof.

The proof consists of a cost and success probability analysis of Algorithm 2,
where we focus on the success probability that the algorithm outputs the path

${\cal
P}=((s,v_{p,1,2}),(v_{p,1,2},v_{p,1,3}),(v_{p,1,3},v_{p,1,4}),\dots,(v_{p,n,4},t)).$

We invoke Lemma 2.7 with parameters $\ket{\psi}=\ket{\psi_{s}^{+}}$,
$\ket{\varphi}=\ket{\theta^{\sf alt}}$, $\ket{\phi}=-\frac{1}{\sqrt{2{\cal
R}_{s,t}^{{\sf alt}}}}\ket{{\sf p}^{\sf alt}}$ and $p=\frac{1}{2{\cal
R}_{s,t}^{{\sf alt}}}$. By Lemma 2.7 each run of phase estimation in Step $2$
succeeds with a probability of at least $\Theta\left(\frac{1}{{\cal
R}_{s,t}}\right)=\Theta\left(\frac{1}{n^{2}}\right)$. Hence the probability
that at least a single out of the $T_{1}=\Theta(\log(n))$ runs succeed is
constant.

Suppose that we had a perfect copy of $\ket{\theta^{\sf alt}}$, then after
measuring it we would obtain an edge $(u,v)\in{\cal P}$ with probability at
least

$\min\limits_{(u,v)\in{\cal P}}\frac{1}{{\cal R}_{s,t}^{{\sf
alt}}}\frac{(\theta^{\sf alt}_{u,v})^{2}}{{\sf
w}_{u,v}}=\Omega\left(\frac{1}{n^{2}}\right).$

Instead, we have access to a state $\ket{\theta^{\prime}}$, which by Lemma 2.7
satisfies

$\frac{1}{2}\left\|\ket{\theta^{\prime}}\bra{\theta^{\prime}}-\ket{\theta}\bra{\theta}\right\|_{1}\leq\epsilon=O\left(\frac{1}{n^{2}}\right).$

Hence by measuring $\ket{\theta^{\prime}}$, we obtain an edge $(u,v)\in E$
that contains the vertex $t$ with probability at least
$\Omega\left(\frac{1}{n^{2}}\right)$. The probability that all edges in ${\cal
P}$ are present in $S$ after reaching Step $4$ is due to the union bound
therefore at least

$1-\left|{\cal
P}\right|\left(1-O\left(\frac{1}{n^{2}}\right)\right)^{T_{2}}\geq
1-O(\delta).$

For the cost of Step $2$, each iteration of the phase estimation requires

$O\left(\frac{\|\ket{{\sf p}^{\sf alt}}\|{\cal R}_{s,t}^{{\sf
alt}}}{\epsilon^{2}}\right)=O(n^{8})$

calls to $U_{{\cal A}{\cal B}^{\sf alt}}$. By Lemma 4.7, each such call has a
cost of $O(1)$ queries and $O(n)$ elementary operations. Since we can set up
the initial state $\ket{\psi_{s}}$ in the same cost and we run at most
$T_{1}\cdot T_{2}$ iterations of phase estimation, we find that the total
contribution of Step $2$ to the cost is

$\displaystyle O\left(n^{10}\log(n)\log(n/\delta)\right)\text{ queries},$
$\displaystyle O\left(n^{11}\log(n)\log(n/\delta)\right)\text{ time}.$

For the cost of Step $4$, we must only do a Breadth First Search to search for
any $s$-$t$ path in the subgraph defined by the edges in $S$. Since
identifying the vertex $s$ and $t$ can both be done using a single operation
due to them having a distinct degrees, the total cost of this step is
$O(T_{2})=O(n^{2}\log(n\delta))$ queries and other basic operations. So the
cost of Step $2$ dominates the total cost of the algorithm. ∎

###  5.5 Classical lower bound

In this section we show that our Algorithm 2 actually provides an exponential
speedup compared to any classical algorithm under the assumption that the
following welded tree pathfinding problem is classically hard. To simplify the
proof of our lower bound for the pathfinding problem Problem 5.1, we use the
following assumption and the known classical lower bound of the welded tree
problem.

######  Problem 5.3 (The welded tree pathfinding problem).

Given an adjacency list oracle $O_{G}$ to the welded tree graph $G$ and the
names of the starting vertex $s$ and the ending vertex $t$, the goal is to
output the names of the vertices of an $s$-$t$ path.

It is folklore that the welded tree pathfinding problem is classically
difficult, however, there is no formal statement as far as we are aware.

######  Assumption 5.4.

There exist constants $c_{1}>0$ and $c_{2}\in(0,2)$ such that any classical
algorithm that makes at most $2^{n/6}$ number of queries to $O_{G}$ to the
welded tree graph $G$ solves Problem 5.3 with probability at most $c_{1}\cdot
2^{-c_{2}n}$.

######  Lemma 5.5 (Theorem 9 in [CCD+03]).

For the welded tree problem Problem 4.10, any classical algorithm that makes
at most $2^{n/6}$ queries to the oracle $O_{G}$ finds the ending vertex or a
cycle with probability at most $4\cdot 2^{-n/6}$.

We follow the proof of the lower bound proof in [Li23], which in turn is based
on the lower bound proof in [CCD+03]. To prove the lower bound, we analyse the
difficulty of any classical algorithm ${\cal A}$ winning a simpler game:

##### Game A

Let $n$ be odd and let $G$ be the graph as defined in Section 5.3. Let Game A
be the game where any classical algorithm $\mathcal{A}$ wins if it outputs the
name of one of the vertex $v_{p,(n+1)/2,1}$, or if the vertices visited by
$\mathcal{A}$ contain a cycle. Following [CCD+03], the additional cycle
condition that allows $\mathcal{A}$ to win in Game A allows us to analyse the
success probability of ${\cal A}$ winning. This analysis involves determining
whether a random embedding of a random rooted binary tree into the random
graph $G$ contains a cycle or the vertex $v_{p,(n+1)/2,1}$.

Given the starting vertex $s$, the random embedding of a rooted binary tree
$T$ into the graph $G$ is defined as a function $\pi$ from the vertices of $T$
to the vertices of $G$ such that $\pi(\textsf{ROOT})=s$ and such that for any
$(u,v)\in E$, we also have that $\pi(u),\pi(v)$ are neighbours in $T$. We say
that an embedding $\pi$ is proper if $\pi(u)\neq\pi(v)$ for $u\neq v$. We say
that $T$ exits under $\pi$ if $\pi(v)=v_{p,(n+1)/2,1}$. The random embedding
can be obtained as follows:

  1. 1.

Set $\pi(\textsf{ROOT})=s$.

  2. 2.

Let $i$ and $j$ be the two neighbours of ROOT in $T$ and let $u$ and $v$ be
the neighbours of $s$ in $G$. With probability $1/2$ set $\pi(i)=u$ and
$\pi(j)=v$, and with probability $1/2$ set $\pi(i)=v$ and $\pi(j)=u$.

  3. 3.

For any vertex $i$ in $T$, if $i$ is not a leaf and
$\pi(v)\notin\\{s,v_{p,(n+1)/2,1}\\}$, let $j$ and $k$ denote the children of
vertex $i$, and let $\ell$ denote its parent. Let $u$ and $v$ be the two
neighbours of $\pi(i)$ in $G$ other than $\pi(\ell)$. With probability $1/2$
set $\pi(i)=u$ and $\pi(j)=v$, and with probability $1/2$ set $\pi(i)=v$ and
$\pi(j)=u$.

######  Theorem 5.6.

Let $G$ be the graph defined in Section 5.3. Let $c_{1},c_{2}$ be the
constants from Assumption 5.4 and assume that this assumption is true. Then
any classical algorithm that makes at most $2^{n/6}$ queries to $O_{G}$ solves
Problem 5.1 with probability at most $(5+c_{1})\cdot
2^{-\min\\{c_{2},1/6\\}n}$.

###### Proof.

Let $T$ be a random rooted binary tree with $2^{n/6}$ vertices and $\pi(T)$ be
the image in the graph $G$ under the random embedding $\pi$. Given the name of
the starting vertex $s$, similar to [CCD+03], the probability of $\mathcal{A}$
winning Game $A$ can be expressed as the probability that $\pi(T)$ contains a
cycle or the vertex $v_{p,(n+1)/2,1}$.

First, $\mathcal{A}$ has to enter a welded tree subgraph to find a cycle, as
seen in Figure 9. There are two possibilities to get a cycle in a welded tree
subgraph. One is to find a cycle that contains only one root in one of the
welded tree subgraphs. In this case, Lemma 5.5 states that, in one of the
welded tree subgraphs, starting from one root, any classical algorithm that
makes at most $2^{n/6}$ queries to the oracle and finds the other root or a
cycle with probability at most $4\cdot 2^{-n/6}$. The other is to find a cycle
that contains two roots of a welded tree subgraph. By Assumption 5.4, any
classical algorithm that makes at most $2^{n/6}$ queries to the oracle and
finds such a cycle with probability at most $c_{1}\cdot 2^{-c_{2}n}$.

We can now assume that $\mathcal{A}$ will not encounter any cycle. Conditioned
on this fact, the probability that $\mathcal{A}$ finds the name of the vertex
$v_{p,(n+1)/2,1}$ can be expressed as the probability that $\pi(T)$ contains
the vertex $v_{p,(n+1)/2,1}$, for which $\pi$ must follow the corresponding
path $2n$ times, which has probability $2^{-2n}$. Since there are at most
$2^{n/6}$ tries on each path of $T$ and there are at most $2^{n/6}$ paths, the
probability of finding the name of the vertex $v_{p,(n+1)/2,1}$ is by the
union bound at most $2^{n/3}2^{-2n}\leq 2^{-5n/3}$. We have the same result if
the given name is $t$. Therefore, given the name of the starting vertex $s$
and $t$, the probability of $\mathcal{A}$ finding the vertex $v_{p,(n+1)/2,1}$
is $2\cdot 2^{n/3}2^{-2n}\leq 2^{-5n/3}$.

By combining the two cases with the union bound, we find that the probability
of $\mathcal{A}$ winning Game $A$ is at most $2^{-5n/3}+(4+c_{1})\cdot
2^{-\min\\{c_{2},1/6\\}n}\leq(5+c_{1})\cdot 2^{-\min\\{c_{2},1/6\\}n}$. Since
solving Problem 5.1 automatically wins Game $A$, the theorem follows. ∎

######  Remark 5.7.

The authors conjecture that Assumption 5.4 can be removed by showing a
classical lower bound for the welded tree pathfinding problem Problem 5.3,
perhaps by making use of the recent lower bound technique of finding a marked
vertex in random hierarchical graphs developed in the recent work by [BLH23].

##  6 Multidimensional electrical network and the alternative incidence matrix

In this section, inspired by the connection between the electrical network
$G=(V,E,{\sf w})$ and the incidence matrix $B$ of $G$, we rebuild the
connection between the multidimensional electrical network and its alternative
incidence matrix $B_{{\sf alt}}$. We then use this connection to prove the
uniqueness of the $s$-$t$ alternative flow $\theta^{\sf alt}$ and the
existence of the alternative potential ${\sf p}^{\sf alt}$ that satisfy Ohm’s
Alternative Law.

###  6.1 The incidence matrix, Kirchhoff’s Law and Ohm’s Law

We start by restating the connection between on one hand the incidence matrix
of a network $G$ and on the other hand Kirchhoff’s Law and Ohm’s Law. We
follow [Vis13, section 4] in doing so.

######  Definition 6.1 (The edge-vertex incidence matrix).

Let $G=(V,E,{\sf w})$ be a network (See Definition 2.1). The incidence matrix
$B\in\mathbb{C}^{\overrightarrow{E}\times V}$ of $G$, is the matrix whose rows
are indexed by $(u,v)\in\overrightarrow{E}$, whose columns are indexed $u\in
V$ and whose only non-zero entries are given by

$\displaystyle B_{(u,v),u}=\sqrt{{\sf w}_{u,v}},$ $\displaystyle
B_{(u,v),v}=-\sqrt{{\sf w}_{u,v}}.$

Let $W\in\mathbb{C}^{\overrightarrow{E}\times\overrightarrow{E}}$ be the
weighted diagonal matrix with diagonal entries
$W_{(u,v),(u,v)}=1/\sqrt{w_{u,v}}$ and $0$ elsewhere for where
$(u,v)\in\overrightarrow{E}$. By considering a flow $\theta$ on $G=(V,E,{\sf
w})$ not only as a function on $\overrightarrow{E}$, but also as a vector in
$\mathbb{C}^{\overrightarrow{E}}$, we can multiply it with the matrix $W$ to
obtain the weighted flow vector $W\theta\in\mathbb{C}^{\overrightarrow{E}}$
with entries $(W\theta)_{u,v}=\theta_{u,v}/\sqrt{w_{u,v}}$ for the row indexed
by $(u,v)\in\overrightarrow{E}$. The norm of $W\theta$ is therefore precisely
given by $\sqrt{{\cal E}(f)}$. By the introduction of $W\theta$, we can
rephrase Kirchhoff’s Law from Definition 2.5 as a linear equation involving
the incidence matrix $B$. Fix some ordering of the columns of $B$ of the form
$s,u_{1},\dots,u_{2},t$ for some $u_{1},u_{2}\in V\backslash\\{s,t\\}$ and
define the basis vectors ${\sf e}_{i}\in\mathbb{C}^{n}$ which have a $1$ at
the $i$-th location and zero elsewhere.

######  Definition 6.2 (Kirchhoff’s Law (incidence matrix)).

Let $\theta$ be any unit $s$-$t$ flow on an electrical network $G=(V,E,{\sf
w})$. Let $B$ be the incidence matrix of $G$. Then $\theta$ satisfies

$B^{T}W\theta=\begin{bmatrix}\sum_{v\in\Gamma(s)}\theta_{s,v}\\\
\sum_{v\in\Gamma(u_{1})}\theta_{u_{1},v}\\\ \vdots\\\
\sum_{v\in\Gamma(u_{2})}\theta_{u_{2},v}\\\
\sum_{v\in\Gamma(t)}\theta_{t,v}\end{bmatrix}=\begin{bmatrix}1\\\ 0\\\
\vdots\\\ 0\\\ -1\end{bmatrix}={\sf e}_{s}-{\sf e}_{t}.$ (18)

Recall from Definition 2.2 that the $s$-$t$ electrical flow is the flow that
minimises ${\cal E}(\theta)$ for all unit $s$-$t$ flows $\theta$. Since ${\cal
E}(\theta)=\left\|W\theta\right\|^{2}$, this means that the $s$-$t$ electrical
flow corresponds to the ‘smallest’ (in norm) solution to (18), that is, the
unique $s$-$t$ flow $\theta$ such that its flow vector satisfies
$W\theta\in\textnormal{ker}(B^{T})^{\perp}$. We can therefore recover
$W\theta$ by making use of the Moore-Penrose inverse (also known as the
pseudoinverse) of $B^{T}$, denoted by $B^{T+}$. For any matrix $A$, the Moore-
Penrose inverse $A^{+}$ (not to be confused with the conjugate transpose
$A^{\dagger}$), is the unique matrix satisfying

$\displaystyle AA^{+}A=A,$ $\displaystyle A^{+}AA^{+}=A^{+},$
$\displaystyle(AA^{+})^{\dagger}=AA^{+},$
$\displaystyle(A^{+}A)^{\dagger}=A^{+}A,$ (19)

and it is well known that $A^{+}$ maps $\textnormal{ran}(A)$ to
$\textnormal{ker}(A)^{\perp}$. Hence by left-multiplying both sides of (18)
with $B^{T+}$, we recover the following important property of electrical
networks:

######  Theorem 6.3 (Theorem 4.7 in [Vis13]).

Let $\theta$ be the $s$-$t$ electrical flow on a network $G=(V,E,{\sf w})$.
Let $B$ be the incidence matrix of $G$. Then its flow vector $W\theta$ is
given by

$W\theta=B^{T+}({\sf e}_{s}-{\sf e}_{t}).$ (20)

Just like we did with $\theta$, we can also consider a potential vector ${\sf
p}$ as a vector (hence the name) in $\mathbb{C}^{V}$ with entries ${\sf
p}_{u}$ for the row indexed by $u\in V$. In doing so, we can rephrase Ohm’s
Law from Definition 2.6 as a linear equation involving the incidence matrix
$B$. Fix some ordering of the rows of $B$ of the form
$(u_{1},v_{1}),\dots,(u_{2},v_{2})\in\overrightarrow{E}$.

######  Definition 6.4 (Ohm’s Law (incidence matrix)).

Let $\theta$ be the $s$-$t$ electrical flow on an electrical network
$G=(V,E,{\sf w})$. Let $B$ be the incidence matrix of $G$. Then there exists a
potential vector ${\sf p}$ such that

$B{\sf p}=\begin{bmatrix}\sqrt{{\sf w}_{u_{1},v_{1}}}\left({\sf
p}_{u_{1}}-{\sf p}_{v_{1}}\right)\\\ \vdots\\\ \sqrt{{\sf
w}_{u_{2},v_{2}}}\left({\sf p}_{u_{2}}-{\sf
p}_{v_{2}}\right)\end{bmatrix}=\begin{bmatrix}\frac{\theta_{u_{1},v_{1}}}{\sqrt{{\sf
w}_{u_{1},v_{1}}}}\\\ \vdots\\\ \frac{\theta_{u_{2},v_{2}}}{\sqrt{{\sf
w}_{u_{2},v_{2}}}}\end{bmatrix}=W\theta.$ (21)

In Section 2.2 we have said that we may assume the potential vector ${\sf p}$
satisfying Ohm’s Law to satisfy ${\sf p}_{s}={\cal R}_{s,t}$ and ${\sf
p}_{t}=0$, which is easier to see from the incidence matrix perspective.

######  Lemma 6.5.

Let $\theta$ be the $s$-$t$ electrical flow on an electrical network
$G=(V,E,{\sf w})$ with effective resistance ${\cal R}_{s,t}$. Then there
exists a potential vector ${\sf p}$ satisfying Ohm’s Law such that ${\sf
p}_{s}={\cal R}_{s,t}$ and ${\sf p}_{t}=0$.

###### Proof.

From the incidence matrix $B$, we can obtain $B^{T}B$, which is known as the
weighted Laplacian of $G$. It is well known in spectral graph theory (see e.g.
Theorem 2.3 in [Vis13]), that $B^{T}B$ has $0$ as an eigenvalue with
multiplicity $1$. Since $\textnormal{ker}(B)=\textnormal{ker}(B^{T}B)$, not
only does this mean that by setting ${\sf p}_{t}=0$, we still have a valid
solution to (21), but this actually makes the remaining solution unique. By
left-multiplying both sides of (20) with $(W\theta)^{T}$ we obtain together
with (21) that

${\cal R}_{s,t}=\left\|W\theta\right\|^{2}=(W\theta)^{T}B^{T+}({\sf
e}_{s}-{\sf e}_{t})={\sf p}^{T}({\sf e}_{s}-{\sf e}_{t})={\sf p}_{s}-{\sf
p}_{t}={\sf p}_{s}.$ (22)

∎

With the Moore-Penrose inverse we can in fact recover the potential from Lemma
6.5. To achieve this, we remove the last column of $B$ and last row of ${\sf
p}$ to obtain $\overline{B}$ and $\overline{{\sf p}}$, effectively forcing
${\sf p}_{t}=0$:

${\sf p}=\begin{bmatrix}\overline{{\sf p}}\\\
0\end{bmatrix}=\begin{bmatrix}\overline{B}^{+}W\theta\\\ 0\end{bmatrix}.$ (23)

###  6.2 The alternative incidence matrix, Kirchhoff’s Alternative Law and
Ohm’s Alternative Law

What is it that makes the $s$-$t$ electrical flow $\theta$ special, making it
satisfy Ohm’s Law. Why is Ohm’s Law not necessarily true for our $s$-$t$
alternative flow? Even though all flow states live in the symmetric subspace
${\cal A}^{\perp}$ by construction, we saw in (6) that the flow state
$\ket{\theta}$ of the $s$-$t$ electrical flow $\theta$ can be written as

$\ket{\theta}=(I-\Pi_{\cal A})\sqrt{\frac{2}{{\cal R}_{s,t}}}\sum_{u\in V}{\sf
p}_{u}\sqrt{{\sf w}_{u}}\ket{\psi_{u}},$

meaning that $\ket{\theta}$ in fact lives in the the symmetric star space of
${\cal H}$, which is contained in ${\cal A}^{\perp}$:

$\displaystyle H^{+\star}:=\mathrm{span}\\{(I-\Pi_{\cal A})\ket{\psi_{u}}:u\in
V\\}=\mathrm{span}\\{\ket{\psi_{u}^{+}}:u\in V\\}.$ (24)

Out of all $s$-$t$ flows, the $s$-$t$ electrical flow is the unique unit flows
such that $\ket{\theta}$ is the only corresponding flow state that is an
element of $H^{+\star}$ (see e.g. [LP16]). We will not give a formal proof of
this statement, but the intuition is that any other $s$-$t$ flow has a higher
energy, i.e. higher norm, which is due to containing a component that is
orthogonal to all of $H^{+\star}$, namely a circulation. The column space of
the incidence matrix $B$ is in fact isomorphic to $H^{+\star}$, where the
column of $B$ indexed by $u\in V$ represents $\sqrt{{\sf
w}_{u}}\ket{\psi^{+}_{u}}$ through the isometry

${\cal V}:\mathbb{C}^{|\overrightarrow{E}|}\mapsto{\cal A}^{\perp},\text{
where }{\cal V}\left(u,v\right)=\sqrt{2}(I-\Pi_{\cal
A})\ket{u,v}=\frac{1}{\sqrt{2}}\left(\ket{u,v}+\ket{v,u}\right).$ (25)

Through the addition of alternative neighbourhoods (see Definition 3.1), the
space $H_{G}^{+\star}$ is effectively enlarged. Define

$V^{{\sf alt}}:=\\{(u,i)\in
V\times\mathbb{N}:i\in\\{0,1,\cdots,a_{u}-1\\}\\}.$ (26)

Then instead of only considering the span of all $\ket{\psi_{u}^{+}}$ for
$u\in V$, we now consider the span of all alternative neighbourhoods projected
onto the symmetric subspace, meaning
$\ket{\psi_{u,i}^{+}}:=\sqrt{2}(I-\Pi_{\cal A})\ket{\psi_{u,i}}$ for $(u,i)\in
V^{{\sf alt}}$:

$\displaystyle H^{+{\sf alt}}:=\mathrm{span}\\{\ket{\psi_{u,i}^{+}}:u\in
V,i\in\\{0,1,\cdots,a_{u}-1\\}\\}.$ (27)

By modifying the incidence matrix $B$ to ensure that its column space still
represents the newly modified $H_{G}^{+{\sf alt}}$, we obtain the alternative
incidence matrix $B_{{\sf alt}}$.

######  Definition 6.6 (Alternative incidence matrix).

Let $G$ be a network and let $\Psi_{\star}$ be a collection of alternative
neighbourhoods. Let $\\{\ket{{\psi}_{u,0}},\dots,\ket{{\psi}_{u,a_{u}-1}}\\}$
be an orthonormal basis for each $\Psi_{\star}(u)\in\Psi_{\star}$. The
alternative incidence matrix $B_{{\sf
alt}}\in\mathbb{C}^{\overrightarrow{E}\times V^{{\sf alt}}}$ of $G$ is the
matrix whose rows range over $(u,v)\in\overrightarrow{E}$, whose columns range
over $(u,i)\in V^{{\sf alt}}$ and whose only non-zero entries are of the form

$\displaystyle{B_{{\sf alt}}}_{(u,v),(u,i)}=\sqrt{{\sf w}_{u}}\mbox{$\langle
u,v|\psi_{u,i}\rangle$},$ $\displaystyle{B_{{\sf
alt}}}_{(u,v),(v,j)}=\sqrt{{\sf w}_{u}}\mbox{$\langle
u,v|\psi_{v,j}\rangle$}.$

By Definition 3.1 we may assume that each $\ket{{\psi}_{u,i}}$ only has real
coefficients and that $\ket{{\psi}_{u,0}}=\ket{\psi_{u}}$. By substituting $B$
with $B_{{\sf alt}}$ in both (18) and (21), we can recover both Kirchhoff’s
Alternative Law and Ohm’s Alternative Law, showing that these are indeed their
natural definitions with respect to perspective of the incidence matrix. Fix
some ordering of the columns of $B$ of the form
$s,(u_{1},i_{1}),\dots,(u_{2},i_{2}),t$ for some $u_{1},u_{2}\in
V\backslash\\{s,t\\}$ such that $(u_{1},i_{1}),(u_{2},i_{2})\in V^{{\sf
alt}}$.

######  Definition 6.7 (Kirchhoff’s Alternative Law (incidence matrix)).

Let $\theta^{\sf alt}$ be any alternative unit $s$-$t$ flow on an electrical
network $G=(V,E,{\sf w})$ with respect to a collection of alternative
neighbourhoods $\Psi_{\star}$. Let $B_{{\sf alt}}$ be the alternative
incidence matrix of $G$. Then $\theta^{\sf alt}$ satisfies

$B_{{\sf alt}}^{T}W\theta^{\sf
alt}=\begin{bmatrix}\sum_{v\in\Gamma(s)}\theta^{\sf alt}_{s,v}\\\
\sum_{v\in\Gamma(u_{1})}\frac{\theta^{\sf alt}_{u_{1},v}}{\sqrt{{\sf
w}_{u_{1},v}}}\sqrt{{\sf w}_{u_{1}}}\mbox{$\langle
u_{1},v|\psi_{u_{1},i_{1}}\rangle$}\\\ \vdots\\\
\sum_{v\in\Gamma(u_{2})}\frac{\theta^{\sf alt}_{u_{2},v}}{\sqrt{{\sf
w}_{u_{2},v}}}\sqrt{{\sf w}_{u_{2}}}\mbox{$\langle
u_{2},v|\psi_{u_{2},i_{2}}\rangle$}\\\ \sum_{v\in\Gamma(t)}\theta^{\sf
alt}_{t,v}\end{bmatrix}=\begin{bmatrix}1\\\ 0\\\ \vdots\\\ 0\\\
-1\end{bmatrix}={\sf e}_{s}-{\sf e}_{t}.$ (28)

Recall from Definition 3.3 that the $s$-$t$ alternative electrical flow is the
flow that minimises ${\cal E}(\theta^{\sf alt})$ for all alternative unit
$s$-$t$ flows $\theta^{\sf alt}$ (if any such flow exists). By applying the
Moore-Penrose inverse of $B_{{\sf alt}}^{T}$ to (28), we prove that the
$s$-$t$ electrical flow is unique and thus well defined:

######  Theorem 6.8.

Let $\theta^{\sf alt}$ be the $s$-$t$ alternative electrical flow on a network
$G=(V,E,{\sf w})$. Let $B_{{\sf alt}}$ be the alternative incidence matrix of
$G$. Then $W\theta^{\sf alt}$ is given by

$W\theta^{\sf alt}=B_{{\sf alt}}^{T+}({\sf e}_{s}-{\sf e}_{t}).$ (29)

Recall the isometry ${\cal V}$ defined in (25). The column of $B_{{\sf alt}}$
indexed by $(u,i)\in V^{{\sf alt}}$ is equal to ${\cal V}^{T}\left(\sqrt{{\sf
w}_{u}}\ket{\psi_{u,i}^{+}}\right)$, meaning that the column space of $B_{{\sf
alt}}$ is equal to ${\cal V}^{T}\left(H^{+{\sf alt}}\right)$. Moreover, the
column space of $B_{{\sf alt}}$ is equal to the column space of $B_{{\sf
alt}}^{T+}$, due to the properties of the Moore-Penrose inverse in (19).
Combined with the fact that the state $\ket{\theta^{\sf alt}}$ is related to
the vector $W\theta^{\sf alt}$ via the equality $\sqrt{{\cal R}_{s,t}^{{\sf
alt}}}\ket{\theta^{\sf alt}}={\cal V}\left(W\theta\right)$, we find that
$\ket{\theta^{\sf alt}}$ is an element of $H^{+{\sf alt}}$. This means that
there exist coefficients ${\sf p}^{\sf alt}_{(u,i)}$ such that

$\begin{split}\ket{\theta^{\sf alt}}=\frac{1}{\sqrt{{{\cal R}^{{\sf
alt}}_{s,t}}}}\sum_{u\in V}\sum_{i=0}^{a_{u}-1}{\sf p}^{\sf
alt}_{(u,i)}\sqrt{{\sf w}_{u}}\ket{\psi_{u,i}^{+}}.\end{split}$ (30)

The notation ${\sf p}^{\sf alt}_{(u,i)}$ seems to hint that these coefficients
are related to the alternative potential vector ${\sf p}^{\sf alt}$. This is
indeed the case: by defining the potential vector ${\sf p}^{\sf alt}$ as

${\sf p}^{\sf alt}_{u,v}:=\frac{(-1)^{\Delta_{u,v}}}{\sqrt{{\sf
w}_{u,v}}}\sum_{i=0}^{a_{u}-1}{\sf p}^{\sf alt}_{(u,i)}\sqrt{{\sf
w}_{u}}\mbox{$\langle u,v|\psi_{u,i}\rangle$},$ (31)

we guarantee that the state $\ket{{\sf p}^{\sf alt}}$ satisfies $\Pi_{\cal
B}\ket{{\sf p}^{\sf alt}}$:

$\begin{split}\ket{{\sf p}^{\sf alt}}&=\sqrt{\frac{2}{{\cal R}(\theta^{\sf
alt})}}\sum_{(u,v)\in\overrightarrow{E}:s\notin(u,v)}\sqrt{{\sf w}_{u,v}}({\sf
p}^{\sf alt}_{u,v}\ket{u,v}-{\sf p}^{\sf alt}_{v,u}\ket{v,u})\\\
&=\sqrt{\frac{2}{{\cal R}^{{\sf alt}}_{s,t}}}\sum_{u\in
V\setminus\\{s\\}}\sum_{v\in\Gamma(u)}\sum_{i=0}^{a_{u}-1}{\sf p}^{\sf
alt}_{(u,i)}\sqrt{{\sf w}_{u}}\mbox{$\langle
u,v|\psi_{u,i}\rangle$}\ket{u,v}\\\ &=\sqrt{\frac{2}{{\cal R}^{{\sf
alt}}_{s,t}}}\sum_{u\in V\setminus\\{s\\}}\sum_{i=0}^{a_{u}-1}{\sf p}^{\sf
alt}_{(u,i)}\sqrt{{\sf w}_{u}}\ket{\psi_{u,i}}.\end{split}$

Due to the coefficients ${\sf p}^{\sf alt}_{(u,i)}$, we can therefore consider
the alternative potential vector ${\sf p}^{\sf alt}$ as a vector in
$\mathbb{C}^{V^{{\sf alt}}}$ with entries ${\sf p}^{\sf alt}_{(u,i)}$ for the
row indexed by $(u,i)\in V^{{\sf alt}}$. By substituting $B$ with $B_{{\sf
alt}}$ in (21) and combining this with (31), we recover Ohm’s Alternative Law:

######  Definition 6.9 (Ohm’s Alternative Law (incidence matrix)).

Let $\theta^{\sf alt}$ be any alternative unit $s$-$t$ flow on an electrical
network $G=(V,E,{\sf w})$ with respect to a collection of alternative
neighbourhoods $\Psi_{\star}$. Let $B_{{\sf alt}}$ be the alternative
incidence matrix of $G$. Then there exists an alternative potential vector
${\sf p}^{\sf alt}$ such that $\Pi_{\cal B}\ket{{\sf p}^{\sf alt}}=\ket{{\sf
p}^{\sf alt}}$ and

$B{\sf p}^{\sf alt}=\begin{bmatrix}\sqrt{{\sf w}_{u_{1},v_{1}}}\left({\sf
p}^{\sf alt}_{u_{1},v_{1}}-{\sf p}^{\sf alt}_{v_{1},u_{1}}\right)\\\ \vdots\\\
\sqrt{{\sf w}_{u_{2},v_{2}}}\left({\sf p}^{\sf alt}_{u_{2},v_{2}}-{\sf p}^{\sf
alt}_{v_{2},u_{2}}\right)\end{bmatrix}=\begin{bmatrix}\frac{\theta_{u_{1},v_{1}}}{\sqrt{{\sf
w}_{u_{1},v_{1}}}}\\\ \vdots\\\ \frac{\theta_{u_{2},v_{2}}}{\sqrt{{\sf
w}_{u_{2},v_{2}}}}\end{bmatrix}=W\theta^{\sf alt}.$ (32)

Just like with the potential vector ${\sf p}$, we may assume that the
alternative potential vector ${\sf p}^{\sf alt}$ satisfying Ohm’s Alternative
Law also satisfies ${\sf p}^{\sf alt}_{s}={\cal R}_{s,t}^{{\sf alt}}$ and
${\sf p}^{\sf alt}_{t}=0$

######  Theorem 6.10.

Let $\theta^{\sf alt}$ be the $s$-$t$ alternative electrical flow on an
electrical network $G=(V,E,{\sf w})$ with respect to a collection of
alternative neighbourhoods $\Psi_{\star}$. Let $B_{{\sf alt}}$ be the
alternative incidence matrix of $G$. Then there exists an alternative
potential vector ${\sf p}^{\sf alt}$ satisfying Ohm’s Alternative Law such
that ${\sf p}^{\sf alt}_{s}={\cal R}_{s,t}^{{\sf alt}}$ and ${\sf p}^{\sf
alt}_{t}=0$.

###### Proof.

We apply the same trick as in (23), so we remove the last column of $B_{{\sf
alt}}$ and last row of ${\sf p}^{\sf alt}$ to obtain $\overline{B_{{\sf
alt}}}$ and $\overline{{\sf p}^{\sf alt}}$, forcing ${\sf p}^{\sf alt}_{t}=0$
for the solution satisfying (32):

${\sf p}^{\sf alt}=\begin{bmatrix}\overline{{\sf p}^{\sf alt}}\\\
0\end{bmatrix}=\begin{bmatrix}\overline{B_{{\sf alt}}}^{+}W\theta^{\sf alt}\\\
0\end{bmatrix}.$ (33)

By left-multiplying both sides of (29) with $(W{\theta^{\sf alt}})^{T}$ we
obtain together with (32) that

${\cal R}_{s,t}^{{\sf alt}}=\left\|W\theta^{\sf
alt}\right\|^{2}={(W\theta^{\sf alt})}^{T}B^{T+}({\sf e}_{s}-{\sf
e}_{t})={{\sf p}^{\sf alt}}^{T}({\sf e}_{s}-{\sf e}_{t})={\sf p}^{\sf
alt}_{s}-{\sf p}^{\sf alt}_{t}={\sf p}^{\sf alt}_{s}.$ (34)

∎

Due to Theorem 6.10, we may now apply Lemma 2.7 with the parameters
$\ket{\psi}=\ket{\psi_{s}^{+}}$, $\ket{\varphi}=\ket{\theta^{\sf alt}}$,
$\ket{\phi}=-\frac{1}{\sqrt{{\cal R}_{s,t}^{{\sf alt}}{\sf w}_{s}}}\ket{{\sf
p}^{\sf alt}}$ and $p=\frac{1}{{\cal R}_{s,t}^{{\sf alt}}{\sf w}_{s}}$,
proving the following generalisation of Corollary 2.8:

######  Theorem 6.11.

Let $\Psi_{\star}$ be a collection of alternative neighbourhoods on a network
$G=(V,E,{\sf w})$ and let $U_{{\cal A}{\cal B}^{\sf alt}}$ be the quantum walk
operator with respect to $\Psi_{\star}$ as defined in (8). Then by performing
phase estimation on the initial state $\ket{\psi_{s}^{+}}$ with the operator
$U_{{\cal A}{\cal B}^{\sf alt}}$ and precision
$O\left(\frac{\epsilon^{2}}{{\cal R}_{s,t}^{{\sf alt}}{\sf w}_{s}\left\|{\sf
p}^{\sf alt}\right\|}\right)$, the phase estimation algorithm outputs “$0$”
with probability $\Theta\left(\frac{1}{{\cal R}_{s,t}^{{\sf alt}}{\sf
w}_{s}}\right)$, leaving a state $\ket{\theta^{\prime}}$ satisfying

$\frac{1}{2}\left\|\ket{\theta^{\prime}}\bra{\theta^{\prime}}-\ket{\theta^{\sf
alt}}\bra{\theta^{\sf alt}}\right\|_{1}\leq\epsilon.$

###  6.3 Examples

We will now show how these results apply to the examples Figure 1 and Figure 2
from section Section 3.4, which we have restated here in Figure 10 and Figure
11. Consider the graph $G$, consisting of the vertex set $V=\\{s,x,y,t\\}$ and
directed edge set $\overrightarrow{E}=\\{(s,x),(x,y),(x,t),(y,t)\\}$, where
each edge $(u,v)\in\overrightarrow{E}$ has weight ${\sf w}_{u,v}=1/4$, except
for the edge $(s,x)$, which has weight ${\sf w}_{s,x}=1$. This graph is
visualised in Figure 10. These directions and weight assignments give rise to
the following star states for each of our $4$ vertices:

$\displaystyle\ket{\psi_{s}}=\ket{s,x},$
$\displaystyle\ket{\psi_{x}}=\sqrt{\frac{2}{3}}\left(-\ket{x,s}+\frac{1}{2}\ket{x,y}+\frac{1}{2}\ket{x,t}\right),$
$\displaystyle\ket{\psi_{y}}=\sqrt{2}\left(-\frac{1}{2}\ket{y,x}+\frac{1}{2}\ket{y,t}\right),$
$\displaystyle\ket{\psi_{t}}=\sqrt{2}\left(-\frac{1}{2}\ket{t,x}-\frac{1}{2}\ket{t,y}\right).$

By ordering the directed edges as $(s,x),(x,y),(x,t),(y,t)$ and the vertices
as $s,x,y,t$, we have that the incidence matrix $B$ of $G$ and the Moore-
Penrose inverse $B^{T+}$ of its transpose are equal to

$\displaystyle B=\begin{bmatrix}1&-1&0&0\\\ 0&\frac{1}{2}&-\frac{1}{2}&0\\\