Degenerate perturbation theory to quantum search

Abstract

We utilize degenerate perturbation theory to investigate continuous-time quantum search on second-order truncated simplex lattices. In this work, we show that the construction of the Hamiltonian must consider the structure of the lattice. This idea enables effective application of degenerate perturbation theory to third- and higher-order lattices. We identify two constraints on the reduction of the dimension of the Hamiltonian. In addition, we elucidate the influence of the distinct configurations of marked vertices on the quantum search.

1 Introduction

Grover’s algorithm is a powerful algorithm utilized for quantum search in an unstructured database [1,2,3]. Continuous-time quantum walk (CTQW) was introduced to address the search problems in the structured databases by quantizing the classical walk through simulating the classical Markov process [4]. Continuous-time quantum walk has successfully solved the quantum search problems on complete graphs, hypercubes, d-dimensional lattice graphs and other types of graphs with substantial speedup [5,6,7,8,9,10]. Moreover, it has been extended to information transmission in networks [8, 11].

Truncated simplex lattices are of particular interest due to their effectively nonintegral dimensionality. Continuous-time quantum walks have also gained considerable attention for their application in quantum search algorithms on truncated simplex lattices [12,13,14]. Initially, the study of the quantum search in this area was focused on zeroth-order lattices [5]. Subsequently, Thomas G Wong studied first-order truncated simplex lattices [7], and Wang Yunkai et al. studied quantum search on second- and higher-order lattices [15, 16]. Zhu Xuanmin et al. explored quantum search for searching a set of marked vertices [17].

In the CTQW, the evolution of the system relies on the jumping rate $\gamma$ which represents the probability of the transition between the adjacent vertices per unit time [18, 19]. Taking an appropriate value at $\gamma$, known as the critical jumping rate $\gamma _c$, the system can evolve into the target state at an appropriate time. The common approach for determining the critical jumping rate $\gamma _c$ involves calculating the squared overlaps of the Hamiltonian’s eigenstates with the basis states [5, 7, 15,16,17]. As the order of the lattice increases, this method cannot be easily implemented.

In order to determine $\gamma _{c}$ more accurately, Thomas G. Wong introduced degenerate perturbation theory to continuous-time quantum walk [20,21,22]. He provided the schemes of degenerate perturbation theory to determine $\gamma _{c}$ on complete graphs, first-order truncated simplex lattices, and hypercubes [23]. In cases involving weighted graphs and multiple configurations of marked vertices, quantum search schemes utilizing degenerate perturbation theory have also been proposed [24, 25].

However, the existing schemes cannot be used directly to obtain the $\gamma _{c}$ on the second-order and higher-order lattices. To address this, we present a scheme for implementing degenerate perturbation theory in quantum searches on second-order and third-order lattices. The results of our investigations emphasize the importance of the lattice structure when constructing the leading-order terms of Hamiltonian. The dimension of the Hamiltonian can also be reduced to simplify the computational process by eliminating uncorrelated vertices in the evolution. The influence of different configurations of marked vertices on the quantum search is further explored by six simulation experiments with distinct configurations on the second-order lattice.

This paper is structured as follows. In Sect. 2, we explore the application of degenerate perturbation theory to quantum search on a second-order lattice. We study the quantum search on third-order lattices, and present two constraints aimed at reducing the dimension of the Hamiltonian in Sect. 3. In Sect. 4, we discuss quantum search scenarios with different configurations of marked vertices on the second-order lattice. Finally, we give our conclusions in Sect. 5.

Fig. 1

a A zeroth-order 5-dimensional simplex lattice is a 6-dimensional complete graph. b A first-order 5-dimensional simplex lattice is obtained by replacing each vertex of a zeroth-order 5-dimensional simplex lattice with a 5-dimensional complete graph

Fig. 2

A second-order truncated 5-dimensional simplex lattice. It is obtained by replacing each vertex in Fig. 1b with a 5-dimensional complete graph. Vertices that evolving identically are labeled with the same letter. The red vertex labeled a corresponds to the marked state $\left| a \right\rangle$

2 Quantum search on the second-order lattices

Truncated simplex lattices are derived from complete graphs. A complete graph consisting of M vertices can be referred to as a M-dimensional complete graph. And a $(M+1)$-dimensional complete graph can be referred to as a zeroth-order truncated M-dimensional simplex lattice, as illustrated in Fig. 1a. Each vertex in the $(M+1)$-dimensional complete graph is linked to the remaining M vertices on the graph. A first-order M-dimensional lattice is obtained by replacing each vertex in the zeroth-order lattice with a M-dimensional complete graph, resulting in a total of $N = M(M+1)$ vertices, as shown in Fig. 1b. Similarly, a second-order M-dimensional lattice is obtained by replacing each vertex in a first-order lattice with a M-dimensional complete graph, resulting in a total of $N = M^2(M+1)$ vertices, as shown in Fig. 2 [12]. An rth-order M-dimensional lattice is obtained by replacing each vertex of the $(r-1)$th-order M-dimensional lattice with an M-dimensional complete graph. Each vertex in the simplex lattice has a degree of M.

Without the marked vertex, the Hamiltonian of the system can be expressed as follows:

$$\begin{aligned} H=-\gamma L. \end{aligned}$$

(1)

$L = A - D$ is the graph Laplacian [25], where A is the adjacency matrix ($A_{ij} = 1$ if the vertex i is connected to vertex j directly, and $A_{ij}=0$ otherwise), and D is the diagonal degree matrix ($D_{ij}=deg(i)$). With the marked vertex, the Hamiltonian can be represented as [26]:

$$\begin{aligned} H=-\gamma L- \sum _{i \in \text {marked}} \left| i \right\rangle \left\langle i \right| , \end{aligned}$$

(2)

where $|i\rangle$ is the marked state.

Table 1 The adjacency matrix A of a second-order M-dimensional simplex lattice in the invariant subspace, where ${M_l} = M - l$

In regular graphs, all vertices have the same degree. The diagonal matrix D becomes a multiple of the identity matrix, and it does not influence the quantum search. Then the Laplacian operator L can be replaced by the adjacency matrix A [27]. The Hamiltonian can be expressed as $H=-\gamma A- \sum _{i \in \text {marked}} \left| i \right\rangle \left\langle i \right|$.

