# Derandomization of quantum algorithm for triangle finding

Guanzhong Li, Lvzhou Li
Institute of Quantum Computing and Software,
School of Computer Science and Engineering,
Sun Yat-sen University, Guangzhou 510006, China Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>(corresponding author)

###### Abstract

Derandomization is the process of taking a randomized algorithm and turning it
into a deterministic algorithm, which has attracted great attention in
classical computing. In quantum computing, it is challenging and intriguing to
derandomize quantum algorithms, due to the inherent randomness of quantum
mechanics. The significance of derandomizing quantum algorithms lies not only
in theoretically proving that the success probability can essentially be 1
without sacrificing quantum speedups, but also in experimentally improving the
success rate when the algorithm is implemented on a real quantum computer.

In this paper, we focus on derandomizing quanmtum algorithms for the triangle
sum problem (including the famous triangle finding problem as a special case),
which asks to find a triangle in an edge-weighted graph with $n$ vertices,
such that its edges sum up to a given weight. We show that when the graph is
promised to contain at most one target triangle, there exists a deterministic
quantum algorithm that either finds the triangle if it exists or outputs “no
triangle” if none exists. It makes $O(n^{9/7})$ queries to the edge weight
matrix oracle, and thus has the same complexity with the state-of-art bounded-
error quantum algorithm. To achieve this derandomization, we make full use
several techniques: nested quantum walks with quantum data structure,
deterministic quantum search with adjustable parameters, and dimensional
reduction of quantum walk search on Johnson graph.

##  1 Introduction

Randomized algorithms play an important role in computer science, as they can
be significantly efficient in some choice of computational resource for a lot
of basic computational problems, such as time for primality testing [1, 2, 3],
space for undirected s-t connectivity [4] and circuit depth for perfect
matching [5]. Since the polynomial-time deterministic algorithm for primality
testing [6] was proposed in 2004, the study of derandomization, i.e. the
question of whether it’s possible to come up with efficient deterministic
versions of randomized algorithms, has been attracting attention from the
academic community, see for instance, Refs. [7, 8, 9, 10, 11]. Indeed, a lot
of exciting works have been dedicated to derandomizing concrete randomized
algorithms, including the aforementioned primality testing [6], undirected s-t
connectivity [12] and perfect matching [13]. There are also entire books on
derandomization, see for instance, Refs. [14, 15, 16].

Because of the inherent randomness of quantum mechanics, most of the existing
quantum algorithms are randomized, i.e., have a probability of failure [17,
18, 19]. Derandomizing quantum algorithms seems difficult, with only few
quantum algorithms having been successfully derandomized (succeed with
certainty), such as deterministic quantum search [20, 21, 22, 23, 24] and
deterministic quantum algorithms for Simon’s problem [25] (and its
generalization [26]), element distinctness problem [27] and the welded tree
problem [28]. The significance of derandomizing quantum algorithms lies not
only in theoretically proving that the success probability can essentially be
1 without sacrificing quantum speedups, but also in experimentally improving
the success rate when the algorithm is implemented on a real quantum computer.
Thus, it is intriguing to find more quantum algorithms that allows
derandomization. In this paper we will focus on derandomizing quantum
algorithms for triangle finding and its generalization, an important and
extensively studied problem in quantum computing.

###  1.1 Triangle finding and its generalization

The triangle finding problem has been extensively studied in quantum
computing. It aims to find a triangle in an unknown graph with $n$ vertices,
making as few queries as possible to its adjacency matrix given as a black
box. Compared to the classical query complexity of $\Theta(n^{2})$, the
quantum query complexity of the problem has gradually improved from the
trivial $O(n^{3/2})$ using Grover search on triples of the graph’s vertices,
to the state-of-the-art $O(n^{5/4})$ using extended learning graph [29].

The first improvement over $O(n^{3/2})$ was given by Buhrman et al. [30] for
sparse graph with $m=o(n^{2})$ edges, as they presented a quantum algorithm
for the triangle finding problem with query complexity $O(n+\sqrt{nm})$ using
amplitude amplification. Using combinatorial ideas and amplitude
amplification, Szegedy [31] (see also [32]) showed how to solve the problem
with query complexity $\widetilde{O}(n^{10/7})$, where $\widetilde{O}(\cdot)$
hides logarithmic factors. Magniez et al. [32] then utilized quantum walk
search on Johnson graphs, which was originally used to construct an optimal
quantum algorithm for the element distinctness problem [33], to obtain a more
efficient algorithm with $\widetilde{O}(n^{13/10})$ queries. Belovs [34]
introduced the learning graph framework and, as the first application of this
framework, used it to improve the quantum query complexity of triangle finding
to $O(n^{35/27})$. Lee et al. [35] then further improved the query complexity
to $O(n^{9/7})$, again using learning graph. Finally, Le Gall [36] gave a
$\widetilde{O}(n^{5/4})$ quantum algorithm, which utilizes combinatorial
structure of the problem, quantum walk search on Johnson graph, and variable
time quantum search. The logarithmic factors in $\widetilde{O}(n^{5/4})$ was
later removed using extended learning graphs by Carette et al. [29].

As can be seen from the above progress, each improvement in the query
complexity of triangle finding problem has brought deeper insight into the
problem or stimulating new algorithmic technique (See [37] for a more detailed
review). However, the gap between $O(n^{5/4})$ and $\Omega(n)$ is still open.
At the same time, all the above quantum algorithms are bounded-error, that is,
have a probability of failure.

In the above process, Belovs and Rosmanis [38] found that the $O(n^{9/7})$
algorithm by Lee et al. [35] based on non-adaptive learning graph can in fact
solve a more general problem — the triangle sum problem, in which the
underlying graph is now edge-weighted and the goal is to find a target
triangle whose edges sum to a given value. They also showed that the algorithm
is almost optimal by giving a matching lower bound of
$\Omega(n^{9/7}/\sqrt{\log n})$. Jeffery et al. [39] then proposed a new
nested quantum walk with quantum data structures, which is based on the MNRS
framework [40], and as an application they adapted Lee et al.’s algorithm [35]
to a quantum-walk-based algorithm. However, in order to reduce errors when
nesting the bounded-error subroutines, the algorithm makes
$\widetilde{O}(n^{9/7})$ queries with additional log factors.

###  1.2 Our contribution

In this paper, we propose a deterministic quantum algorithm for the triangle
sum problem (and thus also for the famous triangle finding problem), based on
derandomization of the quantum-walk-based algorithm by Jeffery et al. [39].
Our algorithm has the same $O(n^{9/7})$ query complexity with the state-of-
the-art bounded-error quantum algorithm by Lee et al. [35], but we require an
additional promise that the graph has at most one target triangle. Apart from
nested quantum walks with quantum data structures [39], our algorithm also
utilizes deterministic quantum search with adjustable parameters [24] (see
Section 2.3 and especially Lemma 3), and a technique to reduce the dimension
of invariant subspaces of quantum walk search on Johnson graph (see Section
2.2 and especially Lemma 1), which has also found application in designing a
deterministic quantum algorithm for the element distinctness problem [27]. We
think our algorithm has the following significance:

  1. 1.

It’s the first deterministic quantum algorithm for the triangle sum (and also
triangle finding) problem making $O(n^{9/7})$ queries, and provides a new
example of deranomization of quantum algorithms.

  2. 2.

It shows the usefulness of the techniques being utilized, and it’s likely that
more applications will be found.

Formal statement of the triangle sum problem. Consider an undirected and
weighted simple graph $G$ with $n$ vertices, specified by its edge weight
matrix $A\in[M]^{n\times n}$, where $M$ is a positive integer and
$[M]:=\\{0,1,\cdots,M-1\\}$. The edge weight matrix $A$ can be accessed
through a quantum black box (oracle) $O$ whose effect on the computational
basis is as follows:

$O\ket{i,j}\ket{b}\mapsto\ket{i,j}\ket{b\oplus A_{i,j}},$ (1)

where $(i,j)\in[n]\times[n]$ encodes an edge of $G$ to be queried, and
$A_{i,j}\in[M]$ is the corresponding weight. Suppose the value $A_{i,j}$ is
stored in $m$ qubits, then $\oplus$ denotes bit-wise XOR and $O^{2}=I$.

######  Definition 1 (the triangle sum problem).

Given $d\in[M]$, find three vertices $a,b,c\in[n]$ in the graph $G$ such that

$A_{a,b}+A_{b,c}+A_{c,a}=d\mod{M},$ (2)

making as few queries to the oracle $O$ as possible.

The triangle sum promised problem has an additional promise that if such a
target triangle $\triangle abc$ exists in $G$, there is only one.

In this paper we obtain the following result.

######  Theorem 1.

There is a deterministic quantum algorithm that solves the triangle sum
promised problem with certainty and making $O(n^{9/7})$ queries.

Specifically, the algorithm outputs the target triangle if it exists and
claims there’s none if no such triangle exists.

######  Corollary 1.

There is a deterministic quantum algorithm for triangle finding which makes
$O(n^{9/7})$ queries.

###### Proof.

Triangle finding is a special case of the triangle sum problem, which can be
seen by setting $M=4,d=3$ and restricting $A$ to $[2]^{n\times n}$. Thus,
quantum algorithm solving the triangle sum problem also solves triangle
finding. ∎

Note that the addition in Eq. (2) is modulo $M$, which is crucial in proving
the $\Omega(n^{9/7}/\sqrt{\log n})$ lower bound of the triangle sum problem
[38]. Intuitively, ‘addition modulo $M$’ makes it impossible for an algorithm
to rule out potential triangle, say $\triangle a^{\prime}b^{\prime}c^{\prime}$
in $G$, when the queried edge weights $A_{a^{\prime},b^{\prime}}$ and
$A_{b^{\prime},c^{\prime}}$ already sum up to greater than $d$ or either of
them is zero. A more formal description of this property can be found in [41,
38] referred to as the orthogonal array condition or the orthogonality
property.

###  1.3 Paper organization

The rest of the paper is organized as follows. In Section 2 we introduce some
important techniques that will be used later: two forms of quantum walk search
on Johnson graph dubbed “edge-walk” and “vertex-walk”, a technique to reduce
the dimension of the invariant subspace of quantum vertex-walk on Johnson
graph, and deterministic quantum search with adjustable parameters. In Section
3, we first sketch the procedure of our algorithm which contains four layers
of subroutines in Section 3.1, and then show that each layer of subroutine can
be derandomized in Section 3.2, thus obtaining a deterministic quantum
algorithm for the triangle sum promised problem. The details of the quantum
walk search on Johnson graph used in three of the four layers, i.e. how to
implement the setup, update, checking operations and what is the probability
of reaching the target state, are presented in Section 4. We conclude this
paper with some related problems in Section 5.

