# Recovering the original simplicity: succinct and deterministic quantum
algorithm for the welded tree problem

Guanzhong Li Institute of Quantum Computing and Computer Theory, School of
Computer Science and Engineering, Sun Yat-sen University, Guangzhou, China.
Supported by the National Natural Science Foundation of China Grant No.
62272492, and the Guangdong Basic and Applied Basic Research Foundation Grant
No. 2020B1515020050. Authors sorted alphabetically. Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Lvzhou Li11footnotemark: 1 Jingquan Luo11footnotemark: 1

###### Abstract

This work revisits quantum algorithms for the well-known welded tree problem,
proposing a very succinct quantum algorithm based on the simplest coined
quantum walks. It simply iterates the naturally defined coined quantum walk
operator for a predetermined time and finally measure, where the predetermined
time can be efficiently computed on classical computers. Then, the algorithm
returns the correct answer deterministically, and achieves exponential
speedups over any classical algorithm. The significance of the results may be
seen as follows. (i) Our algorithm is rather simple compared with the one in
(Jeffery and Zur, STOC’2023), which not only breaks the stereotype that coined
quantum walks can only achieve quadratic speedups over classical algorithms,
but also demonstrates the power of the simplest quantum walk model. (ii) Our
algorithm theoretically achieves zero-error, which is not possible with
existing methods. Thus, it becomes one of the few examples that exhibit
exponential separation between deterministic (exact) quantum and randomized
query complexities, which may also change people’s perception that since
quantum mechanics is inherently probabilistic, it impossible to have a
deterministic quantum algorithm with exponential speedups for the weled tree
problem.

##  1 Introduction

A primary goal of the field of quantum computing is to design quantum
algorithms that can solve problems faster than classical algorithms. Quantum
walks have developed into a fundamental tool for algorithmic design. Since
Aharonov et al. [1] first coined the term “quantum walks” thirty years ago,
quantum walks have become a major research subject both in theory and in
experiment [2, 3, 4, 5]. There are two kinds of quantum walks: discrete time
quantum walks (DTQW) and continuous time quantum walks (CTQW). Whereas CTQW
evolve a Hamiltonian $H$ (related to the graph under consideration) for any
time $t$, i.e. simulating $e^{iHt}$, DTQW can only evolve the system for
discrete time steps, i.e. applying $U_{\mathrm{walk}}^{h}$ to the initial
state for some integer $h$ and unitary operator $U_{\mathrm{walk}}$.

DTQW can be further divided into many different frameworks. The earliest and
simplest is the coined quantum walks [6, 7] consisting of a coin operator $C$
(usually the Grover diffusion) and a shift operator $S$ (usually the flip-flop
shift, i.e. SWAP operator). Later, Szegedy proposed a quantum walk framework
[8] from the perspective of Markov chains. In this direction, a series of
variant frameworks for spatial search have been developed: the MNRS framework
[9], the interpolated walk [10], the electric network framework [11] and its
finding version [12]. Quantum algorithms based on these frameworks have
provided only at most a quadratic speedup when comparing to the best classical
algorithm. Typical examples include quantum algorithms for the element
distinctness problem [13], matrix product verification [14], triangle finding
[15], group commutativity [16], and so on.

In sharp contrast, exponential algorithmic speedups can be obtained based on
CTQW for the welded tree problem [17], which makes the welded tree problem of
great interest, as it is one of the few problems for which quantum walk-based
algorithms are exponentially faster than classical algorithms. Note that
earlier studies have shown that quantum walks can solve problems exponentially
faster than classical walks [18, 19], but there exist classical efficient
algorithms which are not based on a random walk for those problems [17].

Recently, Jeffery and Zur [20] proposed a new DTQW framework—multidimensional
quantum walks (an extension of the electric network framework), and then
presented a quantum algorithm based on it to solve the welded tree problem,
which achieves exponential speedups over classical algorithms. The pursuit of
exponential algorithmic speedups based on DTQW is one of the reasons for
proposing the framework of multidimensional quantum walks. Actually, Jeffery
and Zur [20] claimed that the major drawback of the existing DTQW frameworks
is that they can achieve at most a quadratic speedup over the best classical
algorithm, but this drawback does not hold for the multidimensional quantum
walk framework 111Ref. [20] claimed “While quantum walk frameworks make it
extremely easy to design quantum algorithms, even without an in-depth
knowledge of quantum computing, as evidenced by their wide application across
domains, the major drawback is that they can achieve at most a quadratic
speedup over the best classical algorithm. This is because a quantum walk
search algorithm essentially takes a classical random walk algorithm, and
produces a quantum algorithm that is up to quadratically better. This drawback
does not hold for the multidimensional quantum walk framework”..

In this work, we revisit quantum algorithms for the welded tree problem,
proposing a quite succinct quantum algorithm based purely on the simplest
coined quantum walks, which not only maintains the exponential speedup, but
also achieves zero-error theoretically. Thus, our work demonstrates the power
of the simplest quantum walk model, and verifies that a good quantum algorithm
does not necessarily resort to complex techniques.

###  1.1 Coined Quantum Walk

For a graph $G=(V,E)$ and $u\in V$, $deg(u)=\\{v:(u,v)\in E\\}$ denotes the
set of neighbours of $u$, and the degree of $u$ is denoted as
$d_{u}=|deg(u)|$. A coined quantum walk on $G=(V,E)$ is defined on the state
space $\mathbb{H}^{N^{2}}=\mathrm{span}\\{\ket{uv},u,v\in V\\}$ with $N=|V|$.
The evolution operator of the coined quantum walk at each step is
$U_{\mathrm{walk}}=SC$. $C$, the coin operator, is defined by $C=\sum_{u\in
V}\ket{u}\bra{u}\otimes C_{u},$ where $C_{u}$ is typically the Grover
diffusion coin operator $C_{u}=2\ket{s_{u}}\bra{s_{u}}-I,$ with
$\ket{s_{u}}=\frac{1}{\sqrt{d_{u}}}\sum_{v\in deg(u)}\ket{v}.$ $S$, the flip-
flop shift operator, is defined as $S\ket{uv}=\ket{vu},$ where
$\ket{uv}=\ket{u}\otimes\ket{v}$ denotes a particle at vertex $u$ pointing
towards vertex $v$. Given the initial state $\ket{\Psi_{0}}$ , the walker’s
state after $h$ steps is $\ket{\Psi_{h}}=U_{\mathrm{walk}}^{h}\ket{\Psi_{0}}$.

###  1.2 The welded tree problem

The welded tree problem was proposed in [17] as a black-box (oracle) problem
to show that a quantum algorithm can be exponentially faster than any
classical algorithm with the help of CTQW. To achieve exponential algorithmic
speedup, the graph to be traversed is carefully designed: the welded tree
$G_{n}$ consists of two horizontal-positioned full binary trees of height $n$
with their $2^{n}$ leaves in the middle. The root of the left tree is the
entrance denoted by $s$, and the root of the right tree is the exit denoted by
$t$. The leaves in the middle are connected by a random cycle that alternates
between the leaves of the two trees instead of identifying them in the direct
way. (See the dashed line in Fig. 1) This makes the leaves have degree $3$
instead of $2$, indistinguishable from all the other internal nodes.

The number of vertices in $G_{n}$ is $|V(G_{n})|=2(2^{n+1}-1)$, thus
$(n+2)$-bit string is enough to encode all the vertices. However, to ensure
the classical hardness of the problem [17, Lemma 7], each vertex $u\in
V(G_{n})$ is randomly assigned a distinct $2n$-bit string as its name, except
that the entrance is fixed as $s\equiv 0^{2n}$. We retain $\perp\equiv 1^{2n}$
as the special symbol, so that the graph $G_{n}$ can be specified by an
$2^{2n}\times 3$ adjacency list $\Gamma$ (See the table in Fig. 1). Note that
when $u\in\\{0,1\\}^{2n}$ is the root $s$ or $t$, exactly one of
$\\{\Gamma(u,i):i=1,2,3\\}$ is $\perp$.

Figure 1:  A welded tree $G_{n}$ for $n=2$ and its $2^{2n}\times 3$ adjacency
list $\Gamma$. $s=0$ is the entrance and $t=9=(1001)_{2}$ is the exit. The
dashed lines in the middle is the random cycle connecting the two trees.

The adjacency list $\Gamma$ is provided in the form of an oracle (black box)
$O$, so that the only way to know about $\Gamma$ is to query $O$ with a name
$u\in\\{0,1\\}^{2n}$, and the oracle will output all the items in row $u$ of
$\Gamma$:

(1.1) $O(u)=\\{\Gamma(u,i):i=1,2,3\\}.$

We are concerned with the number of times an algorithm queries the oracle $O$
(a.k.a query complexity) to find the exit name $t$. In the quantum model, the
effect of $O$ is

(1.2)
$O\ket{u}\bigotimes_{i=1}^{3}\ket{v_{i}}=\ket{u}\bigotimes_{i=1}^{3}\ket{v_{i}\oplus\Gamma(u,i)},$

where $u,v_{i}$ are all $2n$-bit string and $\oplus$ denotes bit-wise modulo
$2$ addition. The welded tree problem can now be formally stated as Definition
1.1.

######  Definition 1.1 (the welded tree problem)

Given the entrance name $s=0^{2n}$, find the exit name $t$ of the welded tree
$G_{n}$ with as few queries as possible to its adjacency list oracle $O$.

Since the degree of each vertex in $G_{n}$ is no more than $3$, even if the
quantum oracle $O$ is provided in its weaker form such that it returns only
one adjacent vertex $\Gamma(u,i)$ when queried with $(u,i)$, as is the case in
[17], the influence on the query complexity is at most by a constant factor
and can be neglected.

###  1.3 Our contribution

In this paper, we propose a rather succinct quantum algorithm (Algorithm 1 in
Section 4) to solve the welded tree problem, which is simply to walk on the
welded tree with the operator $U_{\mathrm{walk}}=SC$ from an initial state
$\ket{\Psi_{s}}$ that is constructed from the entrance vertex $s$. We will
show that the coin operator $C$ can be implemented with $4$ queries to the
given oracle $O$ and the shift operator $S$ has no queries to $O$. Also, we
will prove that after $T\in O(n\log n)$ steps which can be predetermined
efficiently on classical computers, the walker reaches the exit vertex $t$
with probability at least $\Omega(\frac{1}{n})$. More exactly, there is
$|\bra{\Psi_{t}}U_{\mathrm{walk}}^{T}\ket{\Psi_{s}}|^{2}>c\frac{1}{n}$ for
constant $c$, where $\ket{\Psi_{t}}$ encodes the exit $t$. Therefore, the
query complexity of the algorithm is $O(n^{2}\log n)$. Furthermore, the
algorithm can be improved to a deterministic one with $O(n^{1.5}\log n)$
queries by using deterministic (or exact) amplitude amplification as shown by
Algorithm 2 in Section 5. In addition, we conjecture that the actual
complexity of our algorithm is $O(n^{4/3})$ (Conjecture 6.1 in Section 6),
which is strongly supported by numerical simulation for $n=6,\cdots,500$, with
the strict proof left as an open problem.

The significance of our results, in our opinion, lies at least in the
following two aspects:

  1. (1)

Our algorithm is rather succinct compared with the one in [20], which not only
changes the stereotype that coined quantum walks can only achieve quadratic
speedups over classical algorithms, but also demonstrates the power of the
simplest quantum walk models.

  2. (2)

Our algorithm can be made zero-error theoretically, whereas existing methods
cannot (see Table 1). Thus, it becomes one of the few examples that exhibits
exponential separation between deterministic (exact) quantum and randomized
query complexities, and may have potential applications in graph property
testing problems [21, 22]. Previous examples of this kind of separation
include Simon’s problem [23] and its generalization [24]. This deterministic
algorithm may also change people’s perception that since quantum mechanics is
inherently probabilistic, deterministic quantum algorithms with exponential
speedups for the welded tree problem are out of the question.

###  1.4 Technical overview

Despite the succinctness of our algorithms, there are some non-trivial steps
in designing and analyzing it, without losing technical challenges:

  1. (1)

Constructing the operator $U_{\mathrm{walk}}=SC$ from the given oracle $O$
(Lemma 2.1). As the flip-flop shift operator $S$ requires no oracle queries,
the key is to construct the coin operator $C$. Our implementation of $C$ is
inspired by [20], but it is much simpler as alternative neighbourhoods
technique is not needed in this paper.

  2. (2)