The initial state is chosen the one with the equal probability distributed among the N vertices, as: $\left| {{\psi }}(0) \right\rangle = \frac{1}{\sqrt{N}} \sum _{i=1}^{N} \left| i \right\rangle$. While $\left| a \right\rangle$ is the marked state, based on the symmetry of the lattice, the second-order lattice can be seen as a system evolving in a 20-dimensional invariant subspace [16]. This subspace consists of the following basis states: $\left| a \right\rangle$, $\left| b \right\rangle = \frac{1}{\sqrt{M-1}} \sum _{i \in b} \left| i \right\rangle$, $\left| e \right\rangle = \frac{1}{\sqrt{(M-2)(M-1)}} \sum _{i \in e} \left| i \right\rangle$, $\left| v \right\rangle = \frac{1}{\sqrt{(M-3)(M-2)(M-1)}} \sum _{i \in v} \left| i \right\rangle$, and so on. The vertices corresponding to different states are represented by 20 different letters, and the vertices with the same evolution are denoted by the same letter, as shown in Fig. 2. The Hamiltonian is

$$\begin{aligned} H = -\gamma A - \left| a \right\rangle \left\langle a \right| \end{aligned}$$

(3)

where $\left| a \right\rangle \left\langle a \right|$ is considered as an oracle. The adjacency matrix expressed in the 20-dimensional subspace is shown in Table 1.

Fig. 3

a A graphical representation of the Hamiltonian for the second-order truncated five-dimensional simplex lattice. b The leading-order term for the first stage of the algorithm. c The leading-order term for the second stage of the algorithm. d The leading-order term for the third stage of the algorithm

Since $\left| {{\psi }}(0) \right\rangle \approx \left| v \right\rangle$ for large M, the objective of the quantum search is to achieve the system evolution from $\left| v \right\rangle$ to $\left| a \right\rangle$. The quantum search on the second-order lattice is structured into three sequential stages: from $\left| v \right\rangle$ to $\left| e \right\rangle$, then to $\left| b \right\rangle$, and ultimately to $\left| a \right\rangle$. We denote the critical jumping rates of these three stages as $\gamma _{c1}$, $\gamma _{c2}$, and $\gamma _{c3}$, respectively.

The search Hamiltonian can be represented by a weighted graph, as shown in Fig. 3a [22]. Based on the lattice structure, the sets $\{ \left| f \right\rangle , \left| g \right\rangle , \left| h \right\rangle , \left| j \right\rangle , \left| k \right\rangle \}$ are deemed irrelevant to the search. Therefore, we disregard the subsystem $\{ \left| f \right\rangle , \left| g \right\rangle , \left| h \right\rangle , \left| j \right\rangle , \left| k \right\rangle \}$ in the weighted graph and focus solely on the last part depicted in Fig. 3b, which serves as the leading-order term $H_1^{(0)}$ in the first stage. The leading-order term $H_1^{(0)}$ can be expressed as

$$\begin{aligned} H_1^{(0)}= & {} \left( \begin{array}{cc} H_{ab-cde}^{(0)} &{} 0\\ 0 &{} H_{lmn-opq-rtuv}^{(0)}\\ \end{array} \right) , \end{aligned}$$

(4)

where

$$\begin{aligned} H_{ab-cde}^{(0)}= & {} -\gamma \left( \begin{array}{ccccc} \frac{1}{\gamma } &{} \sqrt{M_1} &{} 0 &{} 0 &{} 0 \\ \sqrt{M_1} &{} M_2 &{} 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 &{} \sqrt{M_2} \\ 0 &{} 1 &{} 1 &{} 0 &{} \sqrt{M_2} \\ 0 &{} 0 &{} \sqrt{M_2} &{} \sqrt{M_2} &{} M_2\\ \end{array} \right) , \end{aligned}$$

(5)

$$\begin{aligned} H_{lmn-opq-rtuv}^{(0)}= & {} -\gamma \left( \begin{array}{cccccccccc} 0 &{} 1 &{} \sqrt{M_2} &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ 1 &{} 0 &{} \sqrt{M_2} &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ \sqrt{M_2} &{} \sqrt{M_2} &{} M_3 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} \sqrt{M_2} &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 1 &{} 0 &{} 1 &{} 0 &{} \sqrt{M_2} &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} \sqrt{M_2} &{} \sqrt{M_2} &{} M_3 &{} 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 1 &{} 1 &{} \sqrt{M_3} \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 &{} 1 &{} \sqrt{M_3} \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 1 &{} 1 &{} 0 &{} \sqrt{M_3} \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} \sqrt{M_3} &{} \sqrt{M_3} &{} \sqrt{M_3} &{} M_3 \\ \end{array} \right) , \end{aligned}$$

(6)

and the edge connecting c and l is disregarded now. The eigenstates of $H_{ab-cde}^{(0)}$ and $H_{lmn-opq-rtuv}^{(0)}$ can be expressed as

$$\begin{aligned}{} & {} \left| sp_{ab-cde} \right\rangle =\alpha _a \left| a \right\rangle + \alpha _b \left| b \right\rangle + \alpha _c \left| c \right\rangle + \alpha _d \left| d \right\rangle + \alpha _e \left| e \right\rangle , \end{aligned}$$

(7)

$$\begin{aligned} \left| sp_{lmn-opq-rtuv} \right\rangle{} & {} =\alpha _l \left| l \right\rangle + \alpha _m \left| m \right\rangle + \alpha _n \left| n \right\rangle + \alpha _o \left| o \right\rangle + \alpha _p \left| p \right\rangle \nonumber \\{} & {} \quad + \alpha _q \left| q \right\rangle + \alpha _r \left| r \right\rangle + \alpha _t \left| t \right\rangle + \alpha _u \left| u \right\rangle + \alpha _v \left| v \right\rangle . \end{aligned}$$

(8)