##  2 Preliminaries

In this section, we present some techniques and results that will be used
latter in our deterministic quantum algorithm for the triangle sum promised
problem. We will use two forms of quantum walks search on Johnson graph with
subtle differences. The first one described in Section 2.1 stems from the
nested quantum walk [39], and we call it “quantum edge-walk on Johnson graph”,
since its basis state $\ket{R}\ket{R^{\prime}}$ can be seen as an edge of a
Johnson graph. The second one described in Section 2.2 originates from
Ambainis’ quantum walks for the element distinctness problem [33], and we call
it “quantum vertex-walk on Johnson graph”, since in its basis state
$\ket{R,y}$, $\ket{R}$ can be seen as a vertex of a Johnson graph and
$\ket{y}$ as a coin used to update $\ket{R}$.

In Section 2.2 we will also introduce a technique (Lemma 1) to reduce the
dimension of the invariant subspace of quantum vertex-walk on Johnson graph,
when certain conditions (Condition 1) are satisfied. In order to achieve
certainty of success, we will also need deterministic quantum search (with
adjustable parameters) as described in Section 2.3.

###  2.1 Quantum edge-walk search on Johnson graph

A Johnson graph $J(N,r)$ has $\binom{N}{r}$ vertices. Each vertex is a subset
$R\subseteq[N]$ of size $r$, and two vertices $R,R^{\prime}$ are connected by
an edge if and only if $|R\cap R^{\prime}|=r-1$. We denote by $V(G)$ the
vertex set of $G:=J(N,r)$.

The quantum edge-walk on $G$ has state space
$\\{\ket{R}\ket{R^{\prime}}\ket{D(R)}:R,R^{\prime}\in V(G)\\}$. The data
$D(R)$ associated with $R$ relies on the input of the problem to be solved,
and we check if a vertex $R$ is marked based on whether $D(R)$ satisfies
certain condition. The goal of quantum walk search on $G$ is to obtain a
marked vertex with constant probability, starting from an initial state
$\ket{\psi_{0}}$ and using update operations that comply with the graph’s
edges (i.e. to walk on the graph). Specifically, the quantum edge-walk on $G$
consists of the following three operations.

Setup. Denote by $S$ the Setup operation that transforms the all zero state to
the initial state:

$\ket{\psi_{0}}=S\ket{0},$ (3)

where $\ket{\psi_{0}}$ is an equal superposition of all the edges in $G$:

$\ket{\psi_{0}}=\frac{1}{\sqrt{\binom{N}{r}}}\sum_{R}\ket{R}\frac{1}{\sqrt{r(N-r)}}\sum_{R\to
R^{\prime}}\ket{R^{\prime}}\ket{D(R)},$ (4)

where $R\to R^{\prime}$ means $R^{\prime}$ is adjacent to $R$ in $G$, or
equivalently $|R\cap R^{\prime}|=r-1$.

Update. One step of quantum walk, denoted by the update operation $U$,
consists of three unitary operators:

$U=\mathrm{Data}\cdot\mathrm{Swap}\cdot\mathrm{Coin},$ (5)

where ‘Coin’ acting on $\ket{R}\ket{R^{\prime}}$ is the Grover diffusion of
vertices adjacent to $\ket{R}$:

$\displaystyle\mathrm{Coin}$
$\displaystyle=\sum_{R}\ket{R}\bra{R}\otimes\big{(}2\ket{\varphi(R)}\bra{\varphi(R)}-I\big{)},$
(6) $\displaystyle\ket{\varphi(R)}$
$\displaystyle=\frac{1}{\sqrt{r(N-r)}}\sum_{R\to R^{\prime}}\ket{R^{\prime}},$
(7)

and

$\displaystyle\mathrm{Swap}\ket{R}\ket{R^{\prime}}=\ket{R^{\prime}}\ket{R},$
(8)
$\displaystyle\mathrm{Data}\ket{R^{\prime}}\ket{R}\ket{D(R)}=\ket{R^{\prime}}\ket{R}\ket{D(R^{\prime})}.$
(9)

Checking. The checking subroutine $C$ adds phase shift $(-1)$ to
$\ket{R}\ket{R^{\prime}}\ket{D(R)}$, if the associated data $\ket{D(R)}$
satisfies certain condition.

The whole process of quantum walk search on $G$ can be formulated in the
following equation

$\ket{\psi_{k}}=(U^{\sqrt{r}}C)^{k}S\ket{0}.$ (10)

The process is similar to Grover’s algorithm, as $U^{\sqrt{r}}$ can be seen as
a reflection through the initial state $\ket{\psi_{0}}$ and $C$ as a
reflection through the marked states. It should be noted that the
$U^{\sqrt{r}}$ we used in this paper is replaced with phase estimation and
selected $(-1)$ phase shift in [39, 40]. Finally, by choosing an appropriate
$k$ and measuring $\ket{\psi_{k}}$ in the first register, we will obtain a
marked vertex with constant probability.

###  2.2 Quantum vertex-walk search on Johnson graph

The quantum vertex-walk search on Johnson graph $J(N,r)$ has state space
$\\{\ket{R,y}\ket{D(R)}:R\subseteq[N],y\in[N]-R\\}$.

Setup. The initial state is

$\ket{\psi_{0}}=\frac{1}{\sqrt{\binom{N}{r}}}\sum_{R}\ket{R}\ket{D(R)}\frac{1}{\sqrt{N-r}}\sum_{y\in[N]-R}\ket{y}.$
(11)

Update. One step of quantum walk $U$ consists of two unitary operators:
$U=U_{B}(\theta_{2})U_{A}(\theta_{1})$. The first operator $U_{A}(\theta_{1})$
acts on $\ket{R,y}$, and can be seen as choosing a random $y\in[N]-R$ to be
moved into $R$:

$\displaystyle U_{A}(\theta_{1})$
$\displaystyle=\sum_{R}\ket{R}\bra{R}\otimes\big{(}I-(1-e^{i\theta_{1}})\ket{\varphi(R)}\bra{\varphi(R)}\big{)},$
(12) $\displaystyle\ket{\varphi(R)}$
$\displaystyle=\frac{1}{\sqrt{N-r}}\sum_{y\in[N]-R}\ket{y}.$ (13)

The second operator $U_{B}(\theta_{2})$ can be seen as choosing a random
$y^{\prime}\in R$ being removed from $R$ and at the same time moving $y$ into
$R$. To update $D(R)$ simultaneously, $U_{B}(\theta_{2})$ acts on all
registers, but we only define its effect on register $\ket{R,y}$ for
simplicity:

$\displaystyle U_{B}(\theta_{2})$
$\displaystyle=I-(1-e^{i\theta_{2}})\sum_{R+y\subseteq[N]}\ket{\varphi(R+y)}\bra{\varphi(R+y)},$
(14) $\displaystyle\ket{\varphi(R+y)}$
$\displaystyle=\frac{1}{\sqrt{r+1}}\sum_{y^{\prime}\in
R+y}\ket{R+y-y^{\prime},y^{\prime}}.$ (15)

Note that we enhance the original update operation from [33] with general
phase shift $e^{i\theta}$ instead of $(-1)$, in order to achieve dimensional
reduction of the walk’s invariant subspace.

Checking. The checking subroutine $S_{\mathcal{M}}(\alpha)$ adds relative
phase shift $e^{i\alpha}$ to a marked state $\ket{R,y}\ket{D(R)}$, based on
whether the associated data $\ket{D(R)}$ satisfies certain condition. In fact,
$S_{\mathcal{M}}(\alpha)$ can be implemented by
$C(I\otimes\mathrm{diag}(1,e^{i\alpha}))C$, if there is a checking subroutine
$C$ that flips an auxiliary qubit initialized with $\ket{0}$, when the basis
state is marked.

5-dimensional invrariant subspace $\mathcal{H}_{0}$. Suppose the Checking
subroutine $C$ satisfies the following condition:

######  Condition 1.

There is a special subset $K\subseteq[N]$ with $|K|=2$, such that for a
certain $(j_{0},l_{0})\in\\{(j,0)\\}_{j=0}^{2}\cup\\{(j,1)\\}_{j=0}^{1}$, the
checking subroutine $C$ marks a basis state $\ket{R,y}$ satisfying $|R\cap
K|=j_{0}$ and $|y\cap K|=l_{0}$.

Then the quantum vetex-walk search on $J(N,r)$ can be reduced to a
$5$-dimensional invariant subspace $\mathcal{H}_{0}$ spanned by:

$\mathcal{B}_{0}:=\\{\ket{0,0},\ket{0,1},\ket{1,0},\ket{1,1},\ket{2,0}\\},$
(16)

where $\ket{j,l}\in\mathcal{B}_{0}$ is the equal superposition of basis states
in $S_{j}^{l}:=\\{\ket{R,y}:|R\cap K|=j,|y\cap K|=l\\}$. In basis
$\mathcal{B}_{0}$, the initial state takes the following form:

$\ket{\psi_{0}}=\frac{1}{\sqrt{\binom{N}{r}(N-r)}}\sum_{\ket{j,l}\in\mathcal{B}_{0}}\sqrt{|S_{j}^{l}|}\cdot\ket{j,l},$
(17)

and the target state is $\ket{j_{0},l_{0}}$.

Because $S_{j}^{l}$ can also be seen as the set of $\ket{R,y}$ satisfying
$|(R+y)\cap K|=j+l$ and $|y\cap K|=l$, the size of $S_{j}^{l}$ can be
calculated in two ways. For $\\{\ket{j,0}\\}_{j=0}^{2}$, we have:

$\binom{2}{j}\binom{N-2}{r-j}(N-2-(r-j))=|S_{j}^{0}|=\binom{2}{j}\binom{N-2}{r+1-j}(r+1-j),$
(18)

and for $\\{\ket{j,1}\\}_{j=0}^{1}$, we have:

$\binom{2}{j}\binom{N-2}{r-j}(2-j)=|S_{j}^{1}|=\binom{2}{j+1}\binom{N-2}{r-j}(j+1).$
(19)

This is depicted in Fig. 1 by the two equivalent ways (from left or from
right) of calculating the weight of the middle line marked by $\ket{j,l}$ with
dashed box.

Figure 1: Illustration of the 5 basis states $\ket{j,l}\in\mathcal{B}_{0}$ of
the invariant subspace $\mathcal{H}_{0}$. The two equivalent ways of
calculating $|S_{j}^{l}|$ is depicted by the two ways of calculating the
weights of the lines.

From Fig. 1 and the definition of $U_{A}(\theta_{1})$ and $U_{B}(\theta_{2})$,
it can be seen that $U=U_{B}(\theta_{2})U_{A}(\theta_{1})$ takes the following
form in $\mathcal{B}_{0}$:

$\displaystyle U$
$\displaystyle=(I-(1-e^{i\theta_{2}})BB^{\dagger})\cdot(I-(1-e^{i\theta_{1}})AA^{\dagger}),$
(20) $\displaystyle A.^{2}$
$\displaystyle=\left[\begin{array}[]{ccc}{1-\frac{2}{N-r}}&0&0\\\
{\frac{2}{N-r}}&0&0\\\ 0&{1-\frac{1}{N-r}}&0\\\ 0&{\frac{1}{N-r}}&0\\\
0&0&1\end{array}\right],\quad B.^{2}=\left[\begin{array}[]{ccc}1&0&0\\\
0&\frac{1}{r+1}&0\\\ 0&1-\frac{1}{r+1}&0\\\ 0&0&\frac{2}{r+1}\\\
0&0&1-\frac{2}{r+1}\end{array}\right],$ (31)

where $A,B$ are non-negative matrices, and $A.^{2}$ denotes the entry wise
square of $A$.

Reducing the dimension further to 2. We can now state the following Lemma 1
due to Lemmas 1 and 2 in Ref. [27].

######  Lemma 1.

By setting the parameters $(\theta_{1},\theta_{2})$ in
$U=U_{B}(\theta_{2})U_{A}(\theta_{1})$ and $t\in O(\sqrt{r})$ appropriately,
$U^{t}$ becomes a phase shift of the initial state in $\mathcal{H}_{0}$:

$U^{t}=I-(1-e^{i\beta})|{\psi_{0}}\rangle\langle{\psi_{0}}|.$ (32)

Furthermore, the angle $\beta=t\frac{\theta_{1}+\theta_{2}}{2}\ {\rm mod}\
2\pi$ is known and $\beta\approx 1.29\pi$ when $N\to\infty$.

Thus the invariant subspace of quantum vertex-walk search on $J(N,r)$,
formulated in the following equation:

$\ket{\psi_{k}}=\big{(}U^{t}S_{\mathcal{M}}(\alpha)\big{)}^{k}\ket{\psi_{0}},$
(33)

further reduces to $2$-dimensional spanned by $\ket{\psi_{0}}$ and the target
state $\ket{j_{0},l_{0}}$.

###  2.3 Deterministic quantum search with adjustable parameters

Suppose there is a quantum process (unitary operation) $\mathcal{A}$ that
transforms the all zero state $\ket{0}$ to $\ket{\psi_{0}}$, which contains a
set of target basis states $\mathcal{M}:=\\{\ket{t}\\}$. Denote by
$\Pi_{\mathcal{M}}:=\sum_{\ket{t}\in\mathcal{M}}\ket{t}\bra{t}$ the projection
onto $\mathrm{span}(\mathcal{M})$. If the success probability of measuring
$\ket{\psi_{0}}$ that leads to a target state, i.e.
$\lambda:=\|\Pi_{\mathcal{M}}\ket{\psi_{0}}\|^{2}$ is known beforehand. Then
we can transform $\ket{\psi_{0}}$ to
$\ket{\mathcal{M}}:=\frac{1}{\sqrt{|\mathcal{M}|}}\sum_{\ket{t}\in\mathcal{M}}\ket{t}$
with certainty, by iterating the generalized Grover’s operation
$G(\alpha,\beta)$ for $O(1/\sqrt{\lambda})$ times:

$\displaystyle G(\alpha,\beta)$ $\displaystyle:=S_{\psi_{0}}(\beta)\cdot
S_{\mathcal{M}}(\alpha)$ (34)
$\displaystyle:=e^{-i\beta\ket{\psi_{0}}\bra{\psi_{0}}}\cdot
e^{i\alpha\Pi_{\mathcal{M}}}$ (35)
$\displaystyle=(\mathcal{A}e^{-i\beta\ket{0}\bra{0}}\mathcal{A}^{\dagger})\cdot
e^{i\alpha\Pi_{\mathcal{M}}}.$ (36)

If the two parameters $\alpha,\beta$ are user-controllable, there are at least
three schemes to achieve deterministic quantum search [20, 21, 22]. But the
following lemma due to Long [22] is most concise.

######  Lemma 2 ([22]).

Suppose parameter $\alpha$ satisfies the equation
“$\sin\frac{\pi}{4k+2}=\sqrt{\lambda}\sin\frac{\alpha}{2}$”, and integer
$k>k_{\mathrm{opt}}$, then

$\left|\bra{\mathcal{M}}[G(\alpha,-\alpha)]^{k}\ket{\psi_{0}}\right|=1.$ (37)

The lower bound of number of iterations $k$ is

$k_{\mathrm{opt}}=\frac{\pi}{4\arcsin\sqrt{\lambda}}-\frac{1}{2}.$ (38)

If one of the parameters, for example $\beta$, is uncontrollable but fixed and
known, we can apply the following lemma from [24, Theorem 2].

######  Lemma 3.

Suppose $\beta\in(0,2\pi)$ is arbitrarily given, and $k>k_{\mathrm{lower}}$,
then there always exits a pair of parameters $(\alpha_{1},\alpha_{2})$ such
that

$\left|\bra{\mathcal{M}}[G(\alpha_{1},\beta)G(\alpha_{2},\beta)]^{k}\ket{\psi_{0}}\right|=1.$
(39)

The lower bound of $k$ is

$k_{\mathrm{lower}}=\frac{\pi}{\Big{|}4\arcsin(\sqrt{\lambda}\sin\frac{\beta}{2})\mod[-\frac{\pi}{2},\frac{\pi}{2}]\Big{|}}\in
O(1/\sqrt{\lambda}),$ (40)

where the notation “$x\mod[-\frac{\pi}{2},\frac{\pi}{2}]$” means to add $x$
with an appropriate integer multiples $l$ of $\pi$, such that
$x+l\pi\in[-\frac{\pi}{2},\frac{\pi}{2}]$.

The explicit equations that $(\alpha_{1},\alpha_{2})$ need to satisfy in Lemma
3 can be found in [24].

##  3 Deterministic quantum algorithm for the triangle sum promised problem

Since our algorithm for the promised problem of triangle sum (Definition 1) is
based on the derandomization of Jeffery et al.’s algorithm [39], it also has
$4$ layers of subroutines as described in Section 3.1. We show the
derandomization of each layer in Section 3.2, and thus obtain a deterministic
quantum algorithm and complete the proof of Theorem 1.

###  3.1 Outline and query complexity

Recall that in the triangle sum problem, we are trying to find a triangle
whose edges sum up to a given weight $d$ modulo $M$ in an edge-weighted graph
$G$ with $n$ vertices, by querying its edge weight matrix $A\in[M]^{n\times
n}$ as few times as possible (through oracle $O$ in Eq. (1)).

Our algorithm has $4$ layers of subroutines: layers $1,2,4$ are quantum walk
search on Johnson graph, and layer $3$ is a Grover search. Each layer
implements the Check operation of its upper layer. Intuitively, layer $1$,
$2$, and $(3,4)$ as a whole, find one by one, three vertices in the target
triangle $\triangle abc:=\triangle$.

Denote by $S_{i},U_{i},C_{i}$ the setup, update, checking operation in the
$i$-th layer, the query complexity of implementing the respective operations
from the oracle $O$ are denoted by $s_{i},u_{i},c_{i}$. We also denote by
$\epsilon_{i}$ the proportion of marked vertices in $V(G_{i})$, where $G_{i}$
is the Johnson graph in the $i$-th layer. For two subsets $R_{1}$ and $R_{2}$
of graph $G$’s vertex set $[n]$, denote by $G_{R_{1},R_{2}}$ the sub-matrix of
the edge weight matrix $A$ with rows indexed by $R_{1}$ and columns indexed by
$R_{2}$.

The 4 layers of subroutines are listed below.

  1. 1.

A quantum edge-walk search on Johnson graph $G_{1}=J(n,r_{1})$. We set
$r_{1}=n^{4/7}$ so that the total query complexity $c_{0}$ is $n^{9/7}$ as
shown by Eq. (52) (See [39] for why setting $r_{1}=n^{4/7}$, and
$r_{2}=n^{5/7},m=n^{3/7}$ below). A basis state
$\ket{R_{1}}\ket{R_{1}^{\prime}}\ket{D(R_{1})}$ is marked if
$|R_{1}\cap\triangle|=1$ and $|R_{1}^{\prime}\cap\triangle|=1$. The query
complexity is (with big $O$ omitted)

$\displaystyle c_{0}$
$\displaystyle:=s_{1}+\frac{1}{\sqrt{\epsilon_{1}}}(\sqrt{r_{1}}u_{1}+c_{1})$
(41)
$\displaystyle=r_{1}r_{2}+\sqrt{\frac{n}{r_{1}}}(\sqrt{r_{1}}(r_{1}+r_{2})+c_{1}),$
(42)

where the value of $s_{1}$ and $u_{1}$ will be explained below. The checking
operation $C_{1}$ which checks if $\ket{R_{1}}\ket{R_{1}^{\prime}}$ is marked,
is implemented in layer 2 (see also Section 3.2).

  2. 2.

A quantum vertex-walk search on Johnson graph $G_{2}=J(n_{1},r_{2})$, where
$n_{1}=n-r_{1}$, and we set $r_{2}=n^{5/7}$. A basis state
$\ket{R_{1}}\ket{R_{2},y}\ket{G_{R_{1},R_{2}}}$, where
$R_{2}\subseteq[n]-R_{1}$ and $y\in[n]-R_{1}-R_{2}$, is marked if
$|R_{1}\cap\triangle|=1$, $|R_{2}\cap\triangle|=1$ and $y\notin\triangle$. To
avoid the intolerable Setup cost $s_{2}=r_{1}r_{2}$ to construct
$\ket{G_{R_{1},R_{2}}}$, nested quantum walks with quantum data structure [39]
are used. That is, the data $D(R_{1})$ associated with $\ket{R_{1}}$ in layer
1 is the partial initial state (but $\ket{y}$ is not initialized) of layer 2:

$\ket{D(R_{1})}=\frac{1}{\sqrt{\binom{n_{1}}{r_{2}}}}\sum_{R_{2}\subseteq[n]-R_{1}}\ket{R_{2}}\ket{G_{R_{1},R_{2}}},$
(43)

where the data $\ket{G_{R_{1},R_{2}}}$ stores $G_{R_{1},R_{2}}$ in a
$r_{1}\times r_{2}$ matrix of registers. Therefore, to maintain this data
structure, the setup cost in layer 1 is $s_{1}=r_{1}r_{2}$, and
$u_{1}=2(r_{1}+r_{2})$ so as to implement $D(R_{1})\mapsto D(R_{1}^{\prime})$
based on $\ket{R_{1}^{\prime}}\ket{R_{1}}$ (see Lemma 5). Also, $s_{2}=0$, and
$u_{2}=2r_{1}$ so as to implement $G_{R_{1},R_{2}}\mapsto
G_{R_{1},R_{2}^{\prime}}$. Thus, the query complexity of this layer is