Reducing the $\Theta(2^{n})$-dimensional state space to a $(4n+2)$-dimensional
invariant subspace (Lemma 3.1). In this subspace, the operator
$U_{\mathrm{walk}}=SC$ takes the form of a $(4n+2)$-dimensional square matrix
$M_{U}=M_{S}M_{C}$, and the initial state corresponds to the first base vector
$\ket{0}$ (whose transpose is $[1,0,\cdots,0]$) and the target state
corresponds to the last base vector $\ket{4n+1}$ (whose transpose is
$[0,\cdots,0,1]$. The reduction is done by grouping the vertices according to
their layers, which is inspired by [17], but since our coined quantum walk is
carried out on the edges of the graph, there is some nontrivial difference.

  3. (3)

Analyzing the success probability, which is probably the most technical step.
This is shown in two steps:

    1. (i)

Obtaining the spectral decomposition of matrix
$M_{U}=\sum_{j}e^{i\varphi_{j}}\ket{E_{j}}\bra{E_{j}}$ (Lemma 4.1). This is
inspired by a spectral decomposition result in [25], but we improve it with an
observation concerning Chebyshev polynomial of the second kind. The
improvements make the equation that the eigenvalues need to satisfy become
clear, explicit and easy to analyze.

    2. (ii)

Instead of directly considering a fixed iteration number $t$ (the difficulty
of this approach is noted in Remark 4.3), we will prove that the average
success probability $\mathbb{E}|\bra{4n+1}M_{U}^{t}\ket{0}|^{2}$ has a
$\Omega(\frac{1}{n})$ lower bound when $t$ is chosen according to a specific
distribution over $\\{0,1,\cdots,O(n\log n)\\}$. A key component of the proof
is the helper Lemma 4.2 (inspired by [26, Lemma 3]), which relates the lower
bound of $\mathbb{E}|\bra{4n+1}M_{U}^{t}\ket{0}|^{2}$ with, roughly speaking,
the first and last component of eigenvector $\ket{E_{j}}$ and the
characteristic of eigenvalue angles $\varphi_{j}$. Thus, the spectral
decomposition $M_{U}=\sum_{j}e^{i\varphi_{j}}\ket{E_{j}}\bra{E_{j}}$ in step
(i) is of crucial importance.

###  1.5 Related work

The original algorithm proposed by Childs et al. [17] is based on CTQW and
they prove that the CTQW will find the exit with probability $\Omega(1/n)$ at
a time of $O(n^{4})$. They also showed that the CTQW $e^{iHt}$ can be
simulated for time $t$ with $O(t^{2})$ oracle queries. Thus combined with
fixed-point amplitude amplification [27, 28], the overall query complexity is
$O(n^{8.5})$, where $n^{8.5}=n^{1/2}\cdot n^{4\times 2}$. Lately it was
improved to $O(n^{2.5}\text{log}^{2}n)$ [26]. In contrast, any classical
algorithm requires $2^{\Omega(n)}$ queries [17, 29]. It was claimed in [30]
that there exist exponential algorithmic speedups based on DTQW for the welded
tree problem, but no explicit algorithm was given there. Recently, a quantum
algorithm based on the multidimensional quantum walk framework was proposed by
Jeffery and Zur [20], solving the problem with $O(n)$ queries and $O(n^{2})$
time complexity. The framework uses phase estimation [31] to gain one-bit
information about the exit name, and then uses the Bernstein-Vazirani
algorithm [32] to obtain the whole name. We summarize previous results on the
welded tree problem in Table 1.

algorithm type | queries | succinct? | deterministic?
---|---|---|---
classical [17, 29] | $2^{\Omega(n)}$ |  | *
CTQW [17] | $O(n^{8.5})$ | Yes | No
CTQW [26] | $O(n^{2.5}\text{log}^{2}n)$ | Yes | No
DTQW [20] | $O(n)$ | No | No
DTQW, this work | $O(n^{1.5}\log n)$ | Yes | Yes
Table 1: Summary of the query complexity of different algorithms for the
welded tree problem. The star notation * in the first line stresses that the
lower bound holds for any classical randomized algorithm and thus also holds
for deterministic algorithm.

Compared to the recent quantum algorithm based on multidimensional quantum
walks [20], our algorithm has the following advantages:

  1. (1)

Succinct algorithmic procedure. Our algorithm (see Algorithm 1) simply
iterates the coined quantum walk operator $U_{\mathrm{walk}}$ for a
predetermined time $T$ and then measure the first register to obtain the
result. In contrast, [20] has to combine with Bernstein-Vazirani algorithm
[32] in order to learn the whole name, because their multidimensional quantum
walk framework using phase estimation can only obtain one-bit information
about the exit name (which corresponds to the inner-product oracle in BV
algorithm).

  2. (2)

Simpler implementation of the quantum walk operator. Our implementation of
$U_{\mathrm{walk}}$ is simpler as the coin operator $C$ can be easily
implemented with two oracle queries and the shift operator $S$ is merely $2n$
parallel SWAP gates. In contrast, it was said in [20, Remark 4.8] that one has
to carefully assign different weights to the graph’s edges in order to balance
between the positive and negative witness size, so that the polynomial query
complexity is possible. The weight assigning scheme makes the implementation
of the quantum walk operator much more complicated: (i) The alternative
neighbourhoods technique has to be used since the oracle does not provide
information about which neighbouring vertex is closer to the root. The
technique works as follows: instead of reflecting around the uniform
superposition of neighbours (which is what our coin operator $C$ does), one
has to reflect around a subspace spanned by some easily preparable states.
This makes the operator’s implementation more complicated. (ii) Due to the
specific weight assigning scheme, one has to handle separately the cases when
$n$ is odd or even, and determine the parity of the layers at which each
vertex lies, and also assign different weight $w_{0}=w_{M}=1/(cn)$ to the
edges $(s,\perp),(t,\perp)$.

  3. (3)

Certainty of success theoretically. Since the multidimensional framework [20]
uses phase estimation which is intrinsically randomized, it cannot be made
deterministic, but our simple coined quantum walk algorithm can be made zero-
error theoretically (Algorithm 2).

Compared to the algorithms based on CTQW [17, 26], our algorithms has a better
query complexity, and can be adapted to succeed with certainty. On the
contrary, the implementation of the CTQW operator $e^{iHt}$ from oracle $O$
involves the use of linear combination tool in Hamiltonian simulation, thus
error is introduced inevitably. Also, choosing the quantum walk time $t$
according to some distribution leads to additional randomness.

###  1.6 Paper organization

The rest of the paper is organized as follows. In Section 2 we define the
coined quantum walk operator $U_{\mathrm{walk}}$ and give a detailed
implementation of $U_{\mathrm{walk}}$ from the quantum oracle $O$. In Section
3 we reduce the full state space to a $(4n+2)$-dimensional invariant subspace
and deduce the reduced matrix $M_{U}$, which lays an important first step for
the correctness and complexity analysis of our algorithms. In Section 4 we
present a succinct algorithm (Algorithm 1) and prove a rigorous query upper
bound. In Section 5 we present the theoretically zero-error algorithm
(Algorithm 2). Numerical simulation is shown in Section 6 indicating that the
actual performance of our algorithms is better. We conclude this paper in
Section 7.

##  2 Implementing the coined quantum walk operator

As the adjacency list $\Gamma$ of the welded tree $G_{n}$ defined in Section
1.2 is unknown and can only be accessed through the oracle $O$, the
implementation of the coined quantum walk operator $U_{\mathrm{walk}}$ on
$G_{n}$ needs some careful design as presented in this section.

First, the state space of the coined quantum walk is:

(2.3)
$\mathcal{H}=\text{span}\\{\ket{u}_{r_{1}}\ket{v}_{r_{2}}:u,v\in\\{0,1\\}^{2n}\\},$

which is the state space of $4n$ qubits. The subscript $r_{i}$ of the two
registers will serve later for the convenience of describing the construction
of

(2.4) $\displaystyle U_{\mathrm{walk}}=SC.$

Let $\varphi(u)=\frac{1}{\sqrt{3}}\sum_{i=1}^{3}\ket{\Gamma(u,i)}$ be the
uniform superposition of the adjacent vertices of $u$ and let
$C_{u}=2\ket{\varphi(u)}\bra{\varphi(u)}-I$. Then the coin operator $C$ is
given by

(2.5) $\displaystyle C$
$\displaystyle=\sum_{u\in\\{0,1\\}^{2n}}\ket{u}\bra{u}\otimes C_{u}$ (2.6)
$\displaystyle=2\sum_{u\in\\{0,1\\}^{2n}}\ket{u,\varphi(u)}\bra{u,\varphi(u)}-I.$

Note that we allow the sum to include $u\notin V(G_{n})$, so that the
implementation of $\text{Ref}_{\perp}$ (see Eq. (2.12)) does not need to check
whether $u$ is indeed a vertex in $G_{n}$ or not. When $r\in\\{s,t\\}$ and
$\Gamma(r,i_{1})=\perp$, we let

(2.7)
$\varphi(r)=\frac{1}{\sqrt{2}}(\ket{\Gamma(r,i_{2})}+\ket{\Gamma(r,i_{3})}),$

reflecting the fact that $r\to\perp$ is not an edge in the graph.

The shift operator $S$ is the SWAP operator on the vertex pair $\\{u,v\\}$:

(2.8) $S=\sum_{u,v\in\\{0,1\\}^{2n}}\ket{v,u}\bra{u,v},$

which is actually a reflection operator as well:

(2.9) $S=2\sum_{u\leq v}\ket{\psi_{u,v}}\bra{\psi_{u,v}}-I,$

where

(2.10)
$\ket{\psi_{u,v}}=\begin{cases}\frac{\ket{u,v}+\ket{v,u}}{\sqrt{2}},&u<v;\\\
\ket{u,v},&u=v.\end{cases}$

###### Lemma 2.1

The coined quantum walk operator $U_{\mathrm{walk}}=SC$ can be implemented
with $2$ oracle queries and $O(n)$ elementary operations.

  * Proof.

First, the implementation of $S$ is quite simple, just apply the SWAP gate to
the corresponding $2n$ pairs of qubits between registers $r_{1}$ and $r_{2}$,
which takes $O(n)$ basic operations. The implementation of $C$ is more
complicated and requires $2$ oracle queries as shown below.

We implement $C$ in two steps: first to construct a unitary operator
$U_{\varphi}$ that has the following effect

(2.11) $U_{\varphi}:\ket{u,\perp}\mapsto\ket{u,\varphi(u)},$

and then to construct the reflection

(2.12)
$\text{Ref}_{\perp}=2\sum_{u\in\\{0,1\\}^{2n}}\ket{u,\perp}\bra{u,\perp}-I=I_{r_{1}}\otimes(2\ket{\perp}\bra{\perp}-I_{r_{2}}).$

Thus, we have

(2.13) $\displaystyle C=U_{\varphi}\,\text{Ref}_{\perp}U_{\varphi}^{\dagger},$

where $U_{\varphi}^{\dagger}$ can be implemented by executing the conjugate of
quantum gates composing $U_{\varphi}$ in reverse order.

As global phase shift can be neglected, we will implement
$-\text{Ref}_{\perp}$. Observe that $-\text{Ref}_{\perp}$ simply adds a
relative phase shift of $(-1)$ to $\ket{v}_{r_{2}}$ when $v=\perp=1^{2n}$.
Thus, using phase kick-back effect, $-\text{Ref}_{\perp}$ can be easily
constructed by flipping an auxiliary qubit register $\ket{-}$ conditioned on
all the $2n$ qubits in register $r_{2}$ being in state $\ket{1}$ (i.e. apply a
$\text{C}^{2n}-\text{NOT}$ gate, which decomposes to $O(n)$ basic gates).

The implementation of $U_{\varphi}$ requires $2$ oracle queries and $O(n)$
basic operations, which is a bit lengthy due to the special handling of
$\varphi(r)$ (Eq. (2.7)) and is thus deferred to Appendix A.

As can be seen form the italics, the implementation of $U_{\mathrm{walk}}$
takes $O(n)$ basic operations in total.

###### Remark 2.1

If we enable the oracle to return all the neighbours coherently, i.e.
$O:\ket{u,\perp}\mapsto\ket{u,\varphi(u)}$, which is a common assumption in
the Markov chain based DTQW framework, then the implementation of
$U_{\varphi}$ shown above is unnecessary. But if this is the case, we will
need an additional oracle to check if $u$ is the exit.

The initial state of the coined quantum walk is

(2.14)
$\ket{s,\varphi(s)}=\frac{1}{\sqrt{2}}(\ket{\Gamma(s,i_{2})}+\ket{\Gamma(s,i_{3})}),$

which can be obtained with $2$ oracle queries from $\ket{s,\perp}$ similar to
step 4 in Appendix A. We denote this state preparation unitary by

(2.15) $U_{p}:\ket{s,\perp}\mapsto\ket{s,\varphi(s)}.$

##  3 Reducing to the low-dimensional invariant subspace

In this section, we will determine the $(4n+2)$-dimensional invariant subspace
$\mathcal{H}_{0}$ of the coined quantum walk operator $U_{\mathrm{walk}}$
based on layers of vertices in $G_{n}$, so that the amplitude on the target
state $\ket{t,\varphi(t)}$ after applying $U_{\mathrm{walk}}^{T}$ to the
initial state $\ket{s,\varphi(s)}$ can be calculated exactly when $n$ is
fixed, regardless of the vertices’ random naming or the random cycle in the
middle of $G_{n}$. This lays an important first step for the correctness and
complexity analysis of our algorithms.

Speciffically, we have the following lemma.

###### Lemma 3.1

The coined quantum walk operator $U_{\mathrm{walk}}$ for the welded tree
$G_{n}$ has a $(4n+2)$-dimensional invariant subspace

(3.16)
$\mathcal{H}_{0}=\mathrm{span}\\{\ket{0,R},\ket{1,L},\ket{1,R},\cdots,\ket{2n,L},\ket{2n,R},\ket{2n+1,L}\\},$

where $\ket{0,R}=\ket{s,\varphi(s)}$ is the initial state,
$\ket{2n+1,L}=\ket{t,\varphi(t)}$ is the target state, and the other sates
$\ket{k,L},\ket{k,R}$ are defined respectively in Eqs. (3.17) (3.18) for
$k=1\sim n$ in the left tree, and similarly for $k=(n+1)\sim 2n$ in the right
tree. In this basis, the coined quantum walk operator $U_{\mathrm{walk}}$ can
be represented by a $(4n+2)$-dimensional square matrix $M_{U}=M_{S}\cdot
M_{C}$, where $M_{C}$ and $M_{S}$ are shown in Eqs. (3.22), (3.24)
respectively.

  * Proof.

The welded tree $G_{n}$ has $2(n+1)$ layers of vertices, and we denote by
$V_{k}$ the set of vertices in the $k$-th layer. Thus in the left tree,
$|V_{k}|=2^{k}$ for $k\in\\{0,1,\cdots,n\\}$; and in the right tree,
$|V_{n+k}|=2^{n+1-k}$ for $k\in\\{1,2,\cdots,n+1\\}$. The two basis states
$\ket{k,L},\ket{k,R}$ with $k\in\\{1,\cdots,n\\}$ of $\mathcal{H}_{0}$ are
related to $V_{k}$ in the left tree, and are defined as the superpositions of
the directed edges pointing to the root and to the random cycle, respectively:

(3.17) $\ket{k,L}:=\frac{1}{\sqrt{2^{k}}}\sum_{u\in
V_{k}}\ket{u,\Gamma(u,i_{1})}$

where $\Gamma(u,i_{1})$ is the adjacent vertex of $u$ closest to the root $s$,
and

(3.18) $\ket{k,R}:=\frac{1}{\sqrt{2^{k}}}\sum_{u\in
V_{k}}\frac{1}{\sqrt{2}}\big{(}\ket{u,\Gamma(u,i_{2})}+\ket{\Gamma(u,i_{3})}\big{)}.$

It’s easy to see that they are orthogonal, since the composing computational
basis states represent distinct directed edges in the welded tree graph. The
two basis states $\ket{n+k,L},\ket{n+k,R}$ with $k\in\\{1,\cdots,n\\}$ related
to $V_{n+k}$ in the right tree are defined similarly. Note that
$\ket{0,R}:=\ket{s,\varphi(s)}$ is the initial state and
$\ket{2n+1,L}:=\ket{t,\varphi(t)}$ is the target state. Note also that there
is no $\ket{0,R}$ or $\ket{2n+1,L}$. A diagram of the $4n+4=12$ basis states
of $\mathcal{H}_{0}$ when $n=2$ is shown in Fig. 2.

Figure 2:  Diagram of the basis states of the reduced coined quantum walk
subspace $\mathcal{H}_{0}$ when $n=2$. The box with number inside represents
the vertex set $V_{k}$ of the $k$-th layer. The solid blue arrows represent
basis states $\ket{k,L},\ket{k,R}$ related to $V_{k}$ with
$k\in\\{1,\cdots,n\\}$ in the left tree, and the black hollow arrows represent
basis states $\ket{n+k,L},\ket{n+k,R}$ related to $V_{n+k}$ with
$k\in\\{1,2,\cdots,n\\}$ in the right tree. The state
$\ket{0,R}:=\ket{s,\varphi(s)}$ and $\ket{2n+1,L}:=\ket{t,\varphi(t)}$ are the
initial and target states respectively.

Observe that

(3.19)
$\ket{u,\varphi(u)}=\sqrt{\frac{1}{3}}\ket{u,\Gamma(u,i_{1})}+\sqrt{\frac{2}{3}}\frac{1}{\sqrt{2}}\Big{(}\ket{u,\Gamma(u,i_{2})}+\ket{\Gamma(u,i_{3})}\Big{)}.$

Thus by the definition of the coin operator $C$ (Eq. (2.6)) and linearity, the
$2$-dimensional subspace spanned by $\\{\ket{k,L},\ket{k,R}\\}$ is invariant
under $C$, and the matrix expression of $C$ in this basis is

(3.20) $R_{A}:=2\begin{bmatrix}\sqrt{\frac{1}{3}}\\\
\sqrt{\frac{2}{3}}\end{bmatrix}\cdot[\sqrt{\frac{1}{3}},\sqrt{\frac{2}{3}}]-I=\begin{bmatrix}-\frac{1}{3}&\frac{2\sqrt{2}}{3}\\\
\frac{2\sqrt{2}}{3}&\frac{1}{3}\end{bmatrix}.$

Similarly, the matrix expression of $C$ in the basis
$\\{\ket{n+k,L},\ket{n+k,R}\\}$ related to $V_{n+k}$ in the right tree is

(3.21) $R_{A}^{\prime}:=2\begin{bmatrix}\sqrt{\frac{2}{3}}\\\
\sqrt{\frac{1}{3}}\end{bmatrix}\cdot[\sqrt{\frac{2}{3}},\sqrt{\frac{1}{3}}]-I=\begin{bmatrix}\frac{1}{3}&\frac{2\sqrt{2}}{3}\\\
\frac{2\sqrt{2}}{3}&-\frac{1}{3}\end{bmatrix}.$

Note that $\ket{0,R}$ and $\ket{2n+1,L}$ are invariant under $C$ by Eq. (2.7).
Thus the matrix expression of $C$ in the basis
$\left\\{\ket{0,R},\ket{1,L},\ket{1,R},\cdots,\ket{2n,L},\ket{2n,R},\ket{2n+1,L}\right\\}$
is

(3.22)
$M_{C}:=\text{diag}(1,\underbrace{R_{A},\cdots,R_{A}}_{n},\underbrace{R_{A}^{\prime},\cdots,R_{A}^{\prime}}_{n},1).$

Note that $\ket{k,R}$ and $\ket{k+1,L}$ with $k\in\\{0,\cdots,2n\\}$ are equal
superpositions of basis states in $\\{\ket{u,v}:u\in V_{k},v\in V_{k+1}\\}$
and $\\{\ket{v,u}:u\in V_{k},v\in V_{k+1}\\}$ respectively. Therefore, $S$
simply swaps $\ket{k,R}$ and $\ket{k+1,L}$, and the matrix expression of $S$
in this two basis states is

(3.23) $R_{B}:=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}=2\ket{+}\bra{+}-I.$