The eigenvalues $E_{ab-cde}$ and $E_{lmn-opq-rtuv}$ of $H_{ab-cde}^{(0)}$ and $H_{lmn-opq-rtuv}^{(0)}$ are the corresponding energies. The two lowest energies of the two subsystems are denoted as $E_{0,ab-cde}$ and $E_{0,lmn-opq-rtuv}$, with the eigenstates $\left| spe1 \right\rangle \approx \left| e \right\rangle$ and $\left| spv1 \right\rangle \approx \left| v \right\rangle$, respectively. To ensure the system evolution from $\left| v \right\rangle$ to $\left| e \right\rangle$, it is imperative that $E_{0,ab-cde}=E_{0,lmn-opq-rtuv}$ holds based on the results in Appendix A. As shown in Fig. 4, and the critical jumping rate $\gamma _{c1} = 3 / M$ is determined by $E_{0,ab-cde}=E_{0,lmn-opq-rtuv}$. For the second-order lattice, the edges that scale less than $\sqrt{M}$ in Fig. 3b cannot be excluded and the approximation $M-l \approx M$ and $\sqrt{M-l} \approx \sqrt{M}$ are not applicable, which are different with the quantum search on the first-order lattices [22].

Fig. 4

$\gamma _{c1}$ is determined when $E_{0,ab-cde} = E_{0,lmn-opq-rtuv}$

The total Hamiltonian is defined as $H_1 = H_1^{(0)} + H_1^{(1)}$, where the perturbation term $H_1^{(1)}$ is expressed by the edge connecting the vertices c and l, symbolizing the interaction between the subsystems $\{a, b, c, d, e\}$ and $\{l, m, n, o, p, q, r, t, u, v\}$, as the dashed line in Fig. 3b. By using the basis $\{\left| spe1 \right\rangle , \left| spv1 \right\rangle \}$, the whole Hamiltonian can be expressed as $H_1\!=\! H_{1,spv1,spv1}\!\left| spv1 \rangle \!\langle spv1 \right| \!+\!H_{1,spv1,spe1}\!\left| spv1 \rangle \!\langle spe1 \right| \!+\!H_{1,spe1,spv1}\!\left| spe1 \rangle \!\langle spv1 \right| \!+\!H_{1,spe1,spe1}\!\left| spe1 \rangle \!\langle spe1 \right| .$ The eigenstates of $H_1$ on this two-dimensional subspace are

$$\begin{aligned} \left| \phi _{1-} \right\rangle&= \frac{1}{\sqrt{2}} (\left| spv1 \right\rangle + \left| spe1 \right\rangle ), \end{aligned}$$

(9)

$$\begin{aligned} \left| \phi _{1+} \right\rangle&= \frac{1}{\sqrt{2}} (\left| spv1 \right\rangle - \left| spe1 \right\rangle ). \end{aligned}$$

(10)

The eigenvalues are denoted as $E_{1-}$ and $E_{1+}$, respectively. Therefore, we have $\left| spv1 \right\rangle \approx (\left| \phi _{1-} \right\rangle + \left| \phi _{1+} \right\rangle )/\sqrt{2}$, $\left| spe1 \right\rangle \approx (\left| \phi _{1-} \right\rangle - \left| \phi _{1+} \right\rangle )/\sqrt{2}$ and $\left| \psi (t_{1}) \right\rangle = e^{-iH_{1}t_{1}} \left| spv1 \right\rangle \approx (\left| \phi _{1-} \right\rangle + e^{-i\triangle E_{1}t_{1}} \left| \phi _{1+} \right\rangle )/\sqrt{2}$, where $\triangle E_{1}=E_{1+}-E_{1-}$, and $t_{1}$ represents the time in the first stage. The probability of the system evolving to $\left| spe1 \right\rangle$ is $| \langle spe1|\psi (t) \rangle |^{2} \approx (1-cos\triangle E_{1}t_{1})/2$. When M is large, $\left| spe1 \right\rangle \approx \left| e \right\rangle$ and $\left| spv1 \right\rangle \approx \left| v \right\rangle$. Then, the system evolves from $\left| v \right\rangle$ to $\left| e \right\rangle$ at the time $t_1 = \pi /(E_{1+} - E_{1-})$.

We represent the success probability of the system evolution from $\left| v \right\rangle$ to $\left| e \right\rangle$ as $P_1$. To study the stability of this algorithm, we assume that the jumping rate $\gamma _{1}$ is $3/M+\epsilon _1$ instead of 3/M. When $M=100$, the range of $\epsilon _1$ that ensures $P_1 \geqslant 50\%$ is $[ -2 \times 10^{-3}, 2 \times 10^{-3} ]$. Similarly, for $M=1000$ and $M=10000$, in order to ensure $P_1 \geqslant 50\%$, the value of $\epsilon _1$ should fall in the intervals of $[-6 \times 10^{-5}, 6 \times 10^{-5}]$ and $[-2 \times 10^{-6}, 2 \times 10^{-6}]$ respectively. The detailed results are given in Table 2.

Table 2 On the second-order lattice, when the target state is $\left| a \right\rangle$, the values of $\gamma _{1}$ are required in order to ensure $P_1 \geqslant 50\%$

In the second stage of the algorithm, the system evolves from $\left| \psi (t_1) \right\rangle \approx \left| e \right\rangle$ to $\left| b \right\rangle$. The leading-order term $H_{2}^{(0)}$ of the Hamiltonian is shown in Fig. 3c. We approximate $M-l \approx M$ and $\sqrt{M-l} \approx \sqrt{M}$ while excluding edges with weights less than $\sqrt{M}$. The leading-order term of the Hamiltonian can be expressed as

$$\begin{aligned} H_2^{(0)} = \left( \begin{array}{cc} H_{ab}^{(0)} &{} 0\\ 0 &{} H_{cde}^{(0)}\\ \end{array} \right) , \end{aligned}$$

(11)

where

$$\begin{aligned} H_{ab}^{(0)}&= -\gamma \left( \begin{array}{cc} 1/\gamma &{} \sqrt{M} \\ \sqrt{M} &{} M \\ \end{array} \right) , \end{aligned}$$

(12)

$$\begin{aligned} H_{cde}^{(0)}&= -\gamma \left( \begin{array}{ccc} 0 &{} 0 &{} \sqrt{M} \\ 0 &{} 0 &{} \sqrt{M} \\ \sqrt{M} &{} \sqrt{M} &{} M \\ \end{array} \right) . \end{aligned}$$

(13)

We obtained $\gamma _{c2}=2/M$ by equating the lowest energy $E_{0,ab}$ of $H_{ab}^{(0)}$ to the lowest energy $E_{0,cde}$ of $H_{cde}^{(0)}$, as depicted in Fig. 5.