$\displaystyle c_{1}$
$\displaystyle=s_{2}+\frac{1}{\sqrt{\epsilon_{2}}}(\sqrt{r_{2}}u_{2}+c_{2})$
(44) $\displaystyle=0+\sqrt{\frac{n}{r_{2}}}(\sqrt{r_{2}}r_{1}+c_{2}).$ (45)

The checking operation $C_{2}$ which checks if $\ket{R_{2},y}$ is marked, is
implemented in layer 3.

  3. 3.

A Grover search on $[n]-R_{1}-R_{2}-y$ to find the last vertex
$c\in\triangle$, assuming $R_{1}\cap\triangle=a$ and $R_{2}\cap\triangle=b$.
The query complexity of this layer is

$c_{2}=\sqrt{n}c_{3}.$ (46)

The checking operation $C_{3}$ which checks if $z\in[n]-R_{1}-R_{2}-y$ is the
last vertex $c\in\triangle$, is implemented in layer 4.

  4. 4.

A quantum vertex-walk search on the product Johnson graph
$G_{4}=J(r_{1},m)\times J(r_{2},m)$ with vertex set
$V(G_{4})=\\{\ket{S_{1}}\ket{S_{2}}:S_{i}\subseteq R_{i},|S_{i}|=m\\}$. We set
$m=(r_{1}r_{2})^{1/3}=n^{3/7}$. Vertices $\ket{S_{1}}\ket{S_{2}}$ and
$\ket{S_{1}^{\prime}}\ket{S_{2}^{\prime}}$ are adjacent if $|S_{i}\cap
S_{i}^{\prime}|=m-1$ for $i=1,2$. The data associated with $\ket{S_{i}}$ is
$G_{S_{i},z}$. Assuming $R_{1}\cap\triangle=a$, $R_{2}\cap\triangle=b$ and
$z=c$, vertex $\ket{S_{1}}\ket{S_{2}}$ is marked if $a\in S_{1},b\in S_{2}$.
The query complexity of this layer is

$\displaystyle c_{3}$
$\displaystyle=s_{4}+\frac{1}{\sqrt{\epsilon_{4}}}(\sqrt{m}u_{4}+c_{4})$ (47)
$\displaystyle=m+\frac{\sqrt{r_{1}r_{2}}}{m}(\sqrt{m}\cdot O(1)+0).$ (48)

The checking operation $C_{4}$ flips an auxiliary qubit if there exists $a\in
S_{1},b\in S_{2}$ such that $A_{a,b}+A_{b,c}+A_{a,c}=d\,(\mathrm{mod}\,M)$.
Since $A_{a,b}\in G_{R_{1},R_{2}},A_{b,c}\in G_{S_{1},c},A_{a,c}\in
G_{S_{2},c}$ are already stored in the data structures, $C_{4}$ requires no
oracle query.

We can now calculate the total query complexity as follows:

$\displaystyle c_{3}$ $\displaystyle=(r_{1}r_{2})^{1/3}=n^{3/7},$ (49)
$\displaystyle c_{2}$ $\displaystyle=\sqrt{n}c_{3}=n^{6.5/7},$ (50)
$\displaystyle c_{1}$ $\displaystyle=n^{1/7}(n^{6.5/7}+c_{2})=n^{7.5/7},$ (51)
$\displaystyle c_{0}$ $\displaystyle=n^{9/7}+n^{1.5/7}(n+c_{1})=n^{9/7}.$ (52)

###  3.2 Proof of Theorem 1

The condition that $R_{1},R_{2},y,z$ are mutually disjoint, and the promise
that there’s at most one target triangle, enable us to implement the checking
operation $C_{3}$, $C_{2}$ and then $C_{1}$ with 100% success probability
successively as shown below.

Implementing $C_{3}$ with 100% success probability. We consider $C_{3}$
implemented in layer 4 first, whose checking operation $C_{4}$ does not rely
on other layer. The input state of this layer is
$\ket{R_{1}}\ket{R_{2}}\ket{z}$, and the quantum walk basis state is
$\ket{S_{1}}\ket{S_{2}}$ with $S_{i}\subseteq R_{i}$. From the definition of
the checking operation $C_{4}$, we can see that only when the input state
$\ket{R_{1}}\ket{R_{2}}\ket{z}$ satisfies $|R_{1}\cap\triangle|=1$,
$|R_{2}\cap\triangle|=1$ and $|z\cap\triangle|=1$, dose $C_{4}$ not
degenerates to the identity operator $I$. In this special case, the quantum
walk process $(U^{t_{1}}C_{4})^{t_{2}}\ket{\psi_{0}}$ can be reduced to a
$9$-dimensional invariant subspace as shown in Section 4.1. Setting
$t_{1}=\Theta(\sqrt{m})$ and $t_{2}=\Theta(\sqrt{r_{1}r_{2}}/m)$, the success
amplitude $p=|\bra{t}(U^{t_{1}}C_{4})^{t_{2}}\ket{\psi_{0}}|=\Omega(1)$ by
Lemma 4, where the target state $\ket{t}$ is an equal superposition of
$\ket{S_{1}}\ket{S_{2}}$ with $a\in S_{1},b\in S_{2}$ (assuming $a\in
R_{1},b\in R_{2}$), and $p$ can be computed exactly beforehand. Thus combined
with Lemma 2, we can obtain $\ket{t}$ with certainty. Denote by
$\mathcal{A}_{4}$ the above process that on input state
$\ket{R_{1}}\ket{R_{2}}\ket{z}$, implements $\ket{0}\mapsto\ket{t}$. Then
applying $C_{4}$ once more we can flip an auxiliary qubit with certainty. Thus
$\mathcal{A}_{4}^{\dagger}C_{4}\mathcal{A}_{4}$ implements $C_{3}$ with 100%
success probability, and it acts nontrivially when $|R_{1}\cap\triangle|=1$,
$|R_{2}\cap\triangle|=1$ and $|z\cap\triangle|=1$.

Implementing $C_{2}$ with 100% success probability. The input state of layer 3
is $\ket{R_{1}}\ket{R_{2},y}$, and the search space is
$z\in[n]-R_{1}-R_{2}-y$. Thus combined with the effect of $C_{3}$ shown above,
we can see that only when the input state $\ket{R_{1}}\ket{R_{2},y}$ satisfies
$|R_{1}\cap\triangle|=1$, $|R_{2}\cap\triangle|=1$ and $y\notin\triangle$,
does $C_{3}\neq I$. In this special case, suppose $a\in R_{1},b\in R_{2}$,
then the only target $t\in[n]-R_{1}-R_{2}-y$ is $c\in\triangle$. Therefore,
using the deterministic quantum search shown by Lemma 2, we can obtain
$\ket{t}$. Denote by $\mathcal{A}_{3}$ the above process that on input state
$\ket{R_{1}}\ket{R_{2},y}$, implements $\ket{0}\mapsto\ket{t}$. Then applying
$C_{3}$ once more we can flip an auxiliary qubit with certainty, and thus
$\mathcal{A}_{3}^{\dagger}C_{3}\mathcal{A}_{4}$ implements $C_{2}$ with 100%
success probability, which acts nontrivially when $|R_{1}\cap\triangle|=1$,
$|R_{2}\cap\triangle|=1$ and $y\notin\triangle$.

Implementing $C_{1}$ with 100% success probability. Recall that we want
$C_{1}$ to act nontrivially on $\ket{R_{1}}\ket{R_{1}^{\prime}}\ket{D(R_{1})}$
when $|R_{1}\cap\triangle|=1$ and $|R_{1}^{\prime}\cap\triangle|=1$. We will
implement $C_{1}$ from $\bar{C}_{1}$, which acts nontrivially on
$\ket{R_{1}}\ket{D(R_{1})}$ when $|R_{1}\cap\triangle|=1$. The implementation
of $C_{1}$ from $\bar{C}_{1}$ is described in Section 4.3, which requires
$c_{1}=2u_{1}+4\bar{c}_{1}$ queries. Since
$u_{1}=n^{5/7}\ll\bar{c_{1}}=n^{7.5/7}$, we have $c_{1}=\Theta(\bar{c}_{1})$.
We now describe how to implement $\bar{C}_{1}$. The input state is
$\ket{R_{1}}\ket{D(R_{1})}$, and the quantum walk basis state is
$\ket{R_{2},y}$ with $R_{2}\subseteq[n]-R_{1}$, $y\in[n]-R_{1}-R_{2}$. From
the effect of $C_{2}$ shown above, we can see that only when the input state
satisfies $|R_{1}\cap\triangle|=1$, does $C_{2}\neq I$. In this special case,
$|([n]-R_{1})\cap\triangle|=2$, and thus the quantum walk search process
satisfies Condition 1 with $K=\triangle-R_{1}$ and $(j_{0},l_{0})=(1,0)$.
Therefore, the walk can be reduced to a 2-dimensional invariant subspace by
Lemma 1, and then by Lemma 3 we can obtain with certainty the target state
$\ket{t}$, which is an equal superposition of $\ket{R_{2},y}$ with
$|R_{2}\cap\triangle|=1$ and $y\notin\triangle$. See Section 4.2 for more
details. Denote by $\mathcal{A}_{2}$ the above process that on input state
$\ket{R_{1}}\ket{D(R_{1})}$, implements $\ket{0}\mapsto\ket{t}$. Then applying
$C_{2}$ once more we can flip an auxiliary qubit with certainty, and thus
$\mathcal{A}_{2}^{\dagger}C_{2}\mathcal{A}_{2}$ implements $\bar{C}_{1}$ with
100% success probability.

######  Remark 1.

It’s worth noting that in the implementation of $\bar{C}_{1}$ in layer 2, we
cannot use Lemma 2 to obtain with certainty the target state like in the
implementation of $C_{3}$ in layer 4. This is because in the implementation of
the phase shift operator
$S_{\psi_{0}}(\beta)=e^{-i\beta\ket{\psi_{0}}\bra{\psi_{0}}}$ in Lemma 2, we
would otherwise need to query $r_{1}\times r_{2}$ times to construct
$\ket{G_{R_{1},R_{2}}}$ in $\ket{\psi_{0}}$, which is intolerable since
$r_{1}\times r_{2}=n^{9/7}$ would then be multiplied by
$1/\sqrt{\epsilon_{1}}=n^{1.5/7}$ of layer 1, making the query complexity
exceed $n^{9/7}$.