Thus, the matrix of $S$ in the basis
$\left\\{\ket{0,R},\ket{1,L},\ket{1,R},\cdots,\ket{2n,L},\ket{2n,R},\ket{2n+1,L}\right\\}$
is

(3.24) $M_{S}:=\text{diag}(\underbrace{R_{B},\cdots,R_{B}}_{2n+1}).$

As a result, the operator $U_{\mathrm{walk}}$ corresponds to a
$(4n+2)$-dimensional square matrix

(3.25) $\displaystyle M_{U}=M_{S}\cdot M_{C}.$

In addition, the initial state $\ket{0,R}:=\ket{s,\varphi(s)}$ corresponds to
the $(4n+2)$-dimensional vector $\ket{0}=[1,0,\cdots,0]^{\text{T}}$, and the
target state $\ket{2n+1,L}:=\ket{t,\varphi(t)}$ corresponds to
$\ket{4n+1}=[0,0,\cdots,1]^{\text{T}}$.

##  4 Succinct quantum algorithm with $O(n^{2}\log n)$ queries

Algorithm 1 succinct quantum algorithm for the welded tree problem

Input:

adjacency list quantum oracle $O$ (see Eq. (1.2)) for the welded tree $G_{n}$,
and the entrance name $s\equiv 0^{2n}$.

Output:

the exit name $t$.

Procedure:

  1. 1.

Classical predetermine the walk step number $T_{1}$: For the initial vector
$\ket{\psi_{0}}=\ket{0}$, loop “$\ket{\psi_{T}}\leftarrow
M_{U}\ket{\psi_{T-1}}$” (see Eq. (3.25) for $M_{U}$) and
“$p_{T}\leftarrow|\braket{4n+1}{\psi_{T}}|$”, stop when $T>3.6\,n\log(5n)$.
Record the largest $p_{T_{1}}$ for $2n<T_{1}<3.6\,n\log(5n)$ and the
corresponding $T_{1}$.

  2. 2.

Quantum walk: Apply $T_{1}$ steps of coined quantum walk, i.e.
$U_{\mathrm{walk}}^{T_{1}}$ (Eq. (2.4)) to the initial state
$\ket{s,\varphi(s)}$ (Eq. (2.14)) and measure the first register in the
computational basis to obtain a vertex name with $\Omega(\frac{1}{n})$
probability.

  3. 3.

Repeat step 2 for $O(n)$ times to obtain the exit name $t$ with constant
probability.

Here we present a rather succinct quantum algorithm (i.e., Algorithm 1) for
the welded tree problem, which is to first efficiently compute a walk step
number $T_{1}$ on classical computers, and then simply perform the walk
operator $U_{\mathrm{walk}}$ with $T_{1}$ times. The correctness is guaranteed
by Theorem 4.1, from which together with Lemma 2.1 it is easy to see that the
query complexity of Algorithm 1 is $O(n^{2}\log n)$, with an additional time
complexity of $O(n\cdot n^{2}\log(n))=O(n^{3}\log(n))$.

###### Theorem 4.1

Consider the success probability
$p(t):=\left|\bra{4n+1}M_{U}^{t}\ket{0}\right|^{2}$, where $M_{U}$ is defined
by Eq. (3.25). Then for sufficiently large $n$ and $T\approx 3.6\,n\log(5n)$,
we have

(4.26) $\max\\{p(t):t\in[2n,T]\\}>\frac{1}{20n}.$

The remainder of this section is to prove the above theorem. As mentioned in
Section 1.4, the first and most important step to prove Theorem 4.1 is to
obtain the spectral decomposition of the reduced matrix, i.e.
$M_{U}=\sum_{j}e^{i\varphi_{j}}\ket{E_{j}}\bra{E_{j}}$, which will be shown by
Lemma 4.1 in Section 4.1. Then we will present and prove the helper Lemma 4.2
in Section 4.2, a key step in obtaining the lower bound $\Omega(\frac{1}{n})$
of the average success probability
$\mathbb{E}|\bra{4n+1}M_{U}^{t}\ket{0}|^{2}$, from which Theorem 4.1 follows.
In order to use this helper lemma, we will need the values
$\braket{4n+1}{E_{j}}\cdot\braket{E_{j}}{0}$ for $j\in S$, and bound the gap
$\Delta E_{S}=\min\\{|\varphi_{j}-\varphi_{k}|:\varphi_{j}\in S,\varphi_{k}\in
E,k\neq j\\}$ by choosing $S\subseteq E=\\{\varphi_{j}\\}$ well (so that
$\Delta E_{S}$ will be of order $\Omega(\frac{1}{n})$ as shown by Eq. (4.51)
and Lemma 4.3 in Section 4.3). Thus, even though the explicit formula shown in
Lemma 4.1 is quite complicated, we only need to pay attention to the the first
and last term of the eigenvectors $\ket{E_{j}}$, and the gap between the
eigenvalue angles $\varphi_{j}$.

###  4.1 Spectral decomposition of $M_{U}$

As a preliminary, first notice that $M_{C}$ (see Eq. (3.22)) can be expressed
as $2AA^{\dagger}-I$, where $A$ is the following $2(2n+1)\times 2(n+1)$
centrosymmetric matrix:

(4.27) $A=\left[\begin{array}[]{cccc|c}1&&&&\\\ &\sqrt{p}&&&\\\
&\sqrt{q}&&&\\\ &&\ddots&&\\\ &&&\sqrt{p}&\\\ &&&\sqrt{q}&\\\
\hline\cr&&&&*\\\ \end{array}\right],$

where

(4.28) $p=\frac{1}{3},\ q=1-p$

represent respectively the probability of walking to the roots and to the
random cycle. The $(2n+1)\times(n+1)$ sub-matrix in the bottom right-hand
corner denoted by ‘$*$’ can be deduced from the centrosymmetry of $A$. It’s
easy to see that all the columns in $A$ are orthonormal, thus
$A^{\dagger}A=I_{2(n+1)}$.

###### Lemma 4.1

The matrix $M_{U}$ defined by Eq. (3.25) has $(4n+2)$ different eigenvalues.
Two of which are $\pm 1$, and the respective eigenvectors are $\ket{u_{\pm
1}}=A\ket{v_{\pm 1}}$, where the $i$-th component of $\ket{v_{\pm 1}}$ denoted
by $v_{\pm 1}(i)$ is shown in the following:

(4.29) $v_{\pm 1}(i)=\begin{cases}1,&i=1,\\\
(\pm\sqrt{q/p})^{i-1}/\sqrt{q},&i=2\sim n+1,\\\ \pm(*)&i=n+2\sim
2n+2.\end{cases}$

The $(*)$ above can be deduced from centrosymmetry of $\ket{v_{\pm 1}}$. The
square of norms are:

(4.30) $\|\ket{u_{\pm 1}}\|^{2}=\|\ket{v_{\pm
1}}\|^{2}=\frac{2}{p-q}\\{2p-(q/p)^{n}\\}.$

The other $4n$ eigenvalues are $\exp(\pm i\varphi_{\pm k})$ with $\ k=2\sim
n+1$, where $\varphi_{\pm k}=\arccos\lambda_{\pm k}$ and
$\lambda_{-k}=-\lambda_{k}$. Here, $\lambda_{\pm k}=2\sqrt{pq}\cos\theta_{\pm
k}$, and $\theta_{\pm k}$ ($\theta_{-k}:=\pi-\theta_{k}$) are the $2n$ roots
of the following equation:

(4.31) $\sqrt{q}\sin(n+1)\theta\pm\sqrt{p}\sin n\theta=0.$

The eigenvectors corresponding to $\exp(\pm i\varphi_{\pm k})$ are:

(4.32) $\ket{u_{\pm,\pm k}}:=\ket{a_{\pm k}}-\exp(\pm i\varphi_{\pm
k})\ket{b_{\pm k}},$

where $\ket{a_{\pm k}}=A\ket{v_{\pm k}},\ket{b_{\pm k}}=M_{S}\ket{a_{\pm k}}$.
The components of $\ket{v_{\pm k}}$ are as follows:

(4.33) $v_{\pm k}(i)=\begin{cases}1,&i=1,\\\ \frac{\lambda_{\pm
k}}{\sqrt{p}}{U}_{i-2}(\lambda_{\pm
k}/\sqrt{pq})-\frac{1}{\sqrt{q}}{U}_{i-3}(\lambda_{\pm k}/\sqrt{pq}),&i=2\sim
n+1\\\ \pm(*),&i=n+2\sim 2n+2\end{cases}$

where $(*)$ can be deduced from centrosymmetry, and $U_{i}(x)$ is the monic
Chebyshev of the second kind:

(4.34)
$U_{i}(x)=\frac{\sin(i+1)\arccos\frac{x}{2}}{\sqrt{1-(\frac{x}{2})^{2}}}.$

The square of norms are

(4.35) $\|\ket{u_{\pm,\pm
k}}\|^{2}=\frac{2(1-\lambda_{k}^{2})^{2}}{q\sin^{2}\theta_{k}}\Big{(}n+\sqrt{\frac{q}{p}}\frac{\sin((n+1)2\theta_{k})}{2\sin\theta_{k}}\Big{)}.$

  * Proof.