Fig. 5

$\gamma _{c2}$ is determined when $E_{0,ab} = E_{0,cde}$

By using the whole Hamiltonian $H_{2}=H_{2}^{(0)}+H_2^{(1)}$, we have the eigenstates of the system $\left| \phi _{2\mp } \right\rangle = \frac{1}{\sqrt{2}} (\left| spb2 \right\rangle \pm \left| spe2 \right\rangle )$, where $\left| spb2 \right\rangle$ and $\left| spe2 \right\rangle$ are the eigenvectors of the lowest energies $E_{0,ab}$ and $E_{0,cde}$. And the eigenvalues of $\left| \phi _{2\mp } \right\rangle$ are $E_{2-}$ and $E_{2+}$, respectively. The system evolves from $\left| spe2 \right\rangle \approx \left| e \right\rangle$ to $\left| spb2 \right\rangle \approx \left| b \right\rangle$ at the time $t_2 = \pi /(E_{2+} - E_{2-})$, which can be obtained using a similar method for the derivation of $t_1$.

We denote the probability of successful evolution of this stage as $P_2$ and choose $\gamma _{2} = 2/M + \epsilon _{2}$. When $M=100$, 1000, and 10000, to ensure $P_2 \geqslant 50\%$, the ranges of $\epsilon _{2}$ are $[-1.5 \times 10^{-3}, 1.5 \times 10^{-3}]$, $[-5.5 \times 10^{-3}, 5.5 \times 10^{-5}]$ and $[-1.9 \times 10^{-6}, 1.9 \times 10^{-6}]$, respectively. The detailed results are shown in Table 3.

Table 3 On the second-order lattice, when the target state is $\left| a \right\rangle$, the values of $\gamma _{2}$ are required in order to ensure $P_2 \geqslant 50\%$

In the third stage of the algorithm, the initial state is $\left| b \right\rangle$, and the target state is $\left| a \right\rangle$. As presented in Fig. 3d, in the subspace spanned by the basis states $|a\rangle$ and $|b\rangle$, the leading-order term $H_{3}^{(0)}=-\left( |a\rangle \langle a| +\gamma M |b\rangle \langle b|\right)$. We obtained the critical jumping rate $\gamma _{c3} = 1/M$ by setting the two eigenvalues to be equal. By introducing the perturbation $H_{3}^{(1)}=-\left( \gamma \sqrt{M}|a\rangle \langle b| +\gamma \sqrt{M} |b\rangle \langle a|\right)$, we obtain the eigenstates and eigenvalues of the whole Hamiltonian $H_3=H_3^{(0)} + H_3^{(1)}$:

$$\begin{aligned} |\phi _{3-}\rangle =\frac{1}{\sqrt{2}} (\left| a \right\rangle + \left| b \right\rangle )&, E_{3-}=-1-\sqrt{\frac{1}{M}}, \end{aligned}$$

(14)

$$\begin{aligned} |\phi _{3+}\rangle =\frac{1}{\sqrt{2}} (\left| a \right\rangle - \left| b \right\rangle )&, E_{3+}=-1+\sqrt{\frac{1}{M}}. \end{aligned}$$

(15)

The system evolves into $\left| a \right\rangle$ when $t_3 = \pi / (E_{3+} - E_{3-})=\frac{\pi \sqrt{M}}{2}$.

Assuming the success probability of this stage as $P_3$, we consider $\gamma _{3}=1/M+\epsilon _3$. To ensure $P_3 \geqslant 50\%$ when $M=100$, 1000, and 10000, $\epsilon _3$ must fall in the intervals of $[-2.5 \times 10^{-3}, 2.5 \times 10^{-3}]$, $[-5.5 \times 10^{-5}, 5.5 \times 10^{-5}]$, and $[-1.9 \times 10^{-6}, 1.9 \times 10^{-6}]$, respectively (Table 4).

Table 4 On the second-order lattice, when the target state is $\left| a \right\rangle$, the values of $\gamma _{3}$ are required in order to ensure $P_3 \geqslant 50\%$

For the three-stage quantum search on the second-order lattice, we have obtained the three critical jumping rates $\gamma _{c1} = 3/M$, $\gamma _{c2} = 2/M$ and $\gamma _{c3} = 1/M$. The probability of a successful search on the second-order lattice is depicted in Fig. 6. As M increases, the success probability is close to $100\%$.

Fig. 6

Success probabilities of the quantum search on the second- and third-order truncated M-simplex lattices

Fig. 7

Degenerate perturbation theory on second-order lattices

3 Rules for using degenerate perturbation theory

In the second-order lattice, the structure formed by the set $\{\left| a \right\rangle , \left| b \right\rangle , \left| c \right\rangle , \left| d \right\rangle , \left| e \right\rangle \}$ is referred to as a first-order complete subgraph, which is denoted as A1 in Fig. 7a. Similarly, the structure formed by the set $\{\left| l \right\rangle , \left| m \right\rangle , \left| n \right\rangle , \left| o \right\rangle , \left| p \right\rangle , \left| q \right\rangle , \left| r \right\rangle , \left| t \right\rangle , \left| u \right\rangle , \left| v \right\rangle \}$ is also a first-order complete subgraph denoted by C1. It can be observed that the second-order lattice is constructed by $M+1$ first-order complete subgraphs, as depicted in Fig. 7a. A1, B1, and C1 represent distinct first-order complete subgraphs.

The first stage of the quantum search on the second-order lattice takes place between the first-order complete subgraphs, from C1 to A1. C1 can evolve directly to A1 without going through B1. Moreover, the initial state approximates a superposition of states within C1, making the presence or absence of B1 inconsequential to the initial state. The marked vertex in not in B1, in the quantum search process, the probability of evolving to B1 is small and can be ignored. Therefore, we determined the critical jumping rate $\gamma _{c1}=3/M$ by considering only the two first-order complete subgraphs C1 and A1 to account for degeneracy.