Derandomizing layer 1 and finishing the proof of Theorem 1. As shown above,
$C_{1}$ acts nontrivially only when basis state
$\ket{R_{1}}\ket{R_{1}^{\prime}}\ket{D(R_{1})}$ satisfies
$|R_{1}\cap\triangle|=1$ and $|R_{1}^{\prime}\cap\triangle|=1$. Therefore, the
quantum walk search on $G_{1}=J(n,r_{1})$ can be reduced to a $10$-dimensional
invariant subspace, as shown in Section 4.3. Also, by setting
$t_{1}=\lfloor\frac{\pi}{2}\sqrt{2r_{1}}\rceil$ and
$t_{2}=\lfloor\frac{\pi}{4}\sqrt{\frac{n}{3r_{1}}}\rceil$, the success
amplitude
$p=\left|\bra{t}(W^{t_{1}}C_{1})^{t_{2}}\ket{\psi_{0}}\right|=\Omega(1)$ as
shown by Lemma 6, and $p$ can be computed exactly beforehand. Thus combined
with Lemma 2, we can obtain with certainty the target state $\ket{t}$, which
is an equal superposition of $\ket{R_{1}}$ satisfying
$|R_{1}\cap\triangle|=1$.

We can now apply the deterministic (quantum walk) search
$\mathcal{A}_{2},\mathcal{A}_{3},\mathcal{A}_{4}$ of layers 2,3,4 successively
and then measure all the registers. This will lead to
$\ket{R_{1}}\ket{R_{2}}\ket{z}\ket{S_{1}}\ket{S_{2}}$ satisfying $a\in S_{1}$,
$b\in S_{2}$ and $z=c$. Thus from the associated data
$\ket{G_{R_{1},R_{2}}}\ket{G_{S_{1},z}}\ket{G_{S_{2},z}}$ we can find the
target $\triangle abc$ with certainty. If there’s no $a\in S_{1},b\in S_{2}$
such that $A_{a,b}+A_{a,z}+A_{b,z}=d$, we claim that the graph $G$ does not
contain the target triangle.

##  4 Details of quantum walk search in different layer

In the following subsections, we will fill in the missing details of the three
aforementioned quantum walk search on Johnson graphs: (i) edge-walk on
$G_{1}=J(n,r_{1})$ of layer 1, (ii) vertex-walk on $G_{2}=J(n_{1},r_{2})$ of
layer 2, and (iii) vertex-walk on the product Johnson graph
$G_{4}=J(r_{1},m)\times J(r_{2},m)$ of layer 4. We start with the layer 4
whose checking operation does not rely on other layer.

###  4.1 Layer 4

Suppose the input state $\ket{R_{1}}\ket{R_{2}}\ket{G_{R_{1},R_{2}}}\ket{z}$
of this layer satisfies $a\in R_{1},b\in R_{2},z=c$, the target state of
quantum vertex-walk search on $G_{4}=J(r_{1},m)\times J(r_{2},m)$ is an equal
superposition of $\ket{S_{1}}\ket{S_{2}}$ such that $a\in S_{1},b\in S_{2}$.

Setup. The initial state is

$\ket{\psi_{0}}=\bigotimes_{i=1}^{2}\frac{1}{\sqrt{\binom{r_{i}}{m}}}\sum_{S_{i}\subseteq
R_{i}}\ket{S_{i}}\ket{G_{S_{i},z}}\frac{1}{\sqrt{r_{i}-m}}\sum_{z_{i}\in
R_{i}-S_{i}}\ket{z_{i}}.$ (53)

We first construct an equal superposition of $\ket{S_{i}}$ s.t.
$S_{i}\subseteq R_{i}$ and $|S_{i}|=m$ based on $\ket{R_{i}}$, and then query
the oracle for $m$ times to construct the associated data $\ket{G_{S_{i},z}}$
based on $\ket{S_{i}}\ket{z}$, and finally construct an equal superposition of
$\ket{z_{i}}$ s.t. $z_{i}\in R_{i}-S_{i}$ based on $\ket{R_{i}}\ket{S_{i}}$.

Update. A step of quantum walk $U$ consists of $2$ query operations and $2$
diffusion operations:

$U=Q\cdot U_{B}\cdot Q\cdot U_{A},$ (54)

with working registers:

$\ket{z}\bigotimes_{i=1}^{2}\ket{R_{i}}\ket{S_{i}}\ket{z_{i}}\ket{G_{S_{i},z}}\ket{G_{z_{i},z}}.$
(55)

The first diffusion operation $U_{A}$ acts on registers
$\bigotimes_{i=1}^{2}\ket{R_{i}}\ket{S_{i}}\ket{z_{i}}$, and can be seen as
choosing a random $z_{i}\in R_{i}-S_{i}$ to be moved into $S_{i}$:

$\displaystyle U_{A}$ $\displaystyle=\sum_{R_{1},R_{2}}\sum_{S_{1}\subseteq
R_{1}}\sum_{S_{2}\subseteq
R_{2}}\bigotimes_{i=1}^{2}\ket{R_{i},S_{i}}\bra{R_{i},S_{i}}\otimes\Big{(}2\bigotimes_{i=1}^{2}\big{(}\ket{\varphi(R_{i},S_{i})}\bra{\varphi(S_{i},R_{i})}\big{)}-I\Big{)},$
(56) $\displaystyle\ket{\varphi(S_{i},R_{i})}$
$\displaystyle=\frac{1}{\sqrt{r_{i}-m}}\sum_{z_{i}\in
R_{i}-S_{i}}\ket{z_{i}}.$ (57)

The sum $\sum_{R_{1},R_{2}}$ is over $R_{1}\subseteq[n]$,
$R_{2}\subseteq[n]-R_{1}$, and for other $R_{2},S_{1},S_{2}$ we define $U_{A}$
to act trivially on $\ket{z_{1}}\ket{z_{2}}$. The query operation $Q$ calls
the oracle $O$ (Eq. (1)) on registers $\ket{z_{i}}\ket{z}\ket{G_{z_{i},z}}$
for $i=1,2$. The second diffusion operation $U_{B}$ acts on all registers
except $\ket{z}$, and can be seen as choosing a random $z_{i}^{\prime}\in
S_{i}$ being removed from $S_{i}$ and at the same time moving $z_{i}$ into
$S_{i}$, while updating the associated data
$\ket{G_{S_{i},z}}\ket{G_{z_{i},z}}$ simultaneously:

$\displaystyle U_{B}$
$\displaystyle=\sum_{R_{1},R_{2}}\ket{R_{1},R_{2}}\bra{R_{1},R_{2}}\otimes
C_{R_{1},R_{2}},$ (58) $\displaystyle C_{R_{1},R_{2}}$
$\displaystyle=2\bigotimes_{i=1}^{2}\left(\sum_{S_{i}+z_{i}\subseteq
R_{i}}\sum_{\bar{G}_{i}\in[M]^{m+1}}\ket{\varphi_{S_{i}+z_{i}}^{\bar{G}_{i}}}\bra{\varphi_{S_{i}+z_{i}}^{\bar{G}_{i}}}\right)-I,$
(59) $\displaystyle\ket{\varphi_{S_{i}+z_{i}}^{\bar{G}_{i}}}$
$\displaystyle=\frac{1}{\sqrt{m+1}}\sum_{z_{i}^{\prime}\in
S_{i}+z_{i}}\ket{S_{i}^{\prime}}\ket{z_{i}^{\prime}}\ket{G_{S_{i}^{\prime},z}}\ket{G_{z_{i}^{\prime},z}}.$
(60)

In $\ket{\varphi_{S_{i}+z_{i}}^{\bar{G}_{i}}}$, suppose the vertical
juxtaposition $[G_{S_{i},z};G_{z_{i},z}]=\bar{G}_{i}$, then for
$\ket{S_{i}^{\prime}}\ket{z_{i}^{\prime}}$ s.t.
$S_{i}^{\prime}=S_{i}-z_{i}^{\prime}+z_{i}$, its associated data
$[G_{S_{i}^{\prime},z};G_{z_{i}^{\prime},z}]$ is a corresponding permutation
of $\bar{G}_{i}$: we exchange row $z_{i}$ and $z_{i}^{\prime}$ in
$\bar{G}_{i}$, and then sort the first $m$ rows in the ascending order. Thus,
if $\bar{G}_{i}$ is a sub-matrix of the edge weight matrix $A$, then
$G_{S_{i}^{\prime},z}$ is still a sub-matrix of $A$ with rows indexed by
$S_{i}^{\prime}$ and columns indexed by $z$.

Checking. The checking operation $C_{4}$ flips an auxiliary qubit if there
exists $a\in S_{1},b\in S_{2}$ such that $A_{a,b}+A_{b,z}+A_{a,z}=d$, based on
the data $\ket{G_{S_{i},z}}$ constructed in layer 4, and
$\ket{G_{R_{1},R_{2}}}$ constructed in layer 1. Thus no additional query is
needed. Using the phase kick-back effect: $X\ket{-}=-\ket{-}$, where $X$ is
the Pauli-X matrix and $\ket{-}:=(\ket{0}-\ket{1})/\sqrt{2}$, we can add
$(-1)$ phase shift to the marked states.

Invariant subspace. Denote by $\ket{(j_{1},j_{2})-(k_{1},k_{2})}$ the equal
superposition of states in
$\\{\ket{S_{1},z_{1},S_{2},z_{2}}:|S_{i}\cap\triangle|=j_{i},|(S_{i}+z_{i})\cap\triangle|=k_{i}\\}$.
The $9$ basis states of the quantum walk’s invariant subspace
$\mathcal{H}_{0}$ is illustrated in Fig. 2.

Figure 2: Illustration of the $9$ basis states
$\ket{(j_{1},j_{2})-(k_{1},k_{2})}$ of the invariant subspace
$\mathcal{H}_{0}$ of quantum walk search on $G_{4}=J(r_{1},m)\times
J(r_{2},m)$.

It can be seen form Fig. 2 that a step of quantum walk $U$ takes the following
matrix form in $\mathcal{H}_{0}$.

$W=(2BB^{\dagger}-I)(2AA^{\dagger}-I),$ (61)

where non-negative matrices $A$ and $B$ satisfy:

$A.^{2}=\begin{bmatrix}(1-\frac{1}{r_{1}-m})(1-\frac{1}{r_{2}-m})&0&0&0\\\
\frac{1}{r_{1}-m}(1-\frac{1}{r_{2}-m})&0&0&0\\\
(1-\frac{1}{r_{1}-m})\frac{1}{r_{2}-m}&0&0&0\\\
\frac{1}{(r_{1}-m)(r_{2}-m)}&0&0&0\\\ 0&1-\frac{1}{r_{2}-m}&0&0\\\
0&\frac{1}{r_{2}-m}&0&0\\\ 0&0&1-\frac{1}{r_{1}-m}&0\\\
0&0&\frac{1}{r_{1}-m}&0\\\
0&0&0&1\end{bmatrix},B.^{2}=\begin{bmatrix}1&0&0&0\\\ 0&\frac{1}{m+1}&0&0\\\
0&0&\frac{1}{m+1}&0\\\ 0&0&0&\frac{1}{(m+1)^{2}}\\\ 0&\frac{m}{m+1}&0&0\\\
0&0&0&\frac{m}{(m+1)^{2}}\\\ 0&0&\frac{m}{m+1}&0\\\
0&0&0&\frac{m}{(m+1)^{2}}\\\ 0&0&0&\frac{m^{2}}{(m+1)^{2}}\\\ \end{bmatrix}$
(62)

From the number of basis states in $\ket{(j_{1},j_{2})-(k_{1},k_{2})}$ (or
weights of the $9$ lines in Fig. 2), it’s easy to see the initial state takes
the following form in $\mathcal{H}_{0}$ after simplification:

$\ket{\psi_{0}}.^{2}=\begin{bmatrix}(r_{1}-m-1)(r_{2}-m-1)\\\ (r_{2}-m-1)\\\
(r_{1}-m-1)\\\ 1\\\ m(r_{2}-m-1)\\\ m\\\ (r_{1}-m-1)m\\\ m\\\
m^{2}\end{bmatrix}\div(r_{1}r_{2}),$ (63)

and the overlap with the target state $\ket{t}=\ket{e_{9}}$ is
$\sqrt{\epsilon_{4}}=\frac{m}{\sqrt{r_{1}r_{2}}}$.

######  Lemma 4.

Setting $t_{1}=\lfloor\frac{\pi}{2}\sqrt{\frac{m}{2}}\rceil$ and
$t_{2}=\lfloor\frac{\pi}{4}\frac{\sqrt{r_{1}r_{2}}}{m}\rceil$, the success
amplitude $p=\left|\bra{t}(W^{t_{1}}C_{4})^{t_{2}}\ket{\psi_{0}}\right|$
satisfies $p=1-O(\frac{m}{r_{2}}+\frac{m}{r_{1}}+\frac{1}{m})$.

###### Proof.

Similar to [42, Lemma 2], it can be shown that $W$ has two eigenvectors
$\ket{u_{\pm}}$ with corresponding eigenvalues $e^{\pm i\varphi}$ such that

$\displaystyle\left|\braket{t}{u_{\pm}}\right|$
$\displaystyle=\frac{1}{\sqrt{2}}+O(\frac{1}{m}+\frac{m}{r_{1}}+\frac{m}{r_{2}}),$
(64) $\displaystyle\varphi$
$\displaystyle=\frac{2\sqrt{2}}{\sqrt{m}}(1+O(\frac{1}{\sqrt{m}}+\frac{m}{r_{1}}+\frac{m}{r_{1}})).$
(65)

Similar to [42, Lemma 3], it can be shown that when $t_{1}\varphi\approx\pi$
and $C_{4}=2\ket{t}\bra{t}-I$ adds relative phase shift $(-1)$ to the only
target basis state $\ket{t}$ in $\mathcal{H}_{0}$, $W^{t_{1}}C_{4}$ has two
eigenvectors $\ket{\theta_{\pm}}$ with corresponding eigenvalues $e^{\pm
i\theta}$ such that

$\displaystyle\braket{t}{\theta_{\pm}}$
$\displaystyle=\frac{1}{\sqrt{2}}+\delta,\quad\braket{\psi_{0}}{\theta_{\pm}}=\pm\frac{i}{\sqrt{2}}+\delta,$
(66) $\displaystyle\theta$
$\displaystyle=\frac{2m}{\sqrt{r_{1}r_{2}}}(1+\delta),$ (67)

where $\delta=O(\frac{m}{r_{2}}+\frac{m}{r_{1}}+\frac{1}{m})$. Consider
$p(t_{2})=\left|\bra{t}(W^{t_{1}}C_{4})^{t_{2}}\ket{\psi_{0}}\right|$. Let
$\Pi_{\pm}:=\ket{\theta_{+}}\bra{\theta_{+}}+\ket{\theta_{-}}\bra{\theta_{-}}$,
and $\Pi_{j}$ be the projection onto the other $7$ eigenvectors of
$W^{t_{1}}C_{4}$. Then $\|\Pi_{\pm}\ket{\psi_{0}}\|=1-\delta$, and
$\left|\bra{t}\Pi_{j}\ket{\psi_{0}}\right|\leq\|\Pi_{j}\ket{\psi_{0}}\|=\delta$.
Therefore,

$\displaystyle p(t_{2})$
$\displaystyle\geq\left|e^{it_{2}\theta}\braket{t}{\theta_{+}}\braket{\theta_{+}}{\psi_{0}}+e^{-it_{2}\theta}\braket{t}{\theta_{-}}\braket{\theta_{-}}{\psi_{0}}\right|-\sum_{j}\left|\bra{t}\Pi_{j}\ket{\psi_{0}}\right|$
(68)
$\displaystyle\geq\left|e^{it_{2}\theta}\frac{-i}{2}(1+\delta)+e^{-it_{2}\theta}\frac{i}{2}(1+\delta)\right|-7\delta$
(69) $\displaystyle=\sin(t_{2}\theta)-O(\delta).$ (70)

Setting $t_{2}=\lfloor\frac{\pi}{4}\frac{\sqrt{r_{1}r_{2}}}{m}\rceil$ we have
$p(t_{2})=1-\delta$ which completes the proof. ∎

###  4.2 Layer 2

Suppose the input state $\ket{R_{1}}\ket{D(R_{1})}$ (see Eq. (43) for
$D(R_{1})$) of this layer satisfies $|R_{1}\cap\triangle|=1$, the target state
of quantum edge-walk search on $G_{2}=J(n_{1},r_{2})$ is an equal
superposition of $\ket{R_{2},y}$ such that
$|R_{2}\cap\triangle|=1,y\notin\triangle$.

Setup. The initial state is

$\ket{\psi_{0}}=\ket{R_{1}}\ket{D(R_{1})}\frac{1}{\sqrt{n_{2}}}\sum_{y}\ket{y},$
(71)

where
$\ket{D(R_{1})}=\frac{1}{\sqrt{\binom{n_{1}}{r_{2}}}}\sum_{R_{2}\subseteq[n]-R_{1}}\ket{R_{2}}\ket{G_{R_{1},R_{2}}}$.
We only need to construct an equal superposition of $y\in[n]-R_{1}-R_{2}$
based on $\ket{R_{1}}\ket{R_{2}}$, which requires no query.

Update. A step of quantum walk $U$ consists of $2$ query operations and $2$
diffusion operations:

$U=Q\cdot U_{B}(\theta_{2})\cdot Q\cdot U_{A}(\theta_{1}),$ (72)

with working registers:

$\ket{R_{1}}\ket{R_{2}}\ket{G_{R_{1},R_{2}}}\ket{y}\ket{G_{R_{1},y}}.$ (73)

The first diffusion operation $U_{A}(\theta_{1})$ acts on registers
$\ket{R_{1}}\ket{R_{2}}\ket{y}$, and can be seen as choosing a random
$y\in[n]-R_{1}-R_{2}$ to be moved in to $R_{2}$:

$\displaystyle U_{A}(\theta_{1})$ $\displaystyle=\sum_{R_{1}\cap
R_{2}=\phi}\ket{R_{1},R_{2}}\bra{R_{1},R_{2}}\otimes
C_{R_{1},R_{2}}(\theta_{1}),$ (74) $\displaystyle C_{R_{1},R_{2}}(\theta_{1})$
$\displaystyle=I-(1-e^{i\theta_{1}})\ket{\varphi(R_{1},R_{2})}\bra{\varphi(R_{1},R_{2})},$
(75) $\displaystyle\ket{\varphi(R_{1},R_{2})}$
$\displaystyle=\frac{1}{\sqrt{n_{2}}}\sum_{y\in[n]-R_{1}-R_{2}}\ket{y}$ (76)

The query operation $Q$ calls the oracle $O$ (Eq. (1)) for $r_{1}$ times to
update the data $G_{R_{1},y}$ associated with $\ket{R_{1}}\ket{y}$. The second
diffusion operation $U_{B}(\theta_{2})$ acts on all registers, and can be seen
as choosing a random $y^{\prime}\in R_{2}$ being removed from $R_{2}$ and at
the same time moving $y$ into $R_{2}$, while updating the associated data
$\ket{G_{R_{1},R_{2}}}\ket{G_{R_{1},y}}$ simultaneously:

$\displaystyle U_{B}(\theta_{2})$
$\displaystyle=\sum_{R_{1}}\ket{R_{1}}\bra{R_{1}}\otimes
C_{R_{1}}(\theta_{2}),$ (77) $\displaystyle C_{R_{1}}(\theta_{2})$
$\displaystyle=I-(1-e^{i\theta_{2}})\sum_{R_{2}+y\subseteq[n]-R_{1}}\sum_{\bar{G}\in[M]^{r_{1}\times(r_{2}+1)}}\ket{\varphi_{R_{2}+y}^{\bar{G}}}\bra{\varphi_{R_{2}+y}^{\bar{G}}},$
(78) $\displaystyle\ket{\varphi_{R_{2}+y}^{\bar{G}}}$
$\displaystyle=\frac{1}{\sqrt{r_{2}+1}}\sum_{y^{\prime}\in
R_{2}+y}\ket{R_{2}^{\prime}}\ket{y^{\prime}}\ket{G_{R_{1},R_{2}^{\prime}}}\ket{G_{R_{1},y^{\prime}}}.$
(79)

In $\ket{\varphi_{R_{2}+y}^{\bar{G}}}$, suppose the horizontal juxtaposition
$[G_{R_{1},R_{2}},G_{R_{1},y}]$ equals $\bar{G}$, then for
$\ket{R_{2}^{\prime}}\ket{y^{\prime}}$ s.t.
$R_{2}^{\prime}=R_{2}-y^{\prime}+y$, its associated data
$[G_{R_{1},R_{2}^{\prime}},G_{R_{1},y^{\prime}}]$ is an appropriate
permutation of the columns of $\bar{G}$. This is similar to
$\ket{\varphi_{S_{i}+z_{i}}^{\bar{G}_{i}}}$ defined in Eq. (60).

Checking. The checking operator
$S_{\mathcal{M}}(\alpha)=C_{2}(I\otimes\mathrm{diag}(1,e^{i\alpha}))C_{2}$
adds phase shift $e^{i\alpha}$ to states
$\ket{R_{1}}\ket{R_{2}}\ket{G_{R_{1},R_{2}}}\ket{y}$ which satisfies
$|R_{1}\cap\triangle|=1$, $|R_{2}\cap\triangle|=1$ and $y\notin\triangle$.