The proof is a bit lengthy and is deferred to Appendix B.

###### Remark 4.1

We suspect the reason that no succinct algorithm for the welded tree problem
based on simple coined quantum walks has been proposed a priori, is that an
enough understanding on the spectral decomposition of the DTQW operator has
not been obtained before. Although Ref. [25] is a big step towards this
direction, the results obtained there are not satisfactory:

(4.36)
$\frac{1}{T}\sum_{t\in[T]}|\bra{4n+1}M_{U}^{t}\ket{0}|^{2}=2^{-\Omega(n)},\quad
T\to\infty,$

showing that the average success probability is exponentially small when
$T\to\infty$.

###  4.2 The helper lemma

Another key component in proving Theorem 4.1 is the following helper Lemma
4.2, which is a discrete-time adaptation of [26, Lemma 3]. However, our proof
of Lemma 4.2 is simpler than the one for [26, Lemma 3], as it does not involve
integral or characteristic functions of continuous random variables. Moreover,
their intermediate step [26, Lemma 4] considers the Frobenius norm of the
difference between density matrices, which introduces a strange factor of
$\sqrt{3}$.

Lemma 4.2 shows that when the iteration number $t$ is chosen according to some
specific distribution on $[T]:=\\{0,1,\cdots,T-1\\}$, the average success
probability has a lower bound that is related to the characteristic of the
eigenvalue angles of $M_{U}$ and the products of the first and the last term
of the eigenvectors.

###### Lemma 4.2

Assume that $M_{U}$ has a spectral decomposition
$M_{U}=\sum_{j}e^{i\varphi_{j}}\ket{E_{j}}\bra{E_{j}}$ where $\varphi_{j}$ are
all distinct, and the initial state is written in this eigenbasis as
$\ket{\psi_{0}}=\sum_{j}c_{j}\ket{E_{j}}$ and the target state as
$\ket{y}=\sum_{j}y_{j}\ket{E_{j}}$. For a subset $S\subseteq
E:=\\{\varphi_{j}\\}$, denote $\Delta
E_{S}:=\min\\{|\varphi_{j}-\varphi_{k}|:\varphi_{j}\in S,\varphi_{k}\in
E,k\neq j\\}$. Let $t=\sum_{m=1}^{k}t_{m}$ be the sum of $k$ i.i.d. uniform
random variables $t_{m}\in[T]$. Consider the average success probability

(4.37)
$\bar{p}(y|\psi_{0})=\frac{1}{T^{k}}\sum_{t\in[T]^{k}}|\bra{y}M_{U}^{t}\ket{\psi_{0}}|^{2},$

where $t$ can be regarded as a random vector
$(t_{1},t_{2},\cdots,t_{k})\in[T]^{k}$ each with equal probability
$\frac{1}{T^{k}}$. Then $\bar{p}(y|\psi_{0})$ has the following lower bound:

(4.38) $\bar{p}(y|\psi_{0})\geq\sum_{j:\varphi_{j}\in
S}|y_{j}^{*}\,c_{j}|^{2}-\Big{(}\frac{\pi}{T\,\Delta E_{S}}\Big{)}^{k}.$

  * Proof.

Denote by $A(t):=\bra{y}M_{U}^{t}\ket{\psi_{0}}$ the amplitude of success,
then according to the spectral decomposition of $M_{U}$, we have
$A(t)=\sum_{j}y_{j}^{*}\,c_{j}\,e^{i\varphi_{j}t}$. From
$|A(t)|^{2}=A(t)A(t)^{*}$, we know

(4.39)
$\bar{p}(y|\psi_{0})=\sum_{j,j^{\prime}}\left[y_{j}^{*}\,c_{j}\,y_{j^{\prime}}\,c_{j^{\prime}}^{*}\,\sum_{t\in[T]^{k}}\frac{1}{T^{k}}e^{i(\varphi_{j}-\varphi_{j^{\prime}})t}\right].$

We now divide the sum $\sum_{j,j^{\prime}}[\cdots]$ in Eq. (4.39) into the
following three parts.

    1. (1)

$j=j^{\prime}$ and $\varphi_{j}\in S$: $\sum_{j,j^{\prime}}[\cdots]=\sum_{j\in
S}|y_{j}^{*}\,c_{j}|^{2}$.

    2. (2)

$\varphi_{j}\notin S$ and $\varphi_{j^{\prime}}\notin S$:

(4.40)
$\sum_{j,j^{\prime}}[\cdots]=\frac{1}{T^{k}}\sum_{t}\sum_{j}y_{j}^{*}\,c_{j}e^{i\varphi_{j}t}\sum_{j^{\prime}}y_{j^{\prime}}c_{j^{\prime}}^{*}e^{-i\varphi_{j^{\prime}}t}\geq
0.$

    3. (3)

The rest part, i.e. $j\neq j^{\prime},\varphi_{j}\in S,\varphi_{j^{\prime}}\in
S$, and $\varphi_{j}\notin S,\varphi_{j^{\prime}}\in S$, and $\varphi_{j}\in
S,\varphi_{j^{\prime}}\notin S$.

Therefore, we only need to prove that the value of part (3) is greater than
$-\Big{(}\frac{\pi}{T\,\Delta E_{S}}\Big{)}^{k}$. First, note that now
$\varphi_{j}\neq\varphi_{j^{\prime}}$ and one of them belongs to $S$. Thus
$|\varphi_{j}-\varphi_{j^{\prime}}|\geq\Delta E_{S}$, and we have

(4.41)
$\displaystyle\Big{|}\sum_{t\in[T]^{k}}\frac{1}{T^{k}}e^{i(\varphi_{j}-\varphi_{j^{\prime}})t}\Big{|}$
$\displaystyle=\Big{|}\prod_{m=1}^{k}\sum_{t_{m}=0}^{T-1}\frac{1}{T}e^{i(\varphi_{j}-\varphi_{j^{\prime}})t_{m}}\Big{|}$
(4.42)
$\displaystyle=\prod_{m=1}^{k}\Big{|}\sum_{t_{m}=0}^{T-1}\frac{1}{T}e^{i(\varphi_{j}-\varphi_{j^{\prime}})t_{m}}\Big{|}$
(4.43)
$\displaystyle=\Big{|}\frac{1-e^{i(\varphi_{j}-\varphi_{j^{\prime}})T}}{T(1-e^{i(\varphi_{j}-\varphi_{j^{\prime}})})}\Big{|}^{k}$
(4.44) $\displaystyle\leq\Big{(}\frac{2}{T\cdot{2}\Delta
E_{S}/{\pi}}\Big{)}^{k}=\Big{(}\frac{\pi}{T\Delta E_{S}}\Big{)}^{k},$

where we have used $t=\sum_{m=1}^{k}t_{m}$ in the first equality, and the
following identities
$|1-e^{i\varphi}|=|e^{i\varphi/2}-e^{-i\varphi/2}|=|2\sin\varphi/2|\geq
2\frac{\varphi}{\pi}$ in the last line. Then, we can bound the value of part
(3) using Cauchy-Schwartz as follows:

(4.45) $\displaystyle\Big{|}\sum_{j,j^{\prime}}[\cdots]\Big{|}$
$\displaystyle\leq\Big{(}\frac{\pi}{T\Delta
E_{S}}\Big{)}^{k}\sum_{j,j^{\prime}}|y_{j}^{*}\,c_{j}\,y_{j^{\prime}}\,c_{j^{\prime}}^{*}|$
(4.46) $\displaystyle\leq\Big{(}\frac{\pi}{T\Delta
E_{S}}\Big{)}^{k}\sqrt{\sum_{j,j^{\prime}}|y_{j}|^{2}|y_{j^{\prime}}|^{2}}\sqrt{\sum_{j,j^{\prime}}|c_{j}|^{2}|c_{j^{\prime}}|^{2}}$
(4.47) $\displaystyle=\Big{(}\frac{\pi}{T\Delta E_{S}}\Big{)}^{k}.$

###  4.3 Lower bounding $\Delta E_{S}$

With Lemma 4.2 in hand, in order to prove Theorem 4.1, we will need to select
a suitable subset of eigenvalue angles $S$ and an upper bound of iteration
times $T^{\prime}=k(T-1)<kT$ such that the first term of Eq. (4.38) is
$\Omega(\frac{1}{n})$, and the second term is a smaller $O(\frac{1}{n})$ term.

We now select the eigenvalue angle subset $S$ in Lemma 4.2 to be those
$\varphi_{\pm k}=g(\theta_{\pm k})$ whose $\theta_{\pm k}\in
S^{\prime}:=(\frac{\pi}{3},\frac{2\pi}{3})$, where $g$ is the following
function:

(4.48) $g(\theta_{\pm k}):=\arccos(2\sqrt{pq}\cos\theta_{\pm k}).$

Note that $g(\theta)\in[\arccos(2\sqrt{pq}),\pi-\arccos(2\sqrt{pq})]$ when
$\theta\in[0,\pi]$. Thus the angles $\varphi_{\pm k}$ with $k=2\sim(n+1)$ have
a constant gap with $\varphi_{\pm 1}=0,\pi$. Furthermore, it can be seen from
Fig. 3 that $g(\theta)$ is monotone increasing on $(0,\pi)$, and the minimal
derivative when $\theta\in S^{\prime}$ is $g^{\prime}(\pi/3)=\sqrt{6/7}$,
since

(4.49)
$g^{\prime}(\theta)=\frac{2\sqrt{pq}\sin\theta}{\sqrt{1-4pq\cos^{2}\theta}}.$

The minimal angle gap

(4.50) $\Delta_{\theta}:=\min\\{|\theta_{\pm k}-\theta_{\pm j}|:\theta_{\pm
k}\in S^{\prime},\theta_{\pm j}\in(0,\pi),k\neq j\\}$

of $\theta_{k}$ will result in the minimal angle gap of $\varphi_{k}$ to
satisfy:

(4.51) $\Delta E_{S}\geq\sqrt{6/7}\Delta_{\theta},$

when $n$ is sufficiently large. This is because we only need to consider the
gap between $\theta_{\pm k}$ and $\theta_{\pm j}$ all belonging to
$S^{\prime}$, and the gap $\overline{\Delta_{\theta}}$ between $\theta_{\pm
k}\in S^{\prime}$ nearest to $\pi/3$ and its adjacent $\theta_{\pm j}$ on the
left. In the latter case, we have $g(\theta_{\pm k})-g(\theta_{\pm j})\geq
g^{\prime}(\pi/3-\overline{\Delta_{\theta}})\overline{\Delta_{\theta}}$. But
as $g^{\prime}(\pi/3-\overline{\Delta_{\theta}})\to g^{\prime}(\pi/3)$ when
$n\to\infty$, Eq. (4.51) holds when $n$ is sufficiently large. Therefore, in
order to bound $\Delta E_{S}$, it’s sufficient to consider $\Delta_{\theta}$.

Figure 3:  The function $\varphi=g(\theta)$ defined in Eq. (4.48), and its
derivative $g^{\prime}(\theta)$.

Eq. (4.31) in Lemma 4.1 shows that the angles $\theta_{\pm k}$ where $k=2\sim
n+1$ are the $2n$ roots of the following equation in the interval $(0,\pi)$.

(4.52) $\frac{\sin(n+1)\theta}{\sin n\theta}=\mp\frac{1}{\sqrt{2}}.$

###### Remark 4.2

Equation (4.52) is almost the same as the one presented in Ref. [17], but the
RHS there is $\pm\sqrt{2}$. Therefore our analysis shown below is slightly
different from those shown in Ref. [26] (which contains a review and some
improvements of the results in Ref. [17]).

For an intuitive understanding of Eq. (4.52), its LHS for $n=8$ and the
horizontal lines $y=0,\pm\frac{1}{\sqrt{2}}$ are plotted in Fig. 4.

Figure 4:  Left hand side of Eq. (4.52) for $n=8$.

We now present Lemma 4.3 showing that $\Delta_{\theta}=\Omega(1/n)$ with our
choice of $S^{\prime}$.

###### Lemma 4.3

When $n$ is sufficiently large, the minimal gap $\Delta_{\theta}$ of the roots
of Eq. (4.52) has the following $\Omega(1/n)$ lower bound with
$S^{\prime}=(\frac{\pi}{3},\frac{2\pi}{3})$:

(4.53) $\displaystyle\Delta_{\theta}$ $\displaystyle=\min\\{|\theta_{\pm
k}-\theta_{\pm j}|:\theta_{\pm k}\in S^{\prime},\theta_{\pm j}\in(0,\pi),k\neq
j\\}$ (4.54)
$\displaystyle\geq\frac{\pi-2\theta_{0}}{n}\approx\frac{0.15\pi}{n},$

where $\tan\theta_{0}=\frac{\sqrt{3}}{\sqrt{2}-1}$.

  * Proof.

By centrosymmetry, we only need to consider the angle gap between the root
$\theta=\frac{l\pi}{n}-\delta$ corresponding to RHS$=-\frac{1}{\sqrt{2}}$ in
Eq. (4.52) and the root
$\theta^{\prime}=\frac{l^{\prime}}{n}\pi+\delta^{\prime}$ corresponding to
RHS$=\frac{1}{\sqrt{2}}$ in Eq. (4.52), where $l^{\prime}\in\\{l-1,l\\}$.
Since the $(n-1)$ zeros $\frac{l\pi}{n}$ of $\sin n\theta$ correspond to the
vertical asymptotes of LHS of Eq. (4.52), we have
$\delta,\delta^{\prime}\in(0,\frac{\pi}{n})$.

We now consider the lower and upper bound of $\delta$. Substituting
$\theta=\frac{l\pi}{n}-\delta$ into Eq. (4.52), and using the trigonometric
identity $\sin(a-b)=\sin(a)\cos(b)-\cos(a)\sin(b)$, we have