In the first stage of the search on the second-order lattice, there are two differences from the approach proposed in zeroth- and first-order lattice search. First, because the two sets $\{\left| a \right\rangle , \left| b \right\rangle \}$ and $\{\left| r \right\rangle , \left| t \right\rangle , \left| u \right\rangle , \left| v \right\rangle \}$ are not directly connected, the critical jumping rate $\gamma _{c1}$ cannot be determined by considering only these two subsystems. Second, the elements with a value of 1 in the leading-order Hamiltonian cannot be omitted, and the approximations $M-l \approx M$ and $\sqrt{M-l} \approx \sqrt{M}$ are unavailable. The reason is that these approximations result in a significant change in the graph structure represented by the resulting matrix, compared to the original structure. In zeroth- and first-order structures, these changes are minor. In second-order and even higher-order structures, these changes are so substantial that the critical jumping rate cannot be accurately determined with these approximations.

In the first-order complete subgraph A1, the structures that formed by the vertices $\{\left| a \right\rangle , \left| b \right\rangle \}$ and $\{\left| c \right\rangle , \left| d \right\rangle , \left| e \right\rangle \}$ are referred to as zeroth-order complete subgraphs, as depicted in Fig. 7b. A2 and B2 represent two categories of zeroth-order complete subgraphs.

In the second stage of the quantum search, the evolution from $\left| e \right\rangle$ to $\left| b \right\rangle$ can be approximated as the evolution from B2 to A2. This stage occurs between two zeroth-order complete subgraphs. The third search stage from $\left| b \right\rangle$ to $\left| a \right\rangle$ occurs between two vertices in the zeroth-order complete subgraph A2, as shown in Fig. 7c. The structures involved in these two stages are simpler. Regardless of whether we retain the weighted edge 1 and make the approximations $M-l \approx M$ and $\sqrt{M-l} \approx \sqrt{M}$, we can obtain the exact value of $\gamma _c$.

To prove the generality of the above method, we have extended the application of degenerate perturbation theory to the third-order lattice. A third-order lattice is constructed by replacing each vertex of a second-order lattice with an M-dimensional complete graph, as depicted in Fig. 8. By symmetry, the system of the third-order lattice evolves in a 67-dimensional invariant subspace. This subspace comprises the states $\left| a \right\rangle$, $\ldots$, $\left| z \right\rangle$, $\left| a1 \right\rangle$, $\ldots$, $\left| z1 \right\rangle$ and $\left| a2 \right\rangle$, $\ldots$, $\left| o2 \right\rangle$, as shown in Fig. 8.

Fig. 8

A third-order truncated five-dimensional simplex lattice. Vertices that evolving identically are labeled with the same letter. The red vertex is the marked vertex a

The structures formed by the vertices corresponding to the sets $\{\left| a \right\rangle , \dots , \left| e \right\rangle \}$, $\{\left| p \right\rangle , \dots , \left| d1 \right\rangle \}$ and $\{\left| e1 \right\rangle , \dots , \left| o2 \right\rangle \}$ are referred to as second-order complete subgraphs. And the third-order lattice can be regarded as $M+1$ interconnected second-order complete subgraphs, as depicted in Fig. 9a. A1, B1, and C1 represent three types of second-order complete subgraphs.

The quantum search on the third-order lattice is a four-stage algorithm. When M is large, the first stage of the quantum search on the third-order lattice can be seen as the evolution from the second-order complete subgraph C1 to A1. Hence, we consider A1 and C1 to account for degeneracy and determine the critical jumping rate $\gamma _{c1,3rd-order}$.

Subsequently, the following stages of the quantum search follow a similar evolution as the one on the second-order lattice: at the second stage, the degeneracy of the first-order complete subgraphs represented by A2 and B2 in A1 are considered to determine $\gamma _{c2,3rd-order}$, as depicted in Fig. 9b; at the third stage, we consider the degeneracy of the zeroth-order complete subgraphs represented by A3 and B3 in A2 in order to determine $\gamma _{c3,3rd-order}$, as shown in Fig. 9c; at the fourth stage, we consider the degeneracy of the vertices a and b in A3 to determine $\gamma _{c4,3rd-order}$, as illustrated in Fig. 9d. The critical jumping rates $\gamma _{c}$ of the three stages as depicted in Fig. 10: $\gamma _{c1,3rd-order} \approx 4/M$, $\gamma _{c2,3rd-order} \approx 3/M$, $\gamma _{c3,3rd-order} \approx 2/M$. For the fourth stage, $\gamma _{c4,3rd-order}=1/M$ can be directly computed as discussed in Sect. 2.

It is important to note that at the first and second stages, the edges with a weight of 1 in the second-order complete subgraphs and the first-order complete subgraphs cannot be omitted. Additionally, the approximations $M-l \approx M$ and $\sqrt{M-l} \approx \sqrt{M}$ are not applicable.

Fig. 9

Degenerate perturbation theory on third-order lattice

Fig. 10

In quantum search on the third-order lattice, $\gamma _{c1,3rd-order} \approx 4/M$, $\gamma _{c2,3rd-order} \approx 3/M$, and $\gamma _{c3,3rd-order} \approx 2/M$ can be obtained through numerical calculations

In the construction of leading-order terms based on different orders of complete subgraphs, we observed the correlation between the use of degenerate perturbation theory and the lattice structure. To demonstrate the dependency of degenerate perturbation theory on the structure, we have added two simulation experiments involving a set of marked vertices. In the first experiment, for a second-order lattice, we select $\left| e \right\rangle$ as the marked state which contains $(M-1)(M-2)$ vertices, as depicted in Fig. 11. The search Hamiltonian is

$$\begin{aligned} H=-\gamma A- \left| e \right\rangle \left\langle e \right| . \end{aligned}$$

(16)

This quantum search is a one stage algorithm. Here, we use two schemes to determine the critical jumping rate. The first scheme closely resembles the one discussed in Sect. 2. The leading-order term of the Hamiltonian aligns with the one given by Eq. 4, differing only in

$$\begin{aligned} H_{ab-cde}^{(0)} = -\gamma \left( \begin{array}{ccccc} 0 &{} \sqrt{M_1} &{} 0 &{} 0 &{} 0 \\ \sqrt{M_1} &{} M_2 &{} 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 &{} \sqrt{M_2} \\ 0 &{} 1 &{} 1 &{} 0 &{} \sqrt{M_2} \\ 0 &{} 0 &{} \sqrt{M_2} &{} \sqrt{M_2} &{} \frac{1}{\gamma }+M_2\\ \end{array} \right) . \end{aligned}$$