Assume $|R_{1}\cap\triangle|=1$, then $|([n]-R_{1})\cap\triangle|=2$.
Therefore, the quantum vertex-walk search on $G_{2}=J(n_{1},r_{2})$ satisfies
Condition 1 with $K=\triangle-R_{1}$ and $(j_{0},l_{0})=(1,0)$, and we can
obtain the same $5$-dimensional invariant subspace as shown by Fig. 1 in
Section 2.2, but now $N:=n_{1}$, $r:=r_{2}$, $R:=R_{2}$, and $K:=\triangle-
R_{1}$. Since the target state is now $\ket{t}=\ket{1,0}$, the proportion of
marked states becomes

$\displaystyle\epsilon_{2}$
$\displaystyle=\frac{2\binom{n_{1}-2}{r_{2}-1}(n_{1}-r_{2}-1)}{\binom{n_{1}}{r_{2}}(n_{1}-r_{2})}$
(80)
$\displaystyle=2\frac{r_{2}}{n_{1}}(1-\frac{r_{2}}{n_{1}-1})=\Theta(\frac{r_{2}}{n}).$
(81)

Thus by combing Lemma 1 (where now $t\in O(\sqrt{r_{2}})$) and Lemma 3 (let
$S_{\psi_{0}}(-\beta)=U^{t}$ and $\lambda=\epsilon_{2}$), we can obtain
$\ket{t}$ with certainty, and the query complexity is
$0+\sqrt{{n}/{r_{2}}}(\sqrt{r_{2}}r_{1}+c_{2})$, same as Eq. (45).

###  4.3 Layer 1

The goal of this layer is to construct an equal superposition of
$\ket{R_{1}}\ket{R_{1}^{\prime}}$ such that $|R_{1}\cap\triangle|=1$ and
$|R_{1}^{\prime}\cap\triangle|=1$. The quantum edge-walk search on
$G_{1}=J(n,r_{1})$ is the same as in Section 2.1. We first describe how to
implement the update operator in the following lemma.

######  Lemma 5.

The ‘Data’ operator that transform the data $D(R_{1})$ to $D(R_{1}^{\prime})$
based on $\ket{R_{1}^{\prime}}\ket{R_{1}}$ requires $2(r_{1}+r_{2})$ queries.

###### Proof.

The transformation consists of the following two steps:

$\displaystyle\ket{D(R_{1})}=$
$\displaystyle\frac{1}{\sqrt{\binom{n_{1}}{r_{2}}}}\sum_{R_{2}\cap
R_{1}=\phi}\ket{R_{2}}\ket{G_{R_{1},R_{2}}}$ $\displaystyle U_{1,1}\mapsto$
$\displaystyle\frac{1}{\sqrt{\binom{n_{1}}{r_{2}}}}\sum_{R_{2}^{\prime}\cap
R_{1}^{\prime}=\phi}\ket{R_{2}^{\prime}}\ket{G_{R_{1},R_{2}^{\prime}}}$ (82)
$\displaystyle U_{1,2}\mapsto$
$\displaystyle\frac{1}{\sqrt{\binom{n_{1}}{r_{2}}}}\sum_{R_{2}^{\prime}\cap
R_{1}^{\prime}=\phi}\ket{R_{2}^{\prime}}\ket{G_{R_{1}^{\prime},R_{2}^{\prime}}}=\ket{D(R_{1}^{\prime})}.$
(83)

Specifically, let $x_{1}:=R_{1}\setminus R_{1}^{\prime}$ and
$x_{1}^{\prime}=R_{1}^{\prime}\setminus R_{1}$, which can be calculated from
$\ket{R_{1}}\ket{R_{1}^{\prime}}$. Consider some $R_{2}\subseteq[n]-R_{1}$. If
$x_{1}^{\prime}\notin R_{2}$, then $U_{1,1}$ keeps $R_{2}$ unchanged; if
$x_{1}^{\prime}\in R_{2}$, then $U_{1,1}$ implements $R_{2}\mapsto
R_{2}^{\prime}=R_{2}-x_{1}^{\prime}+x_{1}$ and also update the data
$\ket{G_{R_{1},R_{2}}}$ simultaneously: it clears the data
$G_{R_{1},x_{1}^{\prime}}$ in column $x_{1}^{\prime}$, and then writes back
$G_{R_{1},x_{1}}$, and finally permutes the $r_{2}$ columns so that the
indexes $R_{2}^{\prime}=R_{2}-x_{1}^{\prime}+x_{1}$ remain the ascending
order. Therefore, $U_{1,1}$ requires $2r_{1}$ queries.

Operator $U_{1,2}$ does not need to deal with separate cases, and is simpler
to implement. It updates $G_{x_{1},R_{2}^{\prime}}$ to
$G_{x_{1}^{\prime},R_{2}^{\prime}}$ in row $x_{1}$, and then permutes the
$r_{1}$ rows so that the indexes $R_{1}^{\prime}=R_{1}-x_{1}+x_{1}^{\prime}$
remain the ascending order. Therefore, $U_{1,2}$ requires $2r_{2}$ queries.
The above process is illustrated in Fig. 3.

Figure 3: The update operator in layer 1 requires $2r_{1}+2r_{2}$ queries as
shown in Lemma 5.

∎

Checking. The checking operator $C_{1}$ adds phase shift to
$\ket{R_{1}}\ket{R_{1}^{\prime}}\ket{D(R_{1})}$ such that
$|R_{1}\cap\triangle|=1$ and $|R_{1}^{\prime}\cap\triangle|=1$. Suppose
$\bar{C}_{1}$ implemented in layer 2 flips an auxiliary qubit based on
$\ket{D(R_{1})}$ if $|R_{1}\cap\triangle|=1$, then $C_{1}$ can be implemented
with costs $c_{1}=2u_{1}+4\bar{c}_{1}$ as shown below:

1\. apply $\bar{C}_{1}$ to $\ket{R_{1}}\ket{D(R_{1})}$ and store the result on
$\ket{b_{1}}$ initialized to $\ket{0}$; 2\. update the data $\ket{D(R_{1})}$
to $\ket{D(R_{1}^{\prime})}$ using Lemma 5; 3\. apply $\bar{C}_{1}$ to
$\ket{R_{1}^{\prime}}\ket{D(R_{1}^{\prime})}$ and store the result on
$\ket{b_{1}^{\prime}}$ initialized to $\ket{0}$; 4\. use phase kick-back to
add phase shift $(-1)$ if $b_{1}\wedge b_{1}^{\prime}=1$; 5\. clear the
register $\ket{b_{1}}$, $\ket{b_{1}^{\prime}}$ and recover $D(R_{1})$ by
applying the inverse of the first 3 steps.

Invariant subspace. Denote by $\ket{j,l}$ the equal superposition of states
$\ket{R_{1}}\ket{R_{1}^{\prime}}$ satisfying
$\left|R_{1}\cap\triangle\right|=j$ and
$\left|R_{1}^{\prime}\cap\triangle\right|=l$. The $10$ basis states of the
quantum walk’s invariant subspace $\mathcal{H}_{0}$ is illustrated in Fig. 4.

Figure 4: Illustration of the $10$ basis states $\ket{j,l}$ of the invariant
subspace $\mathcal{H}_{0}$ of quantum walk search on $G_{1}=J(n,r_{1})$.

It can be seen from Fig. 4 and the definition of a step of quantum walk $U$
which consists of ‘Coin’ and ‘Swap’ operators as shown in Section 2.1, that
$U$ takes the following matrix form $W$ in $\mathcal{H}_{0}$:

$W=S(2AA^{\dagger}-I),$ (84)

where $S=\mathrm{diag}(1,X,1,X,1,X,1)$, and non-negative matrix $A$ satisfies

$A.^{2}=\begin{bmatrix}1-\frac{3}{n-r}&0&0&0\\\ \frac{3}{n-r}&0&0&0\\\
0&\frac{n-r-2}{r(n-r)}&0&0\\\ 0&\frac{(r-1)(n-r-2)+2}{r(n-r)}&0&0\\\
0&\frac{2(r-1)}{r(n-r)}&0&0\\\ 0&0&\frac{2(n-r-1)}{r(n-r)}&0\\\
0&0&\frac{(r-2)(n-r-1)+2}{r(n-r)}&0\\\ 0&0&\frac{r-2}{r(n-r)}&0\\\
0&0&0&\frac{3}{r}\\\ 0&0&0&1-\frac{3}{r}\end{bmatrix}.$ (85)

The initial state takes the following form in $\mathcal{H}_{0}$:

$\ket{\psi_{0}}.^{2}=\begin{bmatrix}(n-r_{1}-1)(n-r_{1}-2)(n-r_{1}-3)\\\
3(n-r_{1}-1)(n-r_{1}-2)\\\ 3(n-r_{1}-1)(n-r_{1}-2)\\\
3(n-r_{1}-1)((r_{1}-1)(n-r_{1}-2)+2)\\\ 6(r_{1}-1)(n-r_{1}-1)\\\
6(r_{1}-1)(n-r_{1}-1)\\\ 3(r_{1}-1)((r_{1}-2)(n-r_{1}-1)+2)\\\
3(r_{1}-1)(r_{1}-2)\\\ 3(r_{1}-1)(r_{1}-2)\\\
(r_{1}-1)(r_{1}-2)(r_{1}-3)\end{bmatrix}\div(n(n-1)(n-2)).$ (86)

It can be seen that the overlap between $\ket{\psi_{0}}$ and the target state
$\ket{t}=\ket{e_{4}}$ is $\sqrt{\epsilon_{1}}=\Theta(\sqrt{r_{1}/n})$.

######  Lemma 6.

Setting $t_{1}=\lfloor\frac{\pi}{2}\sqrt{2r_{1}}\rceil$ and
$t_{2}=\lfloor\frac{\pi}{4}\sqrt{\frac{n}{3r_{1}}}\rceil$, the success
amplitude $p=\left|\bra{t}(W^{t_{1}}C_{1})^{t_{2}}\ket{\psi_{0}}\right|$
satisfies $p=1-O(\frac{1}{r_{1}}+\frac{r_{1}}{n})$.

###### Proof.

Similar to [42, Lemma 2], it can be shown that $W$ has two eigenvectors
$\ket{u_{\pm}}$ with eigenvalues $e^{\pm i\varphi}$ such that

$\displaystyle\left|\braket{t}{u_{\pm}}\right|$
$\displaystyle=\frac{1}{\sqrt{2}}+\delta,$ (87) $\displaystyle\varphi$
$\displaystyle=\sqrt{\frac{2}{r}}(1+\delta),$ (88)