(4.55) $\displaystyle-\sqrt{2}\sin(n\theta+\theta)$
$\displaystyle=\sin(n\theta)$ (4.56)
$\displaystyle\Leftrightarrow-\sqrt{2}\sin(l\pi-n\delta+\frac{l\pi}{n}-\delta)$
$\displaystyle=\sin(l\pi-n\delta)$ (4.57)
$\displaystyle\Leftrightarrow-\sqrt{2}\sin(n\delta-\frac{l\pi}{n}+\delta)$
$\displaystyle=\sin(n\delta)$ (4.58)
$\displaystyle\Leftrightarrow-\sqrt{2}\sin(n\delta-\theta)$
$\displaystyle=\sin(n\delta)$ (4.59)
$\displaystyle\Leftrightarrow-\sqrt{2}[\sin(n\delta)\cos\theta-\cos(n\delta)\sin\theta]$
$\displaystyle=\sin(n\delta)$ (4.60)
$\displaystyle\Leftrightarrow-\sqrt{2}[\tan(n\delta)\cos\theta-\sin\theta]$
$\displaystyle=\tan(n\delta)$

Thus

(4.61) $\tan(n\delta)=\frac{\sqrt{2}\sin\theta}{1+\sqrt{2}\cos\theta}.$

Since the RHS of Eq. (4.61) is monotone increasing on
$(\frac{\pi}{3},\frac{2\pi}{3})\ni\theta$, we have
$\frac{\sqrt{3}}{\sqrt{2}+1}<\tan(n\delta)<\frac{\sqrt{3}}{\sqrt{2}-1}$, from
which $\frac{\theta_{1}}{n}<\delta<\frac{\theta_{0}}{n}$, where
$\theta_{1}=\arctan\frac{\sqrt{3}}{\sqrt{2}+1}$.

We now consider the lower and upper bound of $\delta^{\prime}$. If we
Substitute $\theta^{\prime}=\frac{l^{\prime}}{n}\pi+\delta^{\prime}$ into Eq.
(4.52), we have

(4.62)
$\tan(n\delta^{\prime})=\frac{\sqrt{2}\sin\theta^{\prime}}{1-\sqrt{2}\cos\theta^{\prime}}.$

Similarly, it can be shown that
$\frac{\theta_{1}}{n}<\delta^{\prime}<\frac{\theta_{0}}{n}$. Therefore,
$\Delta_{\theta}\geq\min\\{\frac{\pi}{n}-2\frac{\theta_{0}}{n},2\frac{\theta_{1}}{n}\\}=\frac{\pi-2\theta_{0}}{n}\approx\frac{0.15\pi}{n}$.

###  4.4 Proof of Theorem 4.1

With the help of the above three Lemmas 4.1-4.3, We can now prove Theorem 4.1.

In order to lower bound the items $|y_{j}^{*}c_{j}|$ of the sum in Eq. (4.38)
in Lemma 4.2, we first calculate:

(4.63) $\displaystyle\braket{2n+1,L}{u_{\pm,\pm k}}\braket{u_{\pm,\pm
k}}{0,R}$ (4.64) $\displaystyle=\bra{2n+1,L}\cdot(\ket{a_{\pm k}}-\exp(\pm
i\varphi_{\pm k})\ket{b_{\pm k}})\cdot(\bra{a_{\pm k}}-\exp(\pm i\varphi_{\pm
k})\bra{b_{\pm k}})\cdot\ket{0,R}$ (4.65) $\displaystyle=[v_{\pm k}(1)-e^{\pm
i\varphi_{\pm k}}\sqrt{p}v_{\pm k}(2)]\cdot[v_{\pm k}(1)-e^{\mp i\varphi_{\pm
k}}\sqrt{p}v_{\pm k}(2)]\cdot(\pm_{k})$ (4.66) $\displaystyle=[v_{\pm
k}(1)^{2}+pv_{\pm k}(2)^{2}-2\lambda_{\pm k}v_{\pm k}(1)v_{\pm
k}(2)]\cdot(\pm_{k})$ (4.67) $\displaystyle=(\pm_{k})(1-\lambda_{k}^{2}).$

The last line follows from $v_{\pm k}(1)=1$ and $v_{\pm k}(2)=\lambda_{\pm
k}/\sqrt{p}$. Therefore, combined with the norm $\|\ket{u_{k}}\|$ shown by Eq.
(4.35) in Lemma 4.1, we have the following identities when $\theta_{k}\in
S^{\prime}$.

(4.68) $\displaystyle|\bra{2n+1,L}\Pi_{\ket{u_{\pm,\pm k}}}\ket{0,R}|$
$\displaystyle=\frac{1-\lambda_{k}^{2}}{\|\ket{u_{k}}\|^{2}}$ (4.69)
$\displaystyle=\frac{q}{2}\cdot\frac{\sin^{2}\theta_{k}}{1-\lambda_{k}^{2}}\Big{(}n+\sqrt{\frac{q}{p}}\frac{\sin((n+1)2\theta_{k})}{2\sin\theta_{k}}\Big{)}^{-1}$
(4.70)
$\displaystyle\geq\frac{1}{3}\cdot\frac{27}{28}\cdot(n+\sqrt{2}\frac{1}{2\cdot\sqrt{3}/2})^{-1}$
(4.71) $\displaystyle\geq\frac{9}{28n}+O(\frac{1}{n^{2}}).$

The third line above follows from
$\theta_{k}\in(\frac{\pi}{3},\frac{2\pi}{3})$. Since $\theta_{k}$ is almost
uniformly distributed in $(0,\pi)$, we have $\sum_{j\in
S}|y_{j}^{*}\,c_{j}|^{2}\geq\frac{2}{3}\cdot
4n\cdot(\frac{9}{28n})^{2}>\frac{1}{4n}$.

We set

(4.72) $k\geq\log 5n,$

and

(4.73) $T\geq\frac{\pi}{2\Delta E_{S}},$

which is approximately $\frac{n}{0.3\sqrt{6/7}}\approx 3.6n$ by Lemma 4.3 and
Eq. (4.51). Then $\left(\frac{\pi}{T\,\Delta
E_{S}}\right)^{k}\leq(\frac{1}{2})^{\log 5n}=\frac{1}{5n}$. And thus by Eq.
(4.38),

(4.74) $\displaystyle p(y|\psi_{0})$ $\displaystyle\geq\sum_{j\in
S}|y_{j}^{*}\,c_{j}|^{2}-\Big{(}\frac{\pi}{T\,\Delta E_{S}}\Big{)}^{k}$ (4.75)
$\displaystyle\geq\frac{1}{4n}-\frac{1}{5n}=\frac{1}{20n}.$

Note that $p(t)=\left|\bra{4n+1}M_{U}^{t}\ket{0}\right|^{2}=0$ when $t<2n$. In
fact, $M_{U}\ket{0}=\ket{1}$ and one iteration of $M_{U}$ can propagate the
amplitude from $\ket{k}$ to at furthest $\ket{k+2}$, thus $p(t)=0$ when
$t<2n$. Since maximum is greater than average, we have now proven Theorem 4.1.

###### Remark 4.3

We can actually obtain an explicit expression of
$A(t):=\bra{4n+1}M_{U}^{t}\ket{0}$ for odd $t$ as

(4.76) $\displaystyle A(t)$
$\displaystyle=\frac{p-q}{2p-(q/p)^{n}}+2q\sum_{k=2}^{n+1}\frac{\cos(t\arccos(2\sqrt{pq}\cos\theta_{k}))}{1-4pq\cos^{2}\theta_{k}}\frac{\sin^{2}\theta_{k}}{n+\sqrt{\frac{q}{p}}\frac{\sin((n+1)2\theta_{k})}{2\sin\theta_{k}}}.$

Since the expression is too complicated, our first attempt of directly
analyzing $A(t)$ fails, and thus we have turned to the help of Lemma 4.2.

$A(t)$ can be calculated as follows. By Eq. (4.67) and the expression of
$\ket{u_{\pm 1}}$ shown in Lemma 4.1, we have

(4.77) $\displaystyle A(t)$
$\displaystyle=\sum_{\pm}\sum_{\pm_{k}}\sum_{k=2}^{n+1}e^{\pm it\varphi_{\pm
k}}\frac{(\pm_{k})(1-\lambda_{k}^{2})}{\|\ket{u_{k}}\|^{2}}+\sum_{\pm}(\pm)^{t}\frac{(\pm)}{\|\ket{u_{1}}\|^{2}}.$

Note that

(4.78) $\sum_{\pm}e^{\pm it\varphi_{\pm k}}=2\cos(t\varphi_{\pm k}).$

Since $\varphi_{-k}=\pi-\varphi_{k}$, we have

(4.79) $\sum_{\pm_{k}}\cos(t\varphi_{\pm
k})(\pm_{k})=\cos(t\varphi_{k})(1-(-1)^{t}).$

Similarly,

(4.80) $\sum_{\pm}(\pm)^{t}(\pm)=1-(-1)^{t}.$

Therefore, it can be seen that

(4.81) $A(t)=0,\quad\text{if}\ t\ \text{is even.}$

Thus we will only consider odd $t$. Substituting the square of norms
$\|\ket{u_{\pm k}}\|^{2},k=1\sim(n+1)$ in Lemma 4.1, we have $A(t)$ as shown
in Eq. (4.76).

##  5 Deterministic quantum algorithm with $O(n^{1.5}\log n)$ queries

With the matrix expression $M_{U}=M_{S}\cdot M_{C}$ of $U_{\mathrm{walk}}$
within its reduced invariant subspace $\mathcal{H}_{0}$ obtained in Section 3,
the exact value of the amplitude on the target state after $T_{1}$ steps of
quantum walks, i.e. $\bra{4n+1}M_{U}^{T_{1}}\ket{0}$, can be calculated
exactly. Therefore, combining with one of the deterministic quantum search
algorithms [33], for example Long’s algorithm [34], we can design a
deterministic quantum algorithm for the welded tree problem as shown in
Algorithm 2.

More precisely, if there is a quantum process (unitary operation)
$\mathcal{A}$ that transform some initial state $\ket{0}$ to $\ket{\psi}$ that
has known overlap, i.e. $p=|\braket{t}{\psi}|\in(0,1)$, with the desired
target state $\ket{t}$. Then Long’s algorithm [34] can amplify the overlap to
$1$ by applying the generalized Grover’s iteration
$G(\alpha,\beta)=\mathcal{A}S_{0}(\beta)\mathcal{A}^{\dagger}\cdot
S_{t}(\alpha)$, where $S_{t}(\alpha)=e^{i\alpha\ket{t}\bra{t}}$ and
$S_{0}(\beta)=e^{-i\beta\ket{0}\bra{0}}$, for $T=O(1/p)$ times to the state
$\ket{\psi}=\mathcal{A}\ket{0}$.

In the case of the original Grover’s algorithm [35], $\mathcal{A}:=H^{\otimes
n}$ is the Hadarmard gates on $n$ qubits, $\ket{0}:=\ket{0}^{\otimes n}$, and
$\ket{t}$ is the equal-superposition of all target elements. In the case of
Algorithm 2, $\mathcal{A}:=U_{\mathrm{walk}}^{T_{1}}U_{p}$,
$\ket{0}:=\ket{s,\perp}$, and $\ket{t}:=\ket{t,\varphi(t)}$. The parameters
$T,\alpha,\beta$ are determined by the known overlap $p$, where in Grover’s
case is the square root of the proportion of target elements in the
unstructured database, and in our case is
$p_{T_{1}}=|\bra{4n+1}M_{U}^{T_{1}}\ket{0}|$.

Algorithm 2 Deterministic quantum algorithm for the welded tree problem

Input:

adjacency list quantum oracle $O$ (see Eq. (1.2)) for the welded tree $G_{n}$,
and the entrance name $s\equiv 0^{2n}$.

Output:

the exit name $t$.

Procedure:

  1. 1.

Same as step 1 in Algorithm 1.

  2. 2.

Construct quantum circuit of the generalized Grover’s iteration
$G(\alpha,\beta)=\mathcal{A}S_{0}(\beta)\mathcal{A}^{\dagger}\cdot
S_{t}(\alpha)$ as in Fig. 5, where
$\mathcal{A}:=U_{\mathrm{walk}}^{T_{1}}U_{p}$. Set the parameters
$\alpha,\beta,T_{2}$ as
$\alpha=-\beta=2\arcsin\left(\frac{\sin\frac{\pi}{4T_{2}+2}}{\sin\theta}\right)$
and $T_{2}=\lceil\frac{\pi/2-\theta}{2\theta}\rceil$, where
$\theta=\arcsin(p_{T_{1}})$.

  3. 3.

Apply $G(\alpha,\beta)^{T_{2}}$ to
$\ket{\psi_{T_{1}}}=\mathcal{A}\ket{s,\perp}$. This will result in
$\ket{t,\varphi(t)}$ exactly and thus measuring register $r_{1}$ leads to the
exit name $t$ with certainty.

Figure 5:  Quantum circuit implementing the generalized Grover’s iteration
$G(\alpha,\beta)=\mathcal{A}S_{0}(\beta)\mathcal{A}^{\dagger}\cdot
S_{t}(\alpha)$. Single qubit operation
$R_{z}(\alpha):=\mathrm{diag}(1,e^{i\alpha})$. Operator $S_{0}(\beta)$ add
phase shift $e^{-i\beta}$ to the initial state
$\ket{s,\perp}=\ket{0^{2n},1^{2n}}$, and operator $F_{t}$ flip the last
auxiliary qubit conditioned on $\ket{u}_{r_{1}}=\ket{t}$. Determining that
$u=t$ can be done by querying the three adjacent vertices of $u$ and checking
that exactly one of them is $\perp$ and $u\neq s$.

##  6 Numerical simulation supporting $O(n^{4/3})$ query complexity