(17)

The critical jumping rate $\gamma _{c,marked(e)}$ is determined by the two lowest energies $E_{0,ab-cde}$ and $E_{0,lmn-opq-rtuv}$ of the subsystems $\{\left| a \right\rangle ,\left| b \right\rangle ,\left| c \right\rangle ,\left| d \right\rangle ,\left| e \right\rangle \}$ and $\{\left| l \right\rangle ,\left| m \right\rangle ,\left| n \right\rangle ,\left| o \right\rangle , \left| p \right\rangle , \left| q \right\rangle , \left| r \right\rangle , \left| t \right\rangle , \left| u \right\rangle , \left| v \right\rangle \}$, respectively. And $\gamma _{c,\text {marked}(e)}=M$ as illustrated in Fig. 12a.

Fig. 11

In the second-order lattice, we consider $\left| e \right\rangle$ as the marked state. The vertices that undergo the same evolution are represented by the same letter

Fig. 12

In the second-order lattice, $M=100$, and $\left| e \right\rangle$ is the marked state. a We use $\{\left| a \right\rangle ,\left| b \right\rangle , \left| c \right\rangle ,\left| d \right\rangle ,\left| e \right\rangle \}$ and $\{\left| l \right\rangle ,\left| m \right\rangle ,\left| n \right\rangle , \left| o \right\rangle ,\left| p \right\rangle ,\left| q \right\rangle ,\left| r \right\rangle ,\left| t \right\rangle ,\left| u \right\rangle ,\left| v \right\rangle \}$ to construct the Hamiltonian. b We use $\{\left| c \right\rangle ,\left| d \right\rangle ,\left| e \right\rangle \}$ and $\{\left| l \right\rangle ,\left| m \right\rangle ,\left| n \right\rangle ,\left| r \right\rangle ,\left| t \right\rangle ,\left| u \right\rangle ,\left| v \right\rangle \}$ to construct the Hamiltonian

Based on the lattice structure shown in Fig. 11, the set $\{\left| r \right\rangle ,\left| t \right\rangle ,\left| u \right\rangle ,\left| v \right\rangle \}$ is connected to the set $\{\left| c \right\rangle ,\left| d \right\rangle ,\left| e \right\rangle \}$ through the set $\{\left| l \right\rangle ,\left| m \right\rangle ,\left| n \right\rangle \}$. The two kinds of sets $\{\left| a \right\rangle ,\left| b \right\rangle \}$ and $\{\left| o \right\rangle ,\left| p \right\rangle ,\left| q \right\rangle \}$ are unrelated to the evolution. Therefore, we only retain the parts of $\{\left| c \right\rangle ,\left| d \right\rangle ,\left| e \right\rangle \}$ and $\{\left| l \right\rangle ,\left| m \right\rangle \, \left| n \right\rangle ,\left| r \right\rangle \, \left| t \right\rangle ,\left| u \right\rangle ,\left| v \right\rangle \}$ in the leading-order term, as shown in Fig. 13. We consider this method as the second scheme. By setting the lowest energy of $\{\left| c \right\rangle ,\left| d \right\rangle ,\left| e \right\rangle \}$ equal to the lowest energy of $\{\left| l \right\rangle ,\left| m \right\rangle \, \left| n \right\rangle ,\left| r \right\rangle \, \left| t \right\rangle ,\left| u \right\rangle ,\left| v \right\rangle \}$, the critical jumping rate $\gamma '_{c,marked(e)} = M$ can be determined, as illustrated in Fig. 12b. This result is consistent with the first scheme. Further calculations confirm that the system indeed has a high probability of evolving to $\left| e \right\rangle$ when $\gamma _{marked(e)}=M$.

It is found that the success of the second scheme can be attributed to the fact that after omitting $\{\left| a \right\rangle ,\left| b \right\rangle \}$ and $\{\left| o \right\rangle ,\left| p \right\rangle ,\left| q \right\rangle \}$, the structures corresponding to the sets $\{\left| c \right\rangle ,\left| d \right\rangle ,\left| e \right\rangle \}$ and $\{\left| l \right\rangle ,\left| m \right\rangle ,\left| n \right\rangle ,\left| r \right\rangle ,\left| t \right\rangle ,\left| u \right\rangle ,\left| v \right\rangle \}$ share the same overall shape, despite containing different types of vertices. The same overall shapes of the two subsystems are called structural consistency.

Fig. 13

When considering $\left| e \right\rangle$ as the marked state, the leading-order term that only involves $\{\left| c \right\rangle ,\left| d \right\rangle ,\left| e \right\rangle \}$ and $\{\left| l \right\rangle ,\left| m \right\rangle ,\left| n \right\rangle ,\left| r \right\rangle ,\left| t \right\rangle ,\left| u \right\rangle ,\left| v \right\rangle \}$ is shown. The dashed lines from the vertices c connect to the other structures formed by the set $\{\left| l \right\rangle ,\left| m \right\rangle ,\left| n \right\rangle ,\left| r \right\rangle ,\left| t \right\rangle ,\left| u \right\rangle ,\left| v \right\rangle \}$

Now, we summarize the guidelines of using degenerate perturbation theory for the quantum search on an rth-order lattice. Here, we provide several definitions: (1) The $(r-1)$th-order complete subgraph is defined as the secondary structure of an rth-order lattice, and similarly, a $(r-2)$th-order complete subgraph is considered as the secondary structure of the $(r-1)$th-order complete subgraph. (2) We designate the secondary structure associated with the initial state as the ”initial secondary structure” and the secondary structure associated with the target state as the ”target secondary structure”. (3) When some vertices within the $(r-1)$th-order complete subgraph are excluded, we still refer to the resulting structure as a secondary structure of the rth-order lattice. (4) The set of basis states associated with a complete graph is referred to as a basis group, like $\{\left| a \right\rangle ,\left| b \right\rangle \}$ and $\{\left| o \right\rangle ,\left| p \right\rangle ,\left| q \right\rangle \}$.