where $\delta:=O(\frac{1}{r_{1}}+\frac{r_{1}}{n})$. To make
$t_{1}\varphi\approx\pi$, we set $t_{1}$ to be the nearest integer to
$\frac{\pi}{2}\sqrt{2r_{1}}$. Note that $C_{1}=2\ket{t}\bra{t}-I$ adds phase
shift to the only target basis state $\ket{t}=\ket{e_{4}}$ in
$\mathcal{H}_{0}$. Thus, similar to [42, Lemma 3], it can be shown that
$W^{t_{1}}C_{1}$ has two eigenvectors $\ket{\theta_{\pm}}$ with eigenvalues
$e^{\pm i\theta}$ such that

$\displaystyle\braket{t}{\theta_{\pm}}$
$\displaystyle=\frac{1}{\sqrt{2}}+\delta,\quad\braket{\psi_{0}}{\theta_{\pm}}=\pm\frac{i}{\sqrt{2}}+\delta,$
(89) $\displaystyle\theta$ $\displaystyle=2\sqrt{\frac{3r}{n}}(1+\delta).$
(90)

Consider
$p(t_{2})=\left|\bra{t}(W^{t_{1}}C_{1})^{t_{2}}\ket{\psi_{0}}\right|$. Let
$\Pi_{\pm}:=\ket{\theta_{+}}\bra{\theta_{+}}+\ket{\theta_{-}}\bra{\theta_{-}}$,
and $\Pi_{j}$ be the projection onto the other $8$ eigenvectors of
$W^{t_{1}}C_{1}$. Then $\|\Pi_{\pm}\ket{\psi_{0}}\|=1-\delta$, and
$\left|\bra{t}\Pi_{j}\ket{\psi_{0}}\right|\leq\|\Pi_{j}\ket{\psi_{0}}\|=\delta$.
Therefore,

$\displaystyle p(t_{2})$
$\displaystyle\geq\left|e^{it_{2}\theta}\braket{t}{\theta_{+}}\braket{\theta_{+}}{\psi_{0}}+e^{-it_{2}\theta}\braket{t}{\theta_{-}}\braket{\theta_{-}}{\psi_{0}}\right|-\sum_{j}\left|\bra{t}\Pi_{j}\ket{\psi_{0}}\right|$
(91)
$\displaystyle\geq\left|e^{it_{2}\theta}\frac{-i}{2}(1+\delta)+e^{-it_{2}\theta}\frac{i}{2}(1+\delta)\right|-8\delta$
(92) $\displaystyle=\sin(t_{2}\theta)-O(\delta).$ (93)

Setting $t_{2}=\lfloor\frac{\pi}{4}\sqrt{\frac{n}{3r_{1}}}\rceil$, we have
$p(t_{2})=1-\delta$, which completes the proof. ∎

##  5 Discussions

In this paper, we have shown that there is a deterministic quantum algorithm
for the triangle sum promised problem (i.e. the graph contains at most one
target triangle) based on derandomization of a nested-quantum-walk-based
algorithm by Jeffery et al. Our algorithm achieves the same $O(n^{9/7})$
queries with the state-of-the-art bounded error quantum algorithm, utilizing
several non-trivial techniques. It may be worth further considering the
following problems.

  1. 1.

Will the lower bound of $\Omega(n^{9/7}/\sqrt{\log n})$ remains unchanged for
the triangle sum promised problem considered in this paper?

  2. 2.

Is it still possible to design a deterministic quantum algorithm when the
graph is promised to contain none or $k>1$ target triangles?

  3. 3.

Is it possible to derandomize the state-of-the-art $O(n^{5/4})$-query quantum
algorithm for triangle finding [29] when given an additional promise?

## References

  * [1] Gary L. Miller.  “Riemann’s hypothesis and tests for primality”.  Journal of Computer and System Sciences 13, 300–317 (1976).
  * [2] Michael O Rabin.  “Probabilistic algorithm for testing primality”.  Journal of Number Theory 12, 128–138 (1980).
  * [3] R. Solovay and V. Strassen.  “A fast monte-carlo test for primality”.  SIAM Journal on Computing 6, 84–85 (1977).
  * [4] Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, and Charles Rackoff.  “Random walks, universal traversal sequences, and the complexity of maze problems”.  In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979).  Pages 218–223.  (1979).
  * [5] R. M. Karp, E. Upfal, and A. Wigderson.  “Constructing a perfect matching is in random nc”.  Combinatorica 6, 35–48 (1986).
  * [6] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.  “Primes is in p”.  Annals of Mathematics 160, 781–793 (2004).  url: http://www.jstor.org/stable/3597229.
  * [7] Valentine Kabanets.  “Derandomization: A brief overview”.  Current Trends in Theoretical Computer Science 1, 165–188 (2002).
  * [8] Russell Impagliazzo.  “Can every randomized algorithm be derandomized?”.  In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing.  Page 373–374.  STOC ’06New York, NY, USA (2006). Association for Computing Machinery.
  * [9] Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon.  “Derandomization from algebraic hardness: Treading the borders”.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS).  Pages 147–157.  (2019).
  * [10] Lijie Chen and Roei Tell.  “Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost”.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing.  Page 283–291.  STOC 2021New York, NY, USA (2021). Association for Computing Machinery.
  * [11] Dean Doron and Roei Tell.  “Derandomization with Minimal Memory Footprint”.  In Amnon Ta-Shma, editor, 38th Computational Complexity Conference (CCC 2023).  Volume 264 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:15.  Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [12] Omer Reingold.  “Undirected connectivity in log-space”.  J. ACM55 (2008).
  * [13] Ola Svensson and Jakub Tarnawski.  “The matching problem in general graphs is in quasi-nc”.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS).  Pages 696–707.  (2017).
  * [14] Michael Luby and Avi Wigderson.  “Pairwise independence and derandomization”.  Foundations and Trends in Theoretical Computer Science 1, 237–301 (2006).
  * [15] Salil P. Vadhan.  “Pseudorandomness”.  Foundations and Trends in Theoretical Computer Science 7, 1–336 (2012).
  * [16] Roei Tell.  “Quantified derandomization: How to find water in the ocean”.  Foundations and Trends in Theoretical Computer Science 15, 1–125 (2022).
  * [17] Peter W. Shor.  “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”.  SIAM Journal on Computing 26, 1484–1509 (1997).
  * [18] 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.
  * [19] Ashley Montanaro.  “Quantum algorithms: an overview”.  npj Quantum Information 2, 15023 (2016).
  * [20] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  “Quantum amplitude amplification and estimation”.  Contemporary Mathematics 305, 53–74 (2002).  url: arxiv.org/abs/quant-ph/0005055.
  * [21] Peter Hoyer.  “On arbitrary phases in quantum amplitude amplification”.  Physical Review A62 (2000).
  * [22] G. L. Long.  “Grover algorithm with zero theoretical failure rate”.  Phys. Rev. A 64, 022307 (2001).
  * [23] Tanay Roy, Liang Jiang, and David I. Schuster.  “Deterministic grover search with a restricted oracle”.  Phys. Rev. Res. 4, L022013 (2022).
  * [24] Guanzhong Li and Lvzhou Li.  “Deterministic quantum search with adjustable parameters: Implementations and applications”.  Information and Computation 292, 105042 (2023).
  * [25] 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).
  * [26] Zekun Ye, Yunqi Huang, Lvzhou Li, and Yuyi Wang.  “Query complexity of generalized simon’s problem”.  Information and Computation 281, 104790 (2021).
  * [27] Guanzhong Li and Lvzhou Li.  “Optimal exact quantum algorithm for the promised element distinctness problem” (2022).  arXiv:2211.05443.
  * [28] Guanzhong Li, Jingquan Luo, and Lvzhou Li.  “Recover the original simplicity: concise and deterministic quantum algorithm for the welded tree problem” (2023).  arXiv:2304.08395.
  * [29] Titouan Carette, Mathieu Lauriere, and Frederic Magniez.  “Extended Learning Graphs for Triangle Finding”.  In Heribert Vollmer and Brigitte Vallee, editors, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017).  Volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:14.  Dagstuhl, Germany (2017). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [30] Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, and Ronald de Wolf.  “Quantum algorithms for element distinctness”.  SIAM Journal on Computing 34, 1324–1330 (2005).
  * [31] Mario Szegedy.  “On the quantum query complexity of detecting triangles in graphs” (2003).  arXiv:quant-ph/0310107.
  * [32] Frédéric Magniez, Miklos Santha, and Mario Szegedy.  “Quantum algorithms for the triangle problem”.  SIAM J. Comput. 37, 413–424 (2007).
  * [33] Andris Ambainis.  “Quantum walk algorithm for element distinctness”.  SIAM J. Comput. 37, 210–239 (2007).
  * [34] Aleksandrs Belovs.  “Span programs for functions with constant-sized 1-certificates: Extended abstract”.  In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing.  Page 77–84.  STOC ’12New York, NY, USA (2012). Association for Computing Machinery.
  * [35] Troy Lee, Frédéric Magniez, and Miklos Santha.  “Improved quantum query algorithms for triangle finding and associativity testing”.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms.  Page 1486–1502.  SODA ’13USA (2013). Society for Industrial and Applied Mathematics.  url: dl.acm.org/doi/10.5555/2627817.2627924.
  * [36] Francois Le Gall.  “Improved quantum algorithm for triangle finding via combinatorial arguments”.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science.  Pages 216–225.  (2014).
  * [37] Stacey Jeffery and Peter Richter.  “Quantum algorithm for finding triangles”.  Pages 1–6.  Springer Berlin Heidelberg. Berlin, Heidelberg (2014).
  * [38] Aleksandrs Belovs and Ansis Rosmanis.  “On the power of non-adaptive learning graphs”.  In 2013 IEEE Conference on Computational Complexity.  Pages 44–55.  (2013).
  * [39] Stacey Jeffery, Robin Kothari, and Frédéric Magniez.  “Nested quantum walks with quantum data structures”.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms.  Page 1474–1485.  SODA ’13USA (2013). Society for Industrial and Applied Mathematics.
  * [40] Frederic Magniez, Ashwin Nayak, Jeremie Roland, and Miklos Santha.  “Search via quantum walk”.  In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing.  Page 575–584.  STOC ’07New York, NY, USA (2007). Association for Computing Machinery.
  * [41] Aleksandrs Belovs and Robert Spalek.  “Adversary lower bound for the k-sum problem” (2012).  arXiv:1206.6528.
  * [42] Andrew M Childs and Jason M Eisenberg.  “Quantum algorithms for subset finding”.  Quantum Information & Computation 5, 593–604 (2005).  url: dl.acm.org/doi/abs/10.5555/2011656.2011663.