We find that the actual performance of our algorithms is better than
$O(n^{1/2}\cdot n\log n)$, since results of numerical simulation (conducted by
MATLAB) show that the success amplitude will be $\Omega(n^{-1/3})$ when
$U_{\mathrm{walk}}$ is applied for $O(n)$ times. We formalize it in the
following Conjecture 6.1 (an improved version of Theorem 4.1). Then the query
complexity of Algorithm 2 will be $O(n^{1/3}\cdot n)=O(n^{4/3})$.

###### Conjecture 6.1

There exists odd number $T\in[2n,2.5n]$ ($T\approx n/\sqrt{pq}\approx 2.1213n$
for sufficient large $n$) such that

(6.82) $p_{T}:=\left|\bra{4n+1}M_{U}^{T}\ket{0}\right|>n^{-1/3}.$

###### Remark 6.1

We only consider odd $T$ because Eq. (4.81) shows that $p_{T}=0$ when $T$ is
even. The constant $\sqrt{pq}$ may come from the fact that
$g^{\prime}(\pi/2)=2\sqrt{pq}$ (see Eq. (4.49)) and
$2\pi/g^{\prime}(\pi/2)=1/\sqrt{pq}$.

One can obtain the exact value of the largest $p_{T}$ with $T\in[2n,2.5n]$
(denoted by $P_{T}$) using, for example, MATLAB’s Symbolic Math Toolbox. The
exact value of $P_{T}$ when $n=50,100,150$ is shown in Table 2.

$n$ | $T$ | $P_{T}$
---|---|---
$50$ | $109$ | $2^{152}\cdot 19\cdot 38861/3^{108}$
$100$ | $215$ | $2^{300}\cdot 318388779301/3^{214}$
$150$ | $323$ | $2^{451}\cdot 274739\cdot 1231103390273/3^{322}$
Table 2: The exact value of $P_{T}$ when $n=50,100,150$.

The scatter diagram of $P_{T}$ for $n=3,\cdots,500$ is shown in Fig. 6. It can
be seen that $P_{T}>n^{-1/3}$ holds for all $n\in[6,500]$, which supports
Conjecture 6.1.

Figure 6:  Scatter diagram of $P_{T}$ for $n=3,\cdots,500$. Orange solid line
represents $n^{-1/3}$.

The scatter diagram of the ratio $T/n$ for $n=3,\cdots,500$ is shown in Fig.
7. It can be seen that $T/n$ tends to
$\frac{1}{\sqrt{pq}}=\frac{3}{\sqrt{2}}\approx 2.12$ as $n\to\infty$.

Figure 7:  Scatter diagram of $T/n$ for $n=3,\cdots,500$. The horizontal line
represents $\frac{1}{\sqrt{pq}}=\frac{3}{\sqrt{2}}$.

We also depict, as an example $n=200$, evolution of the $(4n+2)$-dimensional
vector $\ket{\psi_{T}}=M_{U}^{T}\ket{0}$ for odd $T$ ranging from $1$ to
$2.5n$ in video [36]. The frame when $T=429$ of the video is shown in Fig. 8.
It can be seen that the amplitude of the state vector $\ket{\psi_{T}}$ can be
positive or negative, showing the periodic coherent and destructive nature of
quantum walk.

Figure 8:  The frame when $T=429$ of the video [36] showing the evolution of
the $(4n+2)$-dimensional vector $\ket{\psi_{T}}$ with $n=200$. The $x$-axis
represents the indices $k\in\\{0,\cdots,4n+1\\}$ of $\ket{\psi_{T}}$, and the
$y$-axis represents the amplitude of the $k$-th component, which is between
$[-1,1]$. The red pillar on the rightmost represents the amplitude
$\braket{4n+1}{\psi_{T}}$.

##  7 Conclusion

In this paper, we have revisited quantum algorithms for the welded tree
problem and proposed a rather succinct algorithm based purely on the simplest
coined quantum walks. A rigorous polynomial query upper bound is provided
based on spectral decomposition of the reduced quantum walk matrix. The
succinctness of our algorithm re-displays the power of the simplest framework
of quantum walks, changing the stereotype that the existing DTQW frameworks
before the multidimensional one can achieve at most a quadratic speedup over
the best classical algorithm. Our algorithm for the welded tree problem can
also be made zero-error theoretically, making it one of the few examples of an
exponential separation between the zero-error (exact) quantum and the
randomized query complexities. Numerical simulation indicates that the actual
performance of our algorithms is better, and it will be a future work to prove
Conjecture 6.1.

##  A Implementing $U_{\varphi}$ in Lemma 2.1

In this appendix, we will implement the unitary operator
$U_{\varphi}:\ket{u,\perp}\mapsto\ket{u,\varphi(u)}$ in Lemma 2.1. We first
introduce five auxiliary registers

(A.1)
$\ket{0}_{q_{1}}\ket{0}_{q_{2}}\ket{0}_{q_{3}}\ket{0}_{a}\ket{0}_{b}\ket{0}_{c},$

where register $q_{i}$ consists of $2n$ qubits storing the query result,
register $a$ is a qutrit with state space
$\mathbb{H}^{3}=\text{span}\\{\ket{0},\ket{1},\ket{2}\\}$ used for generating
$\ket{\varphi(u)}$ when $u$ is an internal node, register $b$ is a qudit with
state space $\mathbb{H}^{5}=\text{span}\\{\ket{0},\cdots,\ket{4}\\}$ storing
conditions, and register $c$ is a qubit used for generating $\ket{\varphi(u)}$
when $u$ is one of the roots. Now $U_{\varphi}$ can be implemented as follows,
where oracle query happens in the first and last step.

  1. 1.

Query the oracle $O$ on registers $r_{1},q_{1},q_{2},q_{3}$ to obtain

(A.2)
$\ket{u}_{r_{1}}\ket{\perp}_{r_{2}}\bigotimes_{i=1}^{3}\ket{\Gamma(u,i)}_{q_{i}}\
\ket{0}_{a}\ket{0}_{b}\ket{0}_{c}.$

  2. 2.

Apply the transformation $\ket{q}\ket{b}\mapsto\ket{q}\ket{b+f(q)}$ on
register $q:=(q_{1},q_{2},q_{3})$ and $b$. The function
$f:\\{0,1\\}^{6n}\to\\{0,\cdots,4\\}$ is defined as: $f(q)=0$ iff there’s no
$q_{i}=\perp$, so that $u$ is an internal node; $f(q)=i$ for $i=1,2,3$ iff
there’s one and only one $q_{i}=\perp$, so that $u\in\\{s,t\\}$, and the $i$th
register $q_{i}$ stores the value $\perp$; $f(q)=4$ iff there’s more than one
$q_{i}=\perp$, so that $u\notin V(G_{n})$. It can be easily seen that
calculating $f$ takes $O(n)$ basic operations.

  3. 3.

Conditioned on $b=0$, i.e. $u$ is an internal node, apply the following two
steps.

    1. 3.1.

Flip all the qubits of register $r_{2}$ so that it’s set to $\ket{0^{2n}}$.
Apply quantum Fourier transform $QFT_{3}$ to register $a$, and then controlled
by $\ket{i}_{a},\,i\in\\{0,1,2\\}$, add (i.e. bit-wise modulo $2$ addition)
the value of register $q_{(i+1)}$ to register $r_{2}$, obtaining

(A.3)
$\ket{u}_{r_{1}}(\frac{1}{\sqrt{3}}\sum_{i=0}^{2}\ket{\Gamma(u,i+1)}_{r_{2}}\ket{i}_{a})\
\bigotimes_{i=0}^{2}\ket{\Gamma(u,i+1)}_{q_{(i+1)}}\ket{b}_{b}\ket{0}_{c}.$

This controlled addition can be done in $O(n)$ basic operations.

    2. 3.2.

Compare $\ket{\Gamma(u,i)}_{r_{2}}$ with $\ket{\Gamma(u,j)}_{q_{j}}$ for
$j=1,2,3$ and subtract $\ket{i}_{a}$ with $(j-1)$, where $j$ is the unique
index $j$ such that $\ket{\Gamma(u,i)}_{r_{2}}=\ket{\Gamma(u,j)}_{q_{j}}$,
obtaining

(A.4)
$\ket{u}_{r_{1}}\ket{\varphi(u)}_{r_{2}}\bigotimes_{i=1}^{3}\ket{\Gamma(u,i)}_{q_{i}}\
\ket{0}_{a}\ket{b}_{b}\ket{0}_{c}.$

The uniqueness of the index $j$ can be easily seen from the condition that all
of $u$’s neighbours $\Gamma(u,i)$ are distinct. This compare (between binary
strings) and subtract operation can be done in $O(n)$ basic operations.

  4. 4.

Conditioned on $b\in\\{1,2,3\\}$, i.e. $u$ is one of the two roots and
register $q_{b}$ stores $\perp$, apply the following steps.

    1. 4.1.

Swap register $q_{b}$ and $q_{3}$ so that the first two auxiliary registers
store the genuine adjacent vertex name of $u\in\\{s,t\\}$. The conditioned
SWAP operation can be done in $O(n)$ basic operations.

    2. 4.2.

similar to step 3.1 and 3.2, transform $\ket{\perp}_{r_{2}}$ to
$\ket{\varphi(u)}_{r_{2}}$ with the help of
$H\ket{0}_{c}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$.

    3. 4.3.

Repeat step 4.1 so that the order of register $q_{i}$ is restored, ensuring
the success of step 7.

  5. 5.

Conditioned on $b=4$, apply the identity transformation $I$, since register
$r_{1}$ already stores $\varphi(u)=\perp$ (the three ‘neighbours’ of $u\notin
V(G_{n})$ are all $\perp$).

  6. 6.

Similar to step 2, apply the transformation
$\ket{q}\ket{b}\mapsto\ket{q}\ket{b-f(q)}$ to register $q,b$, where the
subtraction is modulo $5$. Therefore, register $b$ is recovered to
$\ket{0}_{b}$.

  7. 7.

Query the oracle $O$ once more as in step 2, so that all the auxiliary
registers are restored back to zero.

Thus $U_{\varphi}$ can be implemented with $2$ oracle queries and $O(n)$ basic
operations.

##  B Spectral decomposition of the reduced matrix

In this Appendix, we prove Lemma 4.1 about the spectral decomposition of the
reduced coined quantum walk matrix $M_{U}=M_{S}M_{C}$. The proof is inspired
by [25]. However, since its analysis is not perfect (as they did not obtain
analytical expression of $U_{k}$ shown in Eq. (B.42) by comparing with
Chebyshev polynomial of the second kind), we will show in detail the complete
proof for the sake of completeness and convenience of the readers.

We also expand or improve some of the implicit or complicated steps in [25],
and point out a connection with another commonly used technique for analyzing
quantum walk operators, i.e. the singular value decomposition, or more
precisely, Jordan’s Lemma [37] about common invariant subspaces of two
reflection operator, which has been used in Refs. [8, 10, 27, 38].

We first present the following helper Lemma B.1, which is implicit in [25] and
similar to [30, Theorem 1], saying that in order to obtain the spectral
decomposition of $M_{U}=M_{S}M_{C}$, we can instead consider the spectral
decomposition of the following matrix

(B.5) $A^{\dagger}M_{S}A=:J_{2n}.$

###### Lemma B.1

Consider the quantum walk operator $U=\mathrm{Ref}_{B}\,\mathrm{Ref}_{A}$,
where $\mathrm{Ref}_{A}=(2AA^{\dagger}-I)$ and $A$ is a matrix with full
column rank satisfying $A^{\dagger}A=I$. Let

(B.6) $\ket{a}:=A\ket{v},\ \ket{b}:=\mathrm{Ref}_{B}\ket{a},$

where $\|\ket{v}\|^{2}=1$. If

(B.7) $A^{\dagger}\mathrm{Ref}_{B}A\ket{v}=\lambda\ket{v}.$

Then, when $\left|\lambda\right|<1$, we have

(B.8) $U\ket{u}:=U\big{(}\ket{a}-e^{\pm i\varphi}\ket{b}\big{)}=e^{\pm
i\varphi}\ket{u},$

where $\varphi:=\arccos\lambda$, and $\|\ket{u}\|^{2}=2(1-\lambda^{2})$. And
when $\lambda=\pm 1$, we have

(B.9) $U\ket{a}=\pm\ket{a}.$

  * Proof.

We first consider the case when $\left|\lambda\right|<1$. From Eq. (B.7) we
know

(B.10) $\displaystyle U\ket{b}$
$\displaystyle=\mathrm{Ref}_{B}(2AA^{\dagger}-I)(\mathrm{Ref}_{B}A\ket{v})$
(B.11) $\displaystyle=2\mathrm{Ref}_{B}A\lambda\ket{v}-A\ket{v}$ (B.12)
$\displaystyle=2\lambda\ket{b}-\ket{a}.$

Therefore, $\mathrm{span}\\{\ket{a},\ket{b}\\}$ is an invariant subspace of
$U$, and $U$ takes the following matrix form:

(B.13) $L=\begin{bmatrix}0&-1\\\ 1&2\lambda\end{bmatrix}.$

Let $\lambda=\cos\varphi$, then we obtain the eigenvalues and eigenvectors of
$L$: $e^{\pm i\varphi}$ and $[1,-e^{\pm i\varphi}]^{T}$. This can be easily
verified by the following identities:

(B.14) $\displaystyle 1-2\lambda e^{\pm i\varphi}$
$\displaystyle=1-2\cos(\pm\varphi)e^{\pm i\varphi}$ (B.15)
$\displaystyle=1-2\cos^{2}(\pm\varphi)-2i\cos(\pm\varphi)\sin(\pm\varphi)$
(B.16) $\displaystyle=-\cos(\pm 2\varphi)-i\sin(\pm 2\varphi)$ (B.17)
$\displaystyle=-e^{\pm 2i\varphi}=e^{\pm i\varphi}\cdot(-e^{\pm i\varphi}).$

