Derandomization of quantum algorithm for triangle finding

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.

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$.

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.

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

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.

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.

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.

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:

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.

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].

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}}$.

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.

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

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

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)

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.

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$.