The first step of the quantum search is to identify the initial and target secondary structures. Afterward, we eliminate the basis groups unrelated to the search. Finally, we establish degeneracy between the remaining components of the two secondary structures to determine the critical jumping rate. A basis group can be considered as a set unrelated to the search and can be omitted only when it satisfies the following two constraints:

(1) The basis group is not part of the shortest path between the initial and target states. (2) After the omission of the basis groups, structural consistency can still be retained in the initial and target secondary structures. Following these two constraints, we can effectively reduce the dimension of the Hamiltonian through this omission, resulting in simplified computations.

We consider the search on the third-order lattice with the marked state $\left| o \right\rangle$ in Fig. 14 as an example to demonstrate the above guidelines. The Hamiltonian of the system is

$$\begin{aligned} H=-\gamma A- \left| o \right\rangle \left\langle o \right| . \end{aligned}$$

(18)

We have determined the critical jumping rates by using the above two schemes, as illustrated in Fig. 15. The two schemes all provide the correct critical jumping rate $M^2$. It has been demonstrated that when $\gamma _{marked(o)}=M^2$, the system can effectively evolve from the state $\left| o2 \right\rangle$ to the state $\left| o \right\rangle$ with a high probability.

Fig. 14

In the third-order truncated five-dimensional simplex lattice, $\left| o \right\rangle$ is the marked state

Fig. 15

In the third-order lattice, when $\left| o \right\rangle$ is the marked state, we displayed the target and initial secondary structures, as well as the modified versions of these structures obtained after omitting specific basis groups that are unrelated to the search

4 The impact of varying the positions of marked vertices

Fig. 16

Another case where there’s only one marked vertices on a second-order lattice

In the second-order lattice, the marked vertex labeled as a can be positioned differently, as illustrated in Fig. 16. This variation leads to an increase in the dimension of the invariant subspace from 20 to 47, which includes states $\{\left| a \right\rangle ,\dots ,\left| z \right\rangle \}$ and $\{\left| a1 \right\rangle ,\dots ,\left| u1 \right\rangle \}$.

The initial state is the uniform superposition of all states, given by $\left| {{\psi }}(0) \right\rangle =\frac{1}{\sqrt{N}} \sum _{i=1}^{N} \left| i \right\rangle$. When M is large, we have $\left| {{\psi }}(0) \right\rangle \approx \left| u1 \right\rangle$.

Fig. 17

The evolution to the target state on the second lattice when the marked vertex is positioned differently

The evolution of the system still has three stages, from $\left| {{\psi }}(0) \right\rangle \approx \left| u1 \right\rangle$ to $\left| j \right\rangle$, then to $\left| c \right\rangle$, and finally to $\left| a \right\rangle$, as shown in Fig. 17. The critical jumping rates of the three stages are $\gamma '_{c1}=3/M$, $\gamma '_{c2}=2/M$ and $\gamma '_{c3}=1/M$, respectively. This result is consistent with the findings in Sect. 2. It can be observed that in the second-order lattice, when there is one marked vertex, the different positions of the marked vertex does not affect the values of the critical jumping rates.

For the two quantum searches on the second-order lattice where there is only one marked vertex, as shown in Figs. 2 and 16, further calculations reveal that the time required for each stage is approximately the same. The corresponding structures of the two different marked vertices for each stage are identical, which implies that the different positions of the marked vertex have no effect on the search.

To further investigate the impact of the marked vertices’ positions on quantum search, we consider the quantum search on the second-order lattice with two marked vertices. And five different configurations are analyzed, as depicted in Fig. 18. The corresponding results of the analysis are presented in Table 5.

Fig. 18

Five configurations of the two marked vertices in the second-order lattice, where $M=5$. The vertices that evolve identically are represented by the same letter

Table 5 The five cases of search with two marked vertices, shown in Fig. 18, with the subspace dimension, the three stages’ critical jumping rate($\gamma _{c}$), and evolution

In Fig. 18b and c, the two marked vertices are located in the same first-order complete subgraph, resulting in $\gamma _{c1,Fig(b)}=\gamma _{c1,Fig(c)}=4/M$ for the first stage. In Fig. 18d and e, the two marked vertices are in two different first-order complete subgraphs, leading to $\gamma _{c1,Fig(d)}=\gamma _{c1,Fig(e)}=3/M$ for the first stage. For the second stage, in Fig. 18b–e, the two marked vertices are situated on different zeroth-order complete subgraphs, yielding $\gamma _{c2,Fig(b)}=\gamma _{c2,Fig(c)}=\gamma _{c2,Fig(d)}=\gamma _{c2,Fig(e)}=2/M$. With the above results, we can consider the searches in Fig. 18b and c as equivalent, as well as the searches in Fig. 18d and e. Therefore, we conclude that changing the positions of the marked vertices does not affect the search, as long as the number of marked vertices and the corresponding secondary structures remain constant.

In comparison to Fig. 18b and c, the two marked vertices in Fig. 18a are positioned on one zeroth-order complete subgraph. In the second search stage in Fig. 18a, the target secondary structure consists of only one zeroth-order complete subgraph, whereas in Fig. 18b and c, the target secondary structure involves two zeroth-order complete subgraphs. This distinct configuration results in $\gamma _{c2,Fig(a)}=3/M$ in Fig. 18a, which is different from $\gamma _{c2,Fig(b)}=\gamma _{c2,Fig(c)}=2/M$ in Fig. 18b and c. This finding aligns with [25], stating that the numerator of $\gamma _{c}$ increases by 1 when the number of marked vertices on the same target secondary structure increases by 1. This local difference has an impact on the overall search process. So in Fig. 18b and c, $\gamma _{c1,Fig(b)}=\gamma _{c1,Fig(c)}=4/M$, while in Fig. 18a, $\gamma _{c1,Fig(a)}=(4+1)/M=5/M$. Thus, we conclude that different evolution in lower-order substructures will influence the evolution in higher-order structures.

It is observed that in Fig. 18d and e, the critical jumping rates of each stage are identical to the case with only one marked vertex. Furthermore, we have obtained that in Fig. 18d and e, the number of stages, and the time are the same as the ones in the previously discussed cases with one marked vertex. This result implies that when the marked vertices are located in different secondary structures, the searches among these substructures do not affect each other. In Fig. 18d and e, the search can be viewed as two parallel processes searching for a single marked vertex on the second-order lattice. Similarly, in Fig. 18b and c, the two second stages of search processes are equivalent to two parallel processes searching for a single marked vertex on a first-order subgraph.