Therefore, we obtain two eigenvalues $e^{\pm i\varphi}$ of $U$ and their
respective eigenvectors $\ket{u}:=\ket{a}-e^{\pm i\varphi}\ket{b}$. We now
calculate the square of its norm:

(B.18) $\displaystyle\braket{u}{u}$ $\displaystyle=2-2\,\text{Re}(e^{\pm
i\varphi}\braket{a}{b})$ (B.19) $\displaystyle=2(1-\lambda^{2}).$

The second line follows from
$\braket{a}{b}=\bra{v}A^{\dagger}\text{Ref}_{B}A\ket{v}=\lambda$ and the fact
that $A^{\dagger}\text{Ref}_{B}A$ is Hermitian whose eigenvalue $\lambda$ is a
real number.

We now consider the case when $\lambda=\pm 1$. From Eq. (B.7), we know
$\bra{v}A^{\dagger}\mathrm{Ref}_{B}A\ket{v}=\pm 1$, and thus
$\mathrm{Ref}_{B}A\ket{v}=\pm A\ket{v}$. Therefore,

(B.20) $\displaystyle U\ket{a}$ $\displaystyle=UA\ket{v}$ (B.21)
$\displaystyle=\mathrm{Ref}_{B}(2AA^{\dagger}-I)A\ket{v}$ (B.22)
$\displaystyle=\mathrm{Ref}_{B}A\ket{v}$ (B.23) $\displaystyle=\pm A\ket{v}$
(B.24) $\displaystyle=\pm\ket{a}.$

###### Remark B.1

Suppose $\mathrm{Ref}_{B}=2BB^{\dagger}-I$. Let $D:=A^{\dagger}B$, and
consider its singular value decomposition
$\sum_{i}s_{i}\ket{v_{i}}\bra{w_{i}}$, which is a common approach in Refs. [8,
10, 27, 38]. Then the connection between the eigenvalue $\lambda$ of
$A^{\dagger}\,\mathrm{Ref}_{B}\,A$ and the singular value $s$ of $D$ is:

(B.25) $\arccos(\lambda)=2\arccos(s).$

  * Proof.

Since $DD^{\dagger}\ket{v_{i}}=s_{i}^{2}\ket{v_{i}}$, we have

(B.26) $\displaystyle A^{\dagger}\,\text{Ref}_{B}\,A$
$\displaystyle=A^{\dagger}(2BB^{\dagger}-I)A$ (B.27)
$\displaystyle=2(A^{\dagger}B)(A^{\dagger}B)^{\dagger}-I$ (B.28)
$\displaystyle=2DD^{\dagger}-I.$

Therefore,

(B.29) $A^{\dagger}\,\text{Ref}_{B}\,A\ket{v}=\lambda\ket{v}\Leftrightarrow
DD^{\dagger}\ket{v}=\frac{\lambda+1}{2}\ket{v}.$

From the identity $\frac{\cos\phi_{i}+1}{2}=\cos^{2}\frac{\phi_{i}}{2}$, we
obtain Eq.(B.25).

We now analyze the eigenvalues and eigenvectors of $J_{2n}=A^{\dagger}M_{S}A$.
First, we will need the matrix expression of $J_{2n}$. Recalling $A$ as
defined in Eq. (4.27), and since $M_{S}$ swaps two adjacent rows (columns), we
have:

(B.30) $A^{\dagger}M_{S}=\left[\begin{array}[]{ccccccc|c}0&1&&&&&&\\\
\sqrt{p}&0&0&\sqrt{q}&&&&\\\ &&\sqrt{p}&0&0&\sqrt{q}&&\\\ &&&&&\ddots&&\\\
&&&&\sqrt{p}&0&0&\sqrt{q}\\\ \hline\cr&&&&&&\sqrt{q}&*\\\
\end{array}\right]_{2(n+1)\times 2(2n+1)}.$

Thus $J_{2n}$ is a special tridiagonal and centrosymmetric matrix as shown
below:

(B.31) $J_{2n}=\left[\begin{array}[]{ccccc|c}0&\sqrt{p}&&&&\\\
\sqrt{p}&0&\sqrt{pq}&&\\\ &\sqrt{pq}&0&\ddots&&\\\
&&\ddots&\ddots&\sqrt{pq}&\\\ &&&\sqrt{pq}&0&q\\\
\hline\cr&&&&q&*\end{array}\right]_{2(n+1)\times 2(n+1)}.$

I. eigenvalues of $J_{2n}$

In order to calculate the characteristic equation $p(\lambda):=|\lambda
I-J_{2n}|$ of $J_{2n}$, first introduce the following two principal
submatrices. We use the notation $J_{2n}[l:k]$ to represent the main sub-
matrix from $l$ to $k$ rows (columns) of $J_{2n}$, so as to save space.

(B.32) $\displaystyle E_{k}$ $\displaystyle:=\lambda I-J_{2n}[1:k],$ (B.33)
$\displaystyle F_{k}$ $\displaystyle:=\lambda I-J_{2n}[2:k+1].$

Denote by $|M|:=\det(M)$ the determinant of matrix $M$. Then we have

(B.34) $\displaystyle|E_{2}|$ $\displaystyle=\lambda|E_{1}|-p|E_{0}|,$ (B.35)
$\displaystyle|E_{k}|$ $\displaystyle=\lambda|E_{k-1}|-pq|E_{k-2}|,\ (3\leq
k\leq n+1)$ (B.36) $\displaystyle|E_{k}|$
$\displaystyle=\lambda|F_{k-1}|-p|F_{k-2}|,\ (2\leq k\leq n+1)$ (B.37)
$\displaystyle|F_{k}|$ $\displaystyle=\lambda|F_{k-1}|-pq|F_{k-2}|,\ (2\leq
k\leq n)$

where the first two terms are $|F_{1}|=\lambda,\ |F_{0}|:=1$ and
$|E_{1}|=\lambda,\ |E_{0}|:=1$. Note that Eq.(B.35) is obtained by expanding
$|E_{k}|$ from its lower right corner, while the second equality is obtained
by expanding $|E_{k}|$ from its upper left corner. Dividing all the elements
in $F_{k}$ by $\sqrt{pq}$ and denoting

(B.38) $|F_{k}|/\sqrt{pq}^{k}:=U_{k}(\lambda/\sqrt{pq}),$

Eq. (B.37) is now transformed to
$U_{k}(\lambda/\sqrt{pq})=\lambda/\sqrt{pq}\,U_{k-1}(\lambda/\sqrt{pq})-U_{k-2}(\lambda/\sqrt{pq})$.
If we let $x:=\frac{\lambda}{\sqrt{pq}}$, then Eq. (B.37) further simplifies
to

(B.39) $\displaystyle U_{0}(x)$ $\displaystyle=1,\ U_{1}(x)=x,$ (B.40)
$\displaystyle U_{k}(x)$ $\displaystyle=x\,U_{k-1}(x)-U_{k-2}(x).$

Comparing the above equations with the recurrence relation of Chebyshev
polynomial of the second kind:

$\displaystyle\tilde{U}_{0}(x)$ $\displaystyle=1,\ \tilde{U}_{1}(x)=2x,$
(B.41) $\displaystyle\tilde{U}_{k}(x)$
$\displaystyle=2x\tilde{U}_{k-1}(x)-\tilde{U}_{k-2}(x),\ \text{for}\ k\geq 2,$

we know $U_{k}(x)=\tilde{U}_{k}(x/2)$. From the general term formula
$\tilde{U}_{k}(\cos\theta)=\frac{\sin(k+1)\theta}{\sin\theta}$, we let
$\theta$ be such that it satisfies
$\frac{\lambda}{2\sqrt{pq}}=x/2=\cos\theta$. Therefore,

(B.42)
$U_{k}(\lambda/\sqrt{pq})=\tilde{U}_{k}(\cos\theta)=\frac{\sin(k+1)\theta}{\sin\theta},$

from which Eq. (4.34) in Lemma 4.1 follows.

We now calculate $p(\lambda)=|\lambda I-J_{2n}|$ by expanding its $n+1$ row as
follows. Denote by $E_{k}^{\prime}=\lambda I-J_{2n}[2n+2-k+1:2n+2]$ the last
$k$ rows and columns of $\lambda I-J_{2n}$. It is easy to see that
$|E_{k}^{\prime}|=|E_{k}|$ from the centrosymmetry of $J_{2n}$.

(B.51) $\displaystyle p(\lambda)$
$\displaystyle=\sqrt{pq}\left|\begin{array}[]{ccc}E_{n-1}&&\\\
-\sqrt{pq}&-\sqrt{pq}&\\\
&-q&E_{n+1}^{\prime}\end{array}\right|+\lambda\left|\begin{array}[]{cc}E_{n}&\\\
&E_{n+1}\end{array}\right|+q\left|\begin{array}[]{ccc}E_{n}&-\sqrt{pq}&\\\
&-q&-\sqrt{pq}\\\ &&E_{n}^{\prime}\end{array}\right|$ (B.52)
$\displaystyle=-pq|E_{n-1}|\cdot|E_{n+1}|+\lambda|E_{n}|\cdot|E_{n+1}|-q^{2}|E_{n}|^{2}$
(B.53)
$\displaystyle=(\lambda^{2}-q^{2})|E_{n}|^{2}-2pq\lambda|E_{n}|\cdot|E_{n-1}|+(pq)^{2}|E_{n-1}|^{2}$
(B.54)
$\displaystyle=\big{(}(\lambda-q)|E_{n}|-pq|E_{n-1}|\big{)}\big{(}(\lambda+q)|E_{n}|-pq|E_{n-1}|\big{)}.$

Note that when choosing $-q$ as the pivot to expand the first determinant in
Eq. (B.51), the following sub-determinant is zero.

(B.55) $\left|\begin{array}[]{c|cc}E_{n-1}&&\\\ -\sqrt{pq}&&\\\
\hline\cr&-\sqrt{pq}&E_{n}^{\prime}\end{array}\right|=0.$

This is because the first $n$ rows are rank deficient as there are only $n-1$
columns with non zero elements. The same reasoning applies to expanding the
third determinant in Eq. (B.51). The third line (Eq. (B.53)) uses Eq. (B.35)
to further expand $|E_{n+1}|$.

We can further simplify the two components of $p(\lambda)$ in Eq. (B.54) by
using Eqs. (B.36), (B.37) to expand until $|F_{n-1}|,\ |F_{n-2}|$:

(B.56) $\displaystyle(\lambda\mp q)|E_{n}|-pq|E_{n-1}|$ (B.57)
$\displaystyle=\lambda|F_{n}|-p|F_{n-1}|\mp q(\lambda|F_{n-1}|-p|F_{n-2}|)$
(B.58)
$\displaystyle=\lambda(\lambda|F_{n-1}|-pq|F_{n-2}|)+(\mp(1-p)\lambda-p)|F_{n-1}|\pm
pq|F_{n-2}|$ (B.59) $\displaystyle=[\lambda(\lambda\mp 1)\pm p(\lambda\mp
1)]\cdot|F_{n-1}|-pq(\lambda\mp 1)|F_{n-2}|$ (B.60) $\displaystyle=(\lambda\mp
1)\ (|F_{n}|\pm p|F_{n-1}|).$

Using Eq. (B.38), we now obtain the eigenvalues of $J_{2n}$: $\pm 1$ and
$\lambda_{\pm k}:=2\sqrt{pq}\cos\theta_{\pm k}$, where $\lambda_{\pm k}$ are
the $2n$ roots of the following equation:

(B.61)
$\sqrt{q}\,U_{n}(\lambda/\sqrt{pq})\pm\sqrt{p}\,U_{n-1}(\lambda/\sqrt{pq})=0.$

Combining with Eq. (B.42), we obtain Eq. (4.31) in Lemma 4.1. It can also be
seen that when $\theta_{k}$ corresponds to a root with ‘$+$’, then
$\theta_{-k}:=\pi-\theta_{k}$ corresponds to a root with ‘$-$’, thus
$\lambda_{-k}=-\lambda_{k}$.

II. eigenvectors of $J_{2n}$

We now consider the eigenvectors of $J_{2n}$. Using Eqs. (B.34), (B.35), and
“$(\lambda_{k}\mp q)|E_{n}|-pq|E_{n-1}|=0$” by Eq. (B.56), it is not difficult
to verify that the respective (unnormalized) eigenvector $\ket{v_{\pm k}}$
(which satisfies $(\lambda I-J_{2n})\ket{v_{\pm k}}=0$) is

(B.62)
$[1,\frac{|E_{1}|}{\sqrt{p}},\frac{|E_{2}|}{\sqrt{p}\sqrt{pq}},\cdots,\frac{|E_{n-1}|}{\sqrt{p}\sqrt{pq}^{n-2}},\frac{|E_{n}|}{\sqrt{p}\sqrt{pq}^{n-1}},\pm(*)],$

Where $(*)$ can be deduced from centrosymmetry. Combing with the relation of
the sub-determinant $|E_{k}|$, $|F_{k}|$ shown in Eqs. (B.36), (B.37), the
components and the square of the norm of the eigenvector $\ket{v_{\pm k}}$ can
be calculated as follows.

1\. $\lambda=\pm 1$

Since $\lambda^{2}=(\pm)^{2}=1$, we have

(B.63) $\displaystyle|F_{k}|$ $\displaystyle=\pm|F_{k-1}|-pq|F_{k-2}|$ (B.64)
$\displaystyle=\pm q|F_{k-1}|\pm p(\pm|F_{k-2}|-pq|F_{k-3}|)-pq|F_{k-2}|$
(B.65) $\displaystyle=\pm q(|F_{k-1}|-p^{2}|F_{k-3}|)-p^{2}|F_{k-2}|.$

Thus we know the difference between every other term, i.e.
$|F_{k}|-p^{2}|F_{k-2}|$, is a power series. Therefore,