This observation is further supported by the search illustrated in Fig. 19. There are three marked vertices, with a and b situated in the same zeroth-order complete graph, while d is located in another zeroth-order complete graph. When M is large enough, the initial state $\left| {{\psi }}(0) \right\rangle \approx \left| m \right\rangle$. According to the results presented in Fig. 19b, when we want the system to evolve toward $\{\left| a \right\rangle , \left| b \right\rangle \}$, the jumping rate should be $\gamma _{c1,marked(a \& b)} \approx 3/M$. This aligns with the case of having only a and b as marked vertices without the marked vertex d on the first-order lattice. When the system evolves toward $\left| d \right\rangle$, the jumping rate $\gamma _{c1,marked(d)} \approx 2/M$. This matches the scenario of having a single marked vertex on the first-order lattice. Therefore, we can conclude that the search for different secondary structures does not interfere with each other when the marked vertices are located in distinct secondary structures.

Fig. 19

a The scenario of three marked vertices in the first-order lattice. b The critical jumping rates of the first stage

5 Conclusion

In this paper, degenerate perturbation theory is applied to quantum search on the second-order truncated simplex lattice to determine the critical jumping rate $\gamma _{c}$. With the $\gamma _{c}$, the system can evolve into the target state at an appropriate time. The construction of the leading-order term of the Hamiltonian must consider the lattice structure. Specifically, when the lattice order exceeds 1, edges with weight 1 in the secondary structure, as well as l in $M-l$ and $\sqrt{M-l}$, cannot be omitted.

From the results of the quantum search on the second- and third-order lattices, we have observed that the basis groups can be disregarded if they satisfy the following two constraints: (1) They are not part of the shortest path between the initial state and the target state. (2) After the omission of the basis groups, the structural consistency can still be retained. By employing this omission, the calculations can be substantially simplified.

We have also shown that the change in the position of the single marked vertex on the second-order lattice has no impact on the three-stage search. To examine the influence of the marked vertices’ positions on the search, five distinct configurations of two marked vertices have been studied. Our results reveal three rules regarding the impact of different configurations: (1) When the number of marked vertices and the secondary structures they are located in remain constant, the variations of their positions do not affect the search. (2) Different evolution in lower-order substructures have an influence on the evolution in higher-order structures. (3) The search for different secondary structures does not interfere with each other when the marked vertices are located on separate secondary structures. Our research provides support for the application of degenerate perturbation theory in continuous-time quantum walk and may be a valuable reference for its implementation in other structures.

Appendix

This section provides an example illustrating the necessity of aligning the energies of the two ground states of the two interacted subsystems. Without loss of generality, we consider a quantum system in a two-dimensional Hilbert space. The Hilbert space of this system is spanned by the basis states $\{\left| 0 \right\rangle , \left| 1 \right\rangle \}$. Here, $\left| 0 \right\rangle$ and $\left| 1 \right\rangle$ are the two states of the two subsystems which equivalent to the subsystems mentioned in the main text, such as $\{ab-cde\}$ and $\{lmn-opq-rtuv\}$.

Without loss of generality, the initial state is $\left| 1 \right\rangle$, the marked state is $\left| 0 \right\rangle$. and the Hamiltonian is expressed as $H = \begin{bmatrix} E_1 &{} 1 \\ 1 &{} E_2 \end{bmatrix}$. The Hamiltonian can be divided into two parts $H=H^{(0)}+H^{(1)}$, where the leading-order term $H^{(0)} = \begin{bmatrix} E_1 &{} 0 \\ 0 &{} E_2 \end{bmatrix}$ and the perturbation term $H^{(1)} = \begin{bmatrix} 0 &{} 1 \\ 1 &{} 0 \end{bmatrix}$. Without the perturbation, the energies of the two subsystems are $E_1$ and $E_2$, respectively.

The eigenstates and eigenvalues of the whole Hamiltonian $H=H^{(0)}+H^{(1)}$ are

$$\begin{aligned} |\phi _{-}\rangle =((\alpha - \beta )\left| 0 \right\rangle + \left| 1 \right\rangle )/\gamma _1&, E_{-}=(E_1+E_2-2\beta )/2, \end{aligned}$$

(19)

$$\begin{aligned} |\phi _{+}\rangle =((\alpha + \beta )\left| 0 \right\rangle + \left| 1 \right\rangle )/\gamma _2&, E_{+}=(E_1+E_2+2\beta )/2. \end{aligned}$$

(20)

where $\alpha =(\triangle E)/2$, $\beta =\sqrt{\triangle E^2+4}/2$, $\gamma _1=\sqrt{2\beta ^2-2\alpha \beta }$, $\gamma _2=\sqrt{2\beta ^2+2\alpha \beta }$ and $\triangle E=E_2-E_1$. From the above two equations, we have $\left| 0 \right\rangle = ( |\phi _-\rangle - |\phi _+\rangle )/\sqrt{2}$ and $\left| 1 \right\rangle = ((\alpha +\beta )|\phi _-\rangle - (\alpha -\beta )|\phi _+\rangle )/\sqrt{\triangle E^2+2}$. With the initial state $\left| 1 \right\rangle$, the evolution of the system is described by $|\psi (t)\rangle = e^{-iHt}\left| 1 \right\rangle$. And we have $|\psi (t)\rangle = ((\alpha +\beta )|\phi _-\rangle - e^{-i\triangle E' t}(\alpha -\beta )|\phi _+\rangle )/\sqrt{\triangle E^2+2}$, where $\triangle E'=E_+-E_-=2\beta$. The probability of the system evolving into the marked state $\left| 0 \right\rangle$ is

$$\begin{aligned} |\langle 0|\psi (t_1)\rangle |^2=\frac{1}{2}(1-\frac{2-\triangle E^2}{2+\triangle E^2}\cos {\triangle E' t}). \end{aligned}$$

(21)

.

The probability can attain its maximal value 1 when $\triangle E=0$ ($E_1 = E_2$), and $t=\pi /\triangle E'$. In conclusion, the system can only evolve from one state to the other one if the corresponding energies of the two subsystems are equal without the perturbation term.