(B.66) $\displaystyle|E_{k}|$ $\displaystyle=\pm|F_{k-1}|-p|F_{k-2}|$ (B.67)
$\displaystyle=\pm|F_{k}|-p^{2}|F_{k-1}|$ (B.68) $\displaystyle=(\pm
q)^{k-2}(|F_{2}|-p^{2}|F_{0}|)$ (B.69) $\displaystyle=(\pm
q)^{k-2}(1-pq-p^{2})$ (B.70) $\displaystyle=(\pm)^{k}q^{k-1}.$

The second line follows from substituting $q=1-p$ into the second equality of
Eq. (B.37). Thus the $(i+1)$-th component of $\ket{v_{\pm 1}}$ is

(B.71) $\displaystyle\braket{i}{v_{\pm 1}}$
$\displaystyle=\frac{|E_{i}|}{\sqrt{p}\sqrt{pq}^{i-1}}$ (B.72)
$\displaystyle=\frac{(\pm)^{i}q^{i-1}}{\sqrt{p}\sqrt{pq}^{i-1}}$ (B.73)
$\displaystyle=(\pm)^{i}(\sqrt{{q}/{p}})^{i}/\sqrt{q},$

which is Eq. (4.29) in Lemma 4.1. Hence, the square of the norm of
$\ket{v_{\pm 1}}$ is:

(B.74) $\displaystyle\|\ket{v_{\pm 1}}\|^{2}$
$\displaystyle=2(1+\frac{1}{q}\sum_{i=1}^{n}(\frac{q}{p})^{i})$ (B.75)
$\displaystyle=2(1+\frac{1}{p}\frac{1-(q/p)^{n}}{1-q/p})$ (B.76)
$\displaystyle=\frac{2}{q-p}((q/p)^{n}-2p),$

which is Eq. (4.30) in Lemma 4.1.

2\. $\lambda_{\pm k}$ for $k=2\sim(n+1)$

The $(i+1)$-th component of $\ket{v_{\pm k}}$ can be calculated as follows,
where we omit the subscript $\pm k$ for simplicity.

(B.77) $\displaystyle\braket{i}{v_{\lambda}}=$
$\displaystyle\frac{\lambda|F_{i-1}|-p|F_{i-2}|}{\sqrt{p}\sqrt{pq}^{i-1}}$
(B.78)
$\displaystyle=\frac{\lambda\sqrt{pq}^{i-1}U_{i-1}(\lambda/\sqrt{pq})-p\sqrt{pq}^{i-2}U_{i-2}(\lambda/\sqrt{pq})}{\sqrt{p}\sqrt{pq}^{i-1}}$
(B.79)
$\displaystyle=\frac{\lambda}{\sqrt{p}}U_{i-1}(\lambda/\sqrt{pq})-\frac{1}{\sqrt{q}}U_{i-2}(\lambda/\sqrt{pq}),$

which is Eq. (4.33) in Lemma 4.1. We now consider $\|\ket{v_{\lambda}}\|^{2}$.
We first calculate the square of the $(i+1)$-th component. For simplicity we
denote $U_{i}(\lambda/\sqrt{pq})$ by $U_{i}$ in the following.

(B.80) $\displaystyle|\braket{i}{v_{\lambda}}|^{2}$
$\displaystyle=\frac{\lambda^{2}}{p}U_{i-1}^{2}-\frac{2\lambda}{\sqrt{pq}}U_{i-1}U_{i-2}+\frac{1}{q}U_{i-2}^{2}$
(B.81)
$\displaystyle=\frac{\lambda^{2}}{p}U_{i-1}^{2}+(U_{i}^{2}-\frac{\lambda^{2}}{pq}U_{i-1}^{2}-U_{i-2}^{2})+\frac{1}{q}U_{i-2}^{2}$
(B.82)
$\displaystyle=\frac{p}{q}U_{i-2}^{2}-\frac{\lambda^{2}}{q}U_{i-1}^{2}+U_{i}^{2}.$

The second line is obtained by squaring both sides of the relation
$U_{i}=\frac{\lambda}{\sqrt{pq}}U_{i-1}-U_{i-2}$ which follows from Eq.
(B.40). In order to make the relation true for $i\geq 1$, we set $U_{-1}:=0$.
Then, using the identity $p/q-\lambda^{2}/q+1=(1-\lambda^{2})/q$, we have

(B.83) $\displaystyle\|\ket{v_{\lambda}}\|^{2}/2$
$\displaystyle=1+\sum_{i=1}^{n}|\braket{i}{v_{\lambda}}|^{2}$ (B.84)
$\displaystyle=1+0+\frac{p}{q}-\frac{\lambda^{2}}{q}+\frac{1-\lambda^{2}}{q}\sum_{i=1}^{n-2}U_{i}^{2}-\frac{\lambda^{2}}{q}U_{n-1}^{2}+U_{n-1}^{2}+U_{n}^{2}$
(B.85)
$\displaystyle=\frac{1-\lambda^{2}}{q}+\frac{1-\lambda^{2}}{q}\sum_{i=1}^{n-2}U_{i}^{2}+(-\frac{\lambda^{2}}{q}+1+\frac{p}{q})U_{n-1}^{2}$
(B.86) $\displaystyle=\frac{1-\lambda^{2}}{q}\sum_{i=0}^{n-1}U_{i}^{2}.$

The third line uses Eq. (B.61) satisfied by the eigenvalue $\lambda$. From the
trigonometric expression of $U_{i}$ (Eq. (B.42)), we have

(B.87) $\displaystyle\sum_{i=0}^{n-1}U_{i}^{2}$
$\displaystyle=\frac{1}{\sin^{2}\theta}\sum_{i=0}^{n-1}\sin^{2}(i+1)\theta$
(B.88) $\displaystyle=\frac{1}{\sin^{2}\theta}\sum_{i=1}^{n}\frac{1-\cos
i2\theta}{2}$ (B.89) $\displaystyle=\frac{1}{2\sin^{2}\theta}(n-\frac{\sin
n\theta\cdot\cos(n+1)\theta}{\sin\theta})$ (B.90)
$\displaystyle=\frac{1}{2\sin^{2}\theta}(n\pm\sqrt{\frac{q}{p}}\frac{\sin
2(n+1)\theta}{2\sin\theta}).$

Hence combined with $\|\ket{u}\|^{2}=2(1-\lambda^{2})$ in Lemma B.1 and the
identity $\theta_{-k}=\pi-\theta_{k}$, we obtain Eq. (4.35) in Lemma 4.1. Note
that the last line above uses Eq. (4.31) satisfied by $\theta$. The third line
uses the identity obtained from comparing the real part of the following
identities:

(B.91) $\displaystyle\sum_{k=1}^{n}\cos kx+i\sin kx$ (B.92)
$\displaystyle=\sum_{k=1}^{n}e^{ikx}=\frac{e^{ix}(e^{inx}-1)}{e^{ix}-1}$
(B.93)
$\displaystyle=\frac{e^{ix}e^{\frac{inx}{2}}2i\sin\frac{nx}{2}}{e^{\frac{ix}{2}}2i\sin\frac{x}{2}}=\frac{\sin\frac{nx}{2}}{\sin\frac{x}{2}}e^{i\frac{(n+1)x}{2}}$
(B.94)
$\displaystyle=\frac{\sin\frac{nx}{2}}{\sin\frac{x}{2}}(\cos\frac{(n+1)x}{2}+i\sin\frac{(n+1)x}{2}).$

## Acknowledgements

We would like to thank Yongzhen Xu and Qingwen Wang for helpful discussions on
quantum walk search frameworks. We would also like to thank the reviewers for
suggestions which have improved the presentation of the paper.

## References

  * [1] Y. Aharonov, L. Davidovich, and N. Zagury.  “Quantum random walks”.  Phys. Rev. A 48, 1687–1690 (1993).
  * [2] J. Kempe.  “Quantum random walks: An introductory overview”.  Contemporary Physics 44, 307–327 (2003).
  * [3] Andris Ambainis.  “Quantum walks and their algorithmic applications”.  International Journal of Quantum Information 01, 507–518 (2003).
  * [4] Salvador Elías Venegas-Andraca.  “Quantum walks: a comprehensive review”.  Quantum Information Processing 11, 1015–1106 (2012).
  * [5] Karuna Kadian, Sunita Garhwal, and Ajay Kumar.  “Quantum walk and its application domains: A systematic review”.  Computer Science Review 41, 100419 (2021).
  * [6] Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous.  “One-dimensional quantum walks”.  In Proceedings of the 33rd ACM Symposium on Theory of Computing.  Pages 37–49.  (2001).
  * [7] Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh V. Vazirani.  “Quantum walks on graphs”.  In Proceedings of the 33rd ACM Symposium on Theory of Computing.  Pages 50–59.  (2001).
  * [8] M. Szegedy.  “Quantum speed-up of markov chain based algorithms”.  In 45th Annual IEEE Symposium on Foundations of Computer Science.  Pages 32–41.  (2004).
  * [9] Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha.  “Search via quantum walk”.  SIAM J. Comput. 40, 142–164 (2011).
  * [10] Hari Krovi, Frédéric Magniez, Maris Ozols, and Jérémie Roland.  “Quantum walks can find a marked element on any graph”.  Algorithmica 74, 851–907 (2016).
  * [11] Aleksandrs Belovs.  “Quantum walks and electric networks” (2013).  arXiv:1302.3143.
  * [12] Simon Apers, András Gilyén, and Stacey Jeffery.  “A Unified Framework of Quantum Walk Search”.  In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021).  Volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:13.  Dagstuhl, Germany (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [13] Andris Ambainis.  “Quantum walk algorithm for element distinctness”.  SIAM J. Comput. 37, 210–239 (2007).
  * [14] Harry Buhrman and Robert Spalek.  “Quantum verification of matrix products”.  In Proceedings of the Seventeenth ACM-SIAM Symposium on Discrete Algorithms.  Pages 880–889.  (2006).  url: http://dl.acm.org/citation.cfm?id=1109557.1109654.
  * [15] Frédéric Magniez, Miklos Santha, and Mario Szegedy.  “Quantum algorithms for the triangle problem”.  SIAM J. Comput. 37, 413–424 (2007).
  * [16] Frédéric Magniez and Ashwin Nayak.  “Quantum complexity of testing group commutativity”.  Algorithmica 48, 221–232 (2007).
  * [17] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman.  “Exponential algorithmic speedup by a quantum walk”.  In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing.  Page 59–68.  STOC ’03New York, NY, USA (2003). Association for Computing Machinery.
  * [18] Andrew M. Childs, Edward Farhi, and Sam Gutmann.  “An example of the difference between quantum and classical random walks”.  Quantum Information Processing 1, 35–43 (2002).
  * [19] Julia Kempe.  “Quantum random walks hit exponentially faster” (2002).  arXiv:quant-ph/0205083.
  * [20] Stacey Jeffery and Sebastian Zur.  “Multidimensional quantum walks”.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing.  Page 1125–1130.  STOC 2023New York, NY, USA (2023). Association for Computing Machinery.
  * [21] Andrew M. Childs and Daochen Wang.  “Can graph properties have exponential quantum speedup?” (2020).  arXiv:2001.10520.
  * [22] Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang.  “Symmetries, graph properties, and quantum speedups”.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS).  Pages 649–660.  (2020).
  * [23] G. Brassard and P. Hoyer.  “An exact quantum polynomial-time algorithm for simon’s problem”.  In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems.  Pages 12–23.  (1997).
  * [24] Zekun Ye, Yunqi Huang, Lvzhou Li, and Yuyi Wang.  “Query complexity of generalized simon’s problem”.  Information and Computation 281, 104790 (2021).
  * [25] Yusuke Ide, Norio Konno, Etsuo Segawa, and Xin-Ping Xu.  “Localization of discrete time quantum walks on the glued trees”.  Entropy 16, 1501–1514 (2014).
  * [26] Yosi Atia and Shantanav Chakraborty.  “Improved upper bounds for the hitting times of quantum walks”.  Phys. Rev. A 104, 032215 (2021).
  * [27] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  “Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics”.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing.  Page 193–204.  STOC 2019New York, NY, USA (2019). Association for Computing Machinery.
  * [28] Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang.  “Fixed-point quantum search with an optimal number of queries”.  Phys. Rev. Lett. 113, 210501 (2014).
  * [29] Stephen A. Fenner and Yong Zhang.  “A note on the classical lower bound for a quantum walk algorithm” (2003).  arXiv:quant-ph/0312230.
  * [30] Andrew M. Childs.  “On the relationship between continuous- and discrete-time quantum walk”.  Communications in Mathematical Physics 294, 581–603 (2010).
  * [31] A. Yu. Kitaev.  “Quantum measurements and the abelian stabilizer problem” (1995).  arXiv:quant-ph/9511026.
  * [32] Ethan Bernstein and Umesh Vazirani.  “Quantum complexity theory”.  In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing.  Page 11–20.  STOC ’93New York, NY, USA (1993). Association for Computing Machinery.
  * [33] Guanzhong Li and Lvzhou Li.  “Deterministic quantum search with adjustable parameters: Implementations and applications”.  Information and Computation 292, 105042 (2023).
  * [34] G. L. Long.  “Grover algorithm with zero theoretical failure rate”.  Phys. Rev. A 64, 022307 (2001).
  * [35] Lov K. Grover.  “A fast quantum mechanical algorithm for database search”.  In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing.  Page 212–219.  STOC ’96New York, NY, USA (1996). Association for Computing Machinery.
  * [36] “Evolution of the reduced state vector of DTQW on welded tree”.  https://www.bilibili.com/video/BV1kK411179r/.
  * [37] Camille Jordan.  “Essai sur la géométrie à $n$ dimensions”.  Bulletin de la Société Mathématique de France 3, 103–174 (1875).  url: http://eudml.org/doc/85325.
  * [38] Guanzhong Li and Lvzhou Li.  “Optimal exact quantum algorithm for the promised element distinctness problem” (2022).  arXiv:2211.05443.