# Multimarked Spatial Search by
Continuous-Time Quantum Walk

Pedro H. G. Lugão  National Laboratory of Scientific Computing (LNCC)
Petrópolis, RJ, 25651-075, Brazil  Renato Portugal  National Laboratory of
Scientific Computing (LNCC) Petrópolis, RJ, 25651-075, Brazil  Mohamed Sabri
Department of Mathematics The Open University of Sri Lanka Nawala, Nugegoda,
10250, Sri Lanka  Hajime Tanaka  Research Center for Pure and Applied
Mathematics Graduate School of Information Sciences Tohoku University, Sendai
980-8579, Japan

###### Abstract

The quantum-walk-based spatial search problem aims to find a marked vertex
using a quantum walk on a graph with marked vertices. We describe a framework
for determining the computational complexity of spatial search by continuous-
time quantum walk on arbitrary graphs by providing a recipe for finding the
optimal running time and the success probability of the algorithm. The quantum
walk is driven by a Hamiltonian derived from the adjacency matrix of the graph
modified by the presence of the marked vertices. The success of our framework
depends on the knowledge of the eigenvalues and eigenvectors of the adjacency
matrix. The spectrum of the Hamiltonian is subsequently obtained from the
roots of the determinant of a real symmetric matrix $M$, the dimensions of
which depend on the number of marked vertices. The eigenvectors are determined
from a basis of the kernel of $M$. We show each step of the framework by
solving the spatial searching problem on the Johnson graphs with a fixed
diameter and with two marked vertices. Our calculations show that the optimal
running time is $O(\sqrt{N})$ with an asymptotic probability of $1+o(1)$,
where $N$ is the number of vertices.

Keywords: Continuous-time quantum walk, spatial quantum search, Johnson graph,
multiple marked vertices

##  1 Introduction

Farhi and Gutmann [1] introduced the continuous-time quantum walk as a
discrete-space version of the Schrödinger equation, where the positions of the
particle are the vertices of a graph, specifically, a tree whose nodes
represent solutions to a decision problem [2]. Childs and Goldstone [3] used
the continuous-time quantum walk to address the spatial search problem with
one marked vertex, the goal being to locate the marked vertex when the walk
departs from an initial state that is easy to prepare. The evolution is based
on a Hamiltonian, which includes an extra term that depends on the location of
the marked vertex and differs from the Hamiltonian used by Farhi and Gutmann,
which is solely based on the graph’s adjacency matrix. Childs and Goldstone
analyzed the search on lattices, hypercubes, and complete graphs to determine
whether the quantum-walk-based search algorithm is faster than the random-
walk-based one on the same graphs. They obtained negative results in some
cases, for instance, on $d$-dimensional lattices with $d\leqslant 4$. However,
this should not be interpreted as definitive evidence that it is impossible to
find a quantum-walk-based search algorithm that provides a speedup over the
best random-walk-based case. In fact, using alternative discrete-time quantum
walk models, it is possible to achieve a quadratic speedup for $d$-dimensional
lattices with $d\geqslant 2$ [4, 5].

The origin of the quantum-walk-based spatial search problem lies in the
confluence of two proposals: Farhi and Gutmann’s 1998 suggestion for
accelerating random walks on decision trees using a continuous-time quantum
walk [1], and Benioff’s 2000 proposition to apply Grover’s algorithm [6] with
the aim of speeding up classical search algorithms for a marked vertex on the
two-dimensional lattice [7]. Following the contributions of these authors, the
area of quantum-walk-based spatial search algorithms has diverged into two
different formulations in the literature. Both are significant as they expose
distinct computational and mathematical aspects of quantum walks.

The first formulation investigates whether a quantum walk on a graph $G$
requires fewer steps to find a marked vertex than a classical random walk on
the same graph $G$. This formulation was introduced by Shenvi et al. [8], who
showed that a quantum walk on a hypercube locates a marked vertex faster than
a random walk. In a context close related to the spatial search algorithm,
Childs et al. [9] showed that the propagation of a particle between a specific
pair of nodes is exponentially faster when driven by a continuous-time quantum
walk as compared to a random walk. Numerous papers in the literature address
this formulation in both the discrete-time [8, 10, 11, 12] and continuous-time
[3, 13, 14, 15, 16, 17, 18, 19, 20, 21] cases. The results of this work align
with this formulation. Experimental implementations of search algorithms by
continuous-time quantum walk are described in [22, 23, 24, 25].

The second formulation asks whether the number of steps that a classical
random walk on a graph $G$ takes to find a marked vertex $v\in V(G)$ can be
reduced by implementing a quantum walk on any graph $G^{\prime}$, so that the
quantum walk on $G^{\prime}$ would uncover the necessary information to find
the vertex $v$ in the original graph $G$. This formulation was introduced by
Szegedy [26], who showed that the quantum hitting time of a quantum walk on
the bipartite graph $G^{\prime}$ obtained from a graph $G$, where the random
walk takes place, is quadratically less than the classical hitting time.
However, to locate a marked vertex, it remains essential to prove that the
success probability is $\Omega(1)$. Many papers in the literature have
addressed the second formulation in both the discrete-time [27, 28, 29, 30]
and continuous-time [31, 32] cases. In all these papers, the quantum walk
takes place on a bipartite graph $G^{\prime}$ derived from $G$ via a
duplication process and the random walk takes place on an almost arbitrary
graph $G$ with multiple marked vertices. Ambainis et al. [30] effectively
resolved Szegedy’s problem by showing that there is a quadratic speedup for
finding a marked vertex with success probability $\tilde{\Omega}(1)$ on an
arbitrary graph $G$ by discrete-time quantum walk on $G^{\prime}$. Apers et
al. [32] go along the same line by continuous-time quantum walk. Somma and
Ortiz [33] have described an interesting method to address combinatorial
optimization problems that was used in [31] to modify the standard method
proposed by Childs and Goldstone [3] for the case with one marked vertex.

In this work, we address the first formulation of the spatial search problem
by continuous-time quantum walk on arbitrary graphs with multiple marked
vertices. Additionally, we provide a framework to determine the computational
complexity of the search algorithm that is successful when the gap of two key
eigenvalues $\lambda^{\pm}$ of the Hamiltonian is small enough. Note that our
aim differs from the one described in references [13, 20], which focus on
obtaining optimality conditions, namely, a time complexity that has a
quadratic speedup compared to random walks. Our method may result in non-
optimal time complexity, but it remains interesting if it is better than
$O(N)$. For instance, the $d$-dimensional lattice with multiple marked
vertices, where $d=2$ and $d=3$, are interesting candidates. These were
analyzed in the reference [3], but only for the case with one marked vertex.
As an example of our framework, we analyze in full detail the search algorithm
on the Johnson graph with two marked vertices. The framework is based on a
real symmetric matrix $M$, which depends on the entries of the adjacency
matrix and on the locations of the marked vertices. The fact that the
determinant of this matrix is zero allows us to find the spectrum of the
Hamiltonian. Then, we can find the gap between $\lambda^{\pm}$ and all
quantities necessary to determine the algorithm’s optimal running time and the
success probability assuming that the gap tends to zero when the number of
vertices increases. The relevant quantities are basically the overlaps between
the marked vertices and the initial condition with the eigenvectors of the
Hamiltonian associated with $\lambda^{\pm}$.

The Johnson graph $J(n,k)$ plays an important role in quantum walks because it
is used in the element distinctness algorithm [27] and in many spatial search
algorithms [34, 35]. The vertices of $J(n,k)$ are $k$-subsets of a set with
$n$ elements and two vertices are adjacent if and only if the intersection of
these vertices is a $(k-1)$-subset. In this work, we use the Johnson graph
$J(n,k)$ with two marked vertices as an example of all steps of our framework
for determining the time complexity of the spatial search algorithm by
continuous-time quantum walk. We show that the optimal running time to find a
marked vertex is $\pi k\sqrt{N}/(2\sqrt{2})$ with asymptotic probability
$1+o(1)$ when $k$ is fixed.

The structure of this paper is as follows. In Sec. 2, we lay out a framework
for determining the computational complexity of the spatial search algorithm
by continuous-time quantum walk on graphs with multiple marked vertices. In
Sec. 3, we apply this framework to analyze with mathematical rigor the spatial
search algorithm on the Johnson graph with two marked vertices. Finally, in
Sec. 4, we present our concluding remarks.

##  2 Multimarked framework

Let $G(V,E)$ be a finite connected simple graph with vertex set $V$ and edge
set $E$. We associate $G$ with a Hilbert space $\mathcal{H}$ with
computational basis $\\{|v\rangle:v\in V\\}$, as is usually done in the
definition of the continuous-time quantum walk [1]. Let $W$ be the set of
marked vertices. We consider the time-independent Hamiltonian of the form [3]

$H=-\gamma A-\sum_{w\in W}\big{|}w\big{\rangle}\big{\langle}w\big{|},$ (1)

where $A$ denotes the adjacency matrix of $G(V,E)$, and $\gamma$ is a real and
positive parameter. The spatial search algorithm starts with the initial state
$\big{|}\psi(0)\big{\rangle}$, which is a normalized eigenvector of $-\gamma
A$ associated with the largest eigenvalue of $A$. If $G$ is regular,
$\big{|}\psi(0)\big{\rangle}$ is the uniform superposition of the
computational basis

$\big{|}\psi(0)\big{\rangle}=\frac{1}{\sqrt{N}}\sum_{v\in V}|v\rangle,$

where $N$ is the number of vertices. The quantum state at time $t$ is
therefore given by

$\big{|}\psi(t)\big{\rangle}=\mathrm{e}^{-\mathrm{i}Ht}\big{|}\psi(0)\big{\rangle}.$

The probability of finding a marked vertex at time $t$ is

$p(t)=\sum_{w\in
W}\left|\big{\langle}w\big{|}\psi(t)\big{\rangle}\right|^{2}.$ (2)

Our goal is to find the optimal values of parameters $t$ and $\gamma$ so that
the success probability is as high as possible.

###  2.1 Eigenvalues and eigenvectors of the Hamiltonian

For an operator $U$, let $\sigma(U)$ denote the spectrum of $U$. Suppose that
the adjacency matrix $A$ of $G(V,E)$ has exactly $k+1$ distinct eigenvalues
$\phi_{0}>\phi_{1}>\dots>\phi_{k}$. For $0\leqslant\ell\leqslant k$, let
$P_{\ell}$ denote the orthogonal projector onto the eigenspace of $A$ in
$\mathcal{H}$ for the eigenvalue $\phi_{\ell}$, that is,

$A=\sum_{\ell=0}^{k}\phi_{\ell}P_{\ell}.$

Let $\lambda$ and $\big{|}\lambda\big{\rangle}$ be an eigenvalue and a
normalized eigenvector of $H$, respectively, that is

$H\big{|}\lambda\big{\rangle}=\lambda\big{|}\lambda\big{\rangle}$

and $\big{\langle}\lambda\big{|}\lambda\big{\rangle}=1$. Hamiltonian $H$ and
operator $-\gamma A$ may share common eigenvalues and eigenvectors, as shown
in the next Proposition.

######  Proposition 1.

Let $|\lambda\rangle$ be an eigenvector of $H$ associated with eigenvalue
$\lambda$. Then, $\lambda\in\sigma(-\gamma A)$ and $(-\gamma
A)\big{|}\lambda\big{\rangle}=\lambda\big{|}\lambda\big{\rangle}$ if and only
if $\big{\langle}w\big{|}\lambda\big{\rangle}=0$ for all $w\in W$.

###### Proof.

Using the definition of $H$, we obtain

$\sum_{w\in
W}\big{|}w\big{\rangle}\big{\langle}w\big{|}\lambda\big{\rangle}=-(\gamma
A+H)\big{|}\lambda\big{\rangle}.$

If $\lambda\in\sigma(-\gamma A)$ and $(-\gamma
A)\big{|}\lambda\big{\rangle}=\lambda\big{|}\lambda\big{\rangle}$, the right-
hand side is zero and the entries of the vector $\sum_{w\in
W}\big{|}w\big{\rangle}\big{\langle}w\big{|}\lambda\big{\rangle}$ must be
zero. Then, we have $\big{\langle}w\big{|}\lambda\big{\rangle}=0$ for all
$w\in W$. On the other hand, if $\big{\langle}w\big{|}\lambda\big{\rangle}=0$
for all $w\in W$, the left-hand side is zero. Since
$H\big{|}\lambda\big{\rangle}=\lambda\big{|}\lambda\big{\rangle}$, we have
$\lambda\in\sigma(-\gamma A)$ and $(-\gamma
A)\big{|}\lambda\big{\rangle}=\lambda\big{|}\lambda\big{\rangle}$. ∎

In Eq. (2), it is evident that eigenvectors $\big{|}\lambda\big{\rangle}$,
which satisfy $\big{\langle}w\big{|}\lambda\big{\rangle}=0$ for all $w\in W$,
do not contribute to the computation of the probability $p(t)$ for locating a
marked vertex. These eigenvectors correspond to eigenvalues $\lambda$ that are
part of the spectrum of $-\gamma A$. In the continuation, we are interested in
eigenvectors $\big{|}\lambda\big{\rangle}$ for which
$\big{\langle}w\big{|}\lambda\big{\rangle}\neq 0$, at least for one marked
vertex $w$. The eigenvectors $\big{|}\lambda\big{\rangle}$ fulfilling the
condition $\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}=0$ are also
irrelevant to the dynamics. To discern which eigenvectors of $H$ should be
disregarded, the following proposition is necessary.

######  Proposition 2.

Let $\lambda$ be a real number such that $\lambda\notin\sigma(-\gamma A)$.
Define the real symmetric matrix
$M^{\lambda}=\big{(}M_{ww^{\prime}}^{\lambda}\big{)}_{w,w^{\prime}\in W}$,
where

$M_{ww^{\prime}}^{\lambda}=\delta_{ww^{\prime}}+\sum_{\ell=0}^{k}\frac{\big{\langle}w\big{|}P_{\ell}\big{|}w^{\prime}\big{\rangle}}{\lambda+\gamma\phi_{\ell}}.$
(3)

Then, $\lambda$ is an eigenvalue of $H$ if and only if $\det(M^{\lambda})=0$.

###### Proof.

($\Rightarrow$) Assume that $\lambda$ is an eigenvalue of $H$ and
$\big{|}\lambda\big{\rangle}$ is the corresponding eigenvector. From the
definition of $H$, we have

$P_{\ell}H\big{|}\lambda\big{\rangle}=-P_{\ell}\left(\gamma A+\sum_{w\in
W}\big{|}w\big{\rangle}\big{\langle}w\big{|}\right)\big{|}\lambda\big{\rangle},$
(4)

and since $\lambda\notin\sigma(-\gamma A)$, we can rewrite the above equation
as

$P_{\ell}\big{|}\lambda\big{\rangle}=-\frac{1}{\lambda+\gamma\phi_{\ell}}\sum_{w\in
W}\big{\langle}w\big{|}\lambda\big{\rangle}P_{\ell}\big{|}w\big{\rangle}.$ (5)

Given that $\sum_{\ell=0}^{k}P_{\ell}=I$, for a fixed marked vertex $w$, we
obtain
$\big{\langle}w\big{|}\lambda\big{\rangle}=\sum_{\ell=0}^{k}\big{\langle}w\big{|}P_{\ell}\big{|}\lambda\big{\rangle}.$
Then, using Eq. (5), we derive

$\big{\langle}w\big{|}\lambda\big{\rangle}=-\sum_{\ell=0}^{k}\frac{1}{\lambda+\gamma\phi_{\ell}}\left(\sum_{w^{\prime}\in
W}\big{\langle}w^{\prime}\big{|}\lambda\big{\rangle}\big{\langle}w\big{|}P_{\ell}\big{|}w^{\prime}\big{\rangle}\right),$

which can be rewritten as

$\sum_{w^{\prime}\in
W}M_{ww^{\prime}}^{\lambda}\big{\langle}w^{\prime}\big{|}\lambda\big{\rangle}=0,$
(6)

where $\big{(}M_{ww^{\prime}}^{\lambda}\big{)}_{w,w^{\prime}\in W}$ is as
defined in Eq. (3). Since $\lambda\not\in\sigma(-\gamma A)$, the vector
$\big{\langle}w\big{|}\lambda\big{\rangle}\big{\rvert}_{w\in W}$ is nonzero by
Proposition 1, and hence it is a $0$-eigenvector of $M^{\lambda}$. It follows
that $\det\big{(}M^{\lambda}\big{)}=0.$

($\Leftarrow$) Assume $\lambda$ is a real number not in $\sigma(-\gamma A)$
such that $\det(M^{\lambda})=0$. $M^{\lambda}$ has a 0-eigenvector, denoted as
$u(w)\big{\rvert}_{w\in W}$. Construct $k+1$ vectors
$\big{|}\lambda_{\ell}\big{\rangle}$, inspired by Eq. (5), as follows:

$\big{|}\lambda_{\ell}\big{\rangle}=-\frac{1}{\lambda+\gamma\phi_{\ell}}\sum_{w\in
W}u(w)P_{\ell}\big{|}w\big{\rangle}.$

Note that
$P_{\ell}\big{|}\lambda_{\ell^{\prime}}\big{\rangle}=\delta_{\ell\ell^{\prime}}\big{|}\lambda_{\ell}\big{\rangle}$,
or equivalently,
$A\big{|}\lambda_{\ell}\big{\rangle}=\phi_{\ell}\big{|}\lambda_{\ell}\big{\rangle}$.
Our candidate for an eigenvector of $H$ associated with $\lambda$ is

$\big{|}\lambda\big{\rangle}=\sum_{\ell=0}^{k}\big{|}\lambda_{\ell}\big{\rangle}.$
(7)

First, we claim that $\big{|}\lambda\big{\rangle}$ is nonzero. Indeed, if
$\big{|}\lambda\big{\rangle}=0$, then we have
$0=P_{\ell}\big{|}\lambda\big{\rangle}=\big{|}\lambda_{\ell}\big{\rangle}$ for
all $\ell$, and hence

$0=-\sum_{\ell=0}^{k}(\lambda+\gamma\phi_{\ell})\big{|}\lambda_{\ell}\big{\rangle}=\sum_{\ell=0}^{k}\sum_{w\in
W}u(w)P_{\ell}\big{|}w\big{\rangle}=\sum_{w\in W}u(w)\big{|}w\big{\rangle}$

by $\sum_{\ell=0}^{k}P_{\ell}=I$, but this is impossible because
$u(w)\big{\rvert}_{w\in W}$ is nonzero. We next claim that
$H\big{|}\lambda\big{\rangle}=\lambda\big{|}\lambda\big{\rangle}$. Indeed,
using the definitions of $H$ and $\big{|}\lambda_{\ell}\big{\rangle}$, we have

$\displaystyle H\big{|}\lambda\big{\rangle}$
$\displaystyle=\sum_{\ell=0}^{k}\frac{\gamma\phi_{\ell}}{\lambda+\gamma\phi_{\ell}}\sum_{w\in
W}u(w)P_{\ell}\big{|}w\big{\rangle}+$ $\displaystyle\quad\sum_{w,w^{\prime}\in
W}\left(\sum_{\ell=0}^{k}\frac{\big{\langle}w\big{|}P_{\ell}\big{|}w^{\prime}\big{\rangle}}{\lambda+\gamma\phi_{\ell}}\right)u(w^{\prime})\big{|}w\big{\rangle}.$

The expression in parentheses becomes
$M_{ww^{\prime}}^{\lambda}-\delta_{ww^{\prime}}$ by Eq. (3). Since
$u(w)\big{\rvert}_{w\in W}$ is a $0$-eigenvector of $M^{\lambda}$, we find

$\displaystyle
H\big{|}\lambda\big{\rangle}=\sum_{\ell=0}^{k}\frac{\gamma\phi_{\ell}}{\lambda+\gamma\phi_{\ell}}\sum_{w\in
W}u(w)P_{\ell}\big{|}w\big{\rangle}-\sum_{w\in W}u(w)\big{|}w\big{\rangle}.$

Applying $\sum_{\ell=0}^{k}P_{\ell}$ on the second term of the right-hand
side, the equation simplifies to

$\displaystyle H\big{|}\lambda\big{\rangle}$
$\displaystyle=\lambda\left(-\sum_{\ell=0}^{k}\frac{1}{\lambda+\gamma\phi_{\ell}}\sum_{w\in
W}u(w)P_{\ell}\big{|}w\big{\rangle}\right),$

which concludes the proof, considering Eq. (7). ∎

Given a graph $G(V,E)$ with a set $W$ of marked vertices, the proof of
Proposition 2 outlines a method for determining the eigenvalues
$\lambda\notin\sigma(-\gamma A)$ of the Hamiltonian (1), assuming we know the
eigenvalues and eigenprojections of the adjacency matrix. This method involves
solving the equation $\det(M^{\lambda})=0$ for an unknown real number
$\lambda$. Note that the numerator of $\det(M^{\lambda})$ is a polynomial
$P(\lambda)$ of degree at most $(k+1)|W|$ in the indeterminate $\lambda$.
There can be at most $(k+1)|W|$ roots of $P(\lambda)=0$, some of which may lie
in $\sigma(-\gamma A)$. Additionally, since $A$ is a real symmetric matrix,
$M^{\lambda}$ is also real symmetric and thus orthogonally diagonalizable.

The proof of Proposition 2 also shows how to identify a basis for the
eigenspace associated with $\lambda$. The multiplicity of $\lambda$ is equal
to the multiplicity of the zero eigenvalue of $M^{\lambda}$. Given an
orthogonal basis of $0$-eigenvectors of $M^{\lambda}$, and applying Eq. (7),
we can derive an orthogonal basis for the $\lambda$-eigenspace of $H$.
Consequently, as a corollary, the multiplicity of $\lambda$ is constrained by
the upper bound of $|W|$.

Given that the initial state is $\big{|}\phi_{0}\big{\rangle}$, an eigenvector
$\big{|}\lambda\big{\rangle}$ such that
$\big{\langle}\lambda\big{|}\phi_{0}\big{\rangle}=0$ does not affect the
quantum walk dynamics. The criterion to ensure that
$\big{\langle}\lambda\big{|}\phi_{0}\big{\rangle}\neq 0$ when eigenvector
$\big{|}\lambda\big{\rangle}$ is obtained using Eq. (7) is

$\sum_{w\in W}u(w)\big{\langle}\phi_{0}\big{|}w\big{\rangle}\neq 0.$ (8)

In the case of a regular graph $G(V,E)$, it is necessary to assert that
$\sum_{w\in W}u(w)\neq 0$.

######  Proposition 3.

Let $\lambda^{-}$ be the smallest eigenvalue of $H$ and
$\big{|}\lambda^{-}\big{\rangle}$ be an associated eigenvector. Then,
$\lambda^{-}$ is simple,
$\big{\langle}\lambda^{-}\big{|}\phi_{0}\big{\rangle}\neq 0$, and
$\lambda^{-}<-\gamma\phi_{0}$ for any $\gamma>0$.

###### Proof.

Since $-H$ is irreducible and nonnegative, by the Perron–Frobenius theorem
(see, e.g., [36, 37, 38]), $\lambda^{-}$ is simple and the entries of
$\big{|}\lambda^{-}\big{\rangle}$ are all nonnegative or all nonpositive. In
particular, $\big{\langle}\lambda^{-}\big{|}\phi_{0}\big{\rangle}\neq 0$.
Moreover, since $\gamma A$ and $-H-\gamma A=\sum_{w\in
W}\big{|}w\big{\rangle}\big{\langle}w\big{|}$ are both nonnegative and the
latter is nonzero, we have $\lambda^{-}<-\gamma\phi_{0}$ for any $\gamma>0$. ∎

Let $\lambda^{+}$ denote the eigenvalue of $H$ that is the $(|W|+1)$-smallest,
considering the multiplicity of each eigenvalue. If $\lambda^{+}$ is in the
spectrum $\sigma(-\gamma A)$, or if the eigenvectors
$\big{|}\lambda^{+}\big{\rangle}$ corresponding to $\lambda^{+}$ satisfy
$\big{\langle}\lambda^{+}\big{|}\phi_{0}\big{\rangle}=0$ for $\gamma>0$,
meaning that $\big{|}\lambda^{+}\big{\rangle}$ is derived from a
$0$-eigenvector of $M^{\lambda}$ fulfilling condition (8), then we must select
the next smallest eigenvalue. We claim that there exists a specific value of
$\gamma$ for which the eigenvalue $-\gamma\phi_{0}$ of $-\gamma A$ is
positioned midway between $\lambda^{-}$ and $\lambda^{+}$. Our approach uses
$\lambda^{\pm}$ and this $\gamma$ in the asymptotic limit. Essentially, for
any graph $G(V,E)$ we claim the existence of a $\gamma$ value satisfying

$\lambda^{\pm}=-\gamma\phi_{0}\pm\epsilon,$

where $|\lambda^{-}+\gamma\phi_{0}|=|\lambda^{+}+\gamma\phi_{0}|=\epsilon$.

Before we present the proof of this claim, let us first offer some intuitive
insights into its validity. Considering $H$ as defined in Eq. (1), when
$\gamma=0$, the eigenvalues of $H$ are $-1$ (with multiplicity $|W|$) and $0$
(with multiplicity $N-|W|$), where $N$ is the dimension of the Hilbert space.
For small, nonzero $\gamma$, the eigenvalue of $-1$ splits into $|W|$
eigenvalues (which are not necessarily distinct) corresponding to different
eigenvectors. Note that, based on a dimensionality analysis, at least one of
these $|W|$ eigenvectors $\big{|}\lambda\big{\rangle}$ satisfies
$\big{\langle}\lambda\big{|}\phi_{0}\big{\rangle}\neq 0$, aligned with
$\big{\langle}\lambda^{-}\big{|}\phi_{0}\big{\rangle}\neq 0$. In the case when
$|W|\geq 2$, at least two eigenvalues will be different because $\lambda^{-}$,
the smallest eigenvalue, is simple. As previously described, $\lambda^{+}$
represents the $(|W|+1)$-th eigenvalue of $H$, considering the multiplicity of
each eigenvalue. Consequently, $\lambda^{+}$ is selected as the smallest
eigenvalue of $H$ that approaches 0 when $\gamma$ tends to 0. Due to the
stipulation in constraint (8) and the condition
$\lambda^{+}\notin\sigma(-\gamma A)$, there are instances where $\lambda^{+}$
needs to be the $j$-th eigenvalue, where $j$ exceeds $|W|+1$. It is essential
to avoid any eigenvalues that converge towards $-1$ as $\gamma$ decreases when
choosing $\lambda^{+}$ because, in such scenarios, the gap between
$\lambda^{-}$ and $\lambda^{+}$ becomes too small.

When $\gamma$ is small, the eigenvalue $-\gamma\phi_{0}$ of $-\gamma A$ is
near zero, placing it close to $\lambda^{+}$ on the real line spectrum.
Conversely, as $\gamma$ increases, $-\gamma\phi_{0}$ becomes increasingly
aligned with $\lambda^{-}$, indicating an one-to-one correlation between the
eigenvalues of $-\gamma A$ and $H$. We have established that for small
$\gamma$, the eigenvalue $-\gamma\phi_{0}$ is positioned near the right of the
range $[\lambda^{-},\lambda^{+}]$. As $\gamma$ increases, this eigenvalue
shifts leftward, eventually nearing the left end of this range. Given that the
determinants $|H-\lambda I|$ and $|-\gamma A-\phi I|$ are continuous real
functions of $\gamma$, by applying the intermediate value theorem, we deduce
that a specific $\gamma$ exists where $-\gamma\phi_{0}$ is exactly at the
midpoint of $[\lambda^{-},\lambda^{+}]$.

######  Proposition 4.

Let $\lambda^{-}$ be the smallest eigenvalues of $H$. Let $\lambda^{+}$ be an
eigenvalue of $H$ such that $\lambda^{+}>\lambda^{-}$. Then, there exists
$\gamma>0$ such that

$-\gamma\phi_{0}=\frac{\lambda^{-}+\lambda^{+}}{2},$

where $\phi_{0}$ is the largest eigenvalue of $A$.

###### Proof.

For convenience, set $\tau=\gamma/(1+\gamma)$. Note that $\tau\in(0,1)$. Also,
let $\mu^{\pm}(\tau)=\lambda^{\pm}(\gamma)/(1+\gamma)$, so that they are
eigenvalues of

$(1-\tau)H(\gamma)=-\tau A-(1-\tau)\sum_{w\in
W}\big{|}w\big{\rangle}\big{\langle}w\big{|}.$

Then, observe that the values $\mu^{\pm}(\tau)$ also make sense for
$\tau=0,1$. In particular,

$\mu^{-}(0)=-1,\qquad\mu^{+}(0)\leqslant
0,\qquad\mu^{-}(1)=-\phi_{0},\qquad\mu^{+}(1)=-\phi_{\ell}$

for some $\ell\geqslant 1$, where $\phi_{\ell}$ is the
$(\ell+1)^{\mathrm{st}}$ largest eigenvalue of $A$. We have used that
$\phi_{0}$ is a simple eigenvalue of $A$ because $G(V,E)$ is connected.
Moreover, note that $\mu^{\pm}(\tau)$ are continuous in $\tau$ using Weyl’s
Perturbation Theorem [39]. Now, consider the continuous function

$h(\tau)=\mu^{-}(\tau)+\mu^{+}(\tau)+2\phi_{0}\tau.$

We have $h(0)\leqslant-1<0$ and $h(1)=\phi_{0}-\phi_{\ell}>0$. Hence, by the
intermediate value theorem, there exists $\tau\in(0,1)$ such that $h(\tau)=0$.
The proof is complete after converting back to variable
$\gamma=\tau/(1-\tau)$. ∎

To illustrate an eigenvalue $\lambda$ to avoid because it is in
$\sigma(-\gamma A)$, consider the complete bipartite graph $K_{n,n}$ with $n$
marked vertices in one part. The eigenvalues of $H$ are ordered as
$\lambda^{-}<-1<0<\lambda^{+}$. The second smallest eigenvalue is $-1$ with a
multiplicity of $n-1$. The next eigenvalue, $0$, belongs to $\sigma(-\gamma
A)$, making $\lambda^{+}$ the $(n+2)$-th and final eigenvalue of $H$.

###  2.2 Asymptotic analysis

Let us consider a graph class characterized by some parameters that determine
the number of vertices $N$. Usually, the spectral gap of the Hamiltonian tends
to zero when the number of vertices $N$ increases. In this case, the analysis
of the search algorithm is simpler in the asymptotic regime.

In cases where one vertex is marked, several studies have employed a technique
to analyze quantum-walk-based search algorithms. This technique uses two key
eigenvectors of the evolution operator, ensuring significant overlap between
both the initial and marked states and the space spanned by these eigenvectors
[3, 4, 6]. In this work, we extend and generalize this technique to cases with
multiple marked vertices. The asymptotic computational complexity of the
search algorithm primarily depends on the eigenvalues $\lambda^{\pm}$, where
$\lambda^{-}$ is the smallest eigenvalue of $H$, and $\lambda^{+}$ is the
$(|W|+1)$-smallest, taking into account the multiplicity of each eigenvalue.
Besides, $\lambda^{+}$ must satisfy the conditions
$\lambda^{+}\notin\sigma(-\gamma A)$ and
$\big{\langle}\lambda^{+}\big{|}\phi_{0}\big{\rangle}\neq 0$ for $\gamma>0$.
The value of $\gamma$ is described in Proposition 4, which positions
$-\gamma\phi_{0}$ in the middle of the range $[\lambda^{-},\lambda^{+}]$.
Since calculating this optimal $\gamma$ might be too difficult, we describe an
alternative way to obtain $\gamma$, which asymptotically approaches the
optimal one. Thus, we can write

$\lambda^{\pm}=-\gamma\phi_{0}\pm\epsilon+o(\epsilon).$ (9)

In this case, the gap between $\lambda^{-}$ and $\lambda^{+}$ is
asymptotically $2\epsilon>0$. Note that $2\epsilon$ is larger than the
spectral gap of $H$ unless $|W|=1$. We will detail a method to calculate
$\gamma$ needed in Eq. (9) below.

Using Eq. (3), matrices $M^{\lambda^{\pm}}$ are given by

$M_{ww^{\prime}}^{\lambda^{\pm}}=\delta_{ww^{\prime}}+\sum_{\ell=0}^{k}\frac{\big{\langle}w\big{|}P_{\ell}\big{|}w^{\prime}\big{\rangle}}{\gamma(\phi_{\ell}-\phi_{0})\pm{\epsilon}+o(\epsilon)}.$

Up to second order in $\epsilon$ we obtain

$M_{ww^{\prime}}^{\lambda^{\pm}}=\pm\frac{\big{\langle}w\big{|}P_{0}\big{|}w^{\prime}\big{\rangle}}{\epsilon}+\delta_{ww^{\prime}}-\frac{S^{(1)}_{ww^{\prime}}}{\gamma}\mp\frac{\epsilon
S^{(2)}_{ww^{\prime}}}{\gamma^{2}}+O(\epsilon^{2}),$ (10)

where

$S^{(1)}_{ww^{\prime}}=\sum_{\ell=1}^{k}\frac{\big{\langle}w\big{|}P_{\ell}\big{|}w^{\prime}\big{\rangle}}{\phi_{0}-\phi_{\ell}}$

and

$S^{(2)}_{ww^{\prime}}=\sum_{\ell=1}^{k}\frac{\big{\langle}w\big{|}P_{\ell}\big{|}w^{\prime}\big{\rangle}}{(\phi_{0}-\phi_{\ell})^{2}}.$

Note that the sums $S^{(1)}_{ww^{\prime}}$ and $S^{(1)}_{ww^{\prime}}$, as
well as $\big{\langle}w\big{|}P_{0}\big{|}w^{\prime}\big{\rangle}$, can be
calculated if we know the eigenvalues and eigenprojections of $A$. The unknown
quantities in Eq. (10) are $\gamma$ and $\epsilon$.

One of the goals of the asymptotic analysis is to determine analytical values
of $\gamma$ and $\epsilon$. By using Eq. (10), the condition
$\det(M^{\lambda^{\pm}})=0$, and considering the numerator up to the order of
$\epsilon^{2}$, we derive a quadratic equation in the form
$\epsilon^{2}+a(\gamma)\epsilon-b(\gamma)=O(\epsilon^{3})$. This equation
cannot contain the linear term, as this is the only way to achieve the
$\pm\epsilon$ term in Eq. (9). Consequently, we use the equation $a(\gamma)=0$
to ascertain the value of $\gamma$, which is asymptotically optimal. Once
$\gamma$ is computed, $\epsilon$ can be determined as $\sqrt{b(\gamma)}$.

Proposition 4 ensures that Eq. (9) is applicable to any graph $G(V,E)$.
Furthermore, this asymptotic analysis is valid for any graph such that
$\epsilon\ll 1$ or for any graph class where the gap between $\lambda^{-}$ and
$\lambda^{+}$ approaches 0 as $N$ tends toward infinity. An example where the
gap between $\lambda^{-}$ and $\lambda^{+}$ does not approach zero is the
class of complete bipartite graphs $K_{n,n}$ with $n$ marked vertices in one
part. In this case, using that $\phi_{0}=n$, the optimal parameters are
$\lambda^{\pm}=(-1\pm\sqrt{2})/2$ and $\gamma=1/2n$. This yields a fixed
$\epsilon=1/\sqrt{2}$. Note that the behavior of the gap depends on the
placement of the marked vertices. In the same graph $K_{n,n}$, if the marked
vertices are arranged in a different configuration than the one above, the gap
approaches zero.

###  2.3 Calculation of the computational complexity

Using an orthonormal basis ${\big{|}\lambda\big{\rangle}}$ of eigenvectors of
$H$, we can express the probability of finding a marked vertex as a function
of time $t$ (refer to Eq. (2)) as follows:

$p_{\text{exact}}(t)=\sum_{w\in
W}\Big{|}\sum_{\lambda}\mathrm{e}^{-\mathrm{i}\lambda
t}\big{\langle}w\big{|}\lambda\big{\rangle}\big{\langle}\lambda\big{|}\psi(0)\big{\rangle}\Big{|}^{2}.$

The exact eigenvalues $\lambda$ correspond to the roots of
$\det(M^{\lambda})=0$. However, calculating these roots and the exact
expression for $p_{\text{exact}}(t)$ often proves too complex. In the
asymptotic regime, where $N\rightarrow\infty$ and $\epsilon\rightarrow 0$, it
is preferable to use Eq. (10) as long as the computational complexity is
determined by $\lambda^{\pm}$. Matrices $M^{\lambda^{\pm}}$ are simpler to
compute as their entries depend only on two sums and the term
$\big{\langle}w\big{|}P_{0}\big{|}w^{\prime}\big{\rangle}$. To calculate an
approximate $p_{\text{approx}}(t)$ in this regime, we focus on the dominant
terms:

$p_{\text{approx}}(t)=\sum_{w\in W}\left|\mathrm{e}^{\mathrm{i}\epsilon
t}\big{\langle}w\big{|}\lambda^{-}\big{\rangle}\big{\langle}\lambda^{-}\big{|}\psi(0)\big{\rangle}+\mathrm{e}^{-\mathrm{i}\epsilon
t}\big{\langle}w\big{|}\lambda^{+}\big{\rangle}\big{\langle}\lambda^{+}\big{|}\psi(0)\big{\rangle}\right|^{2}.$
(11)

$\big{|}\lambda^{-}\big{\rangle}$ is a normalized eigenvector of $H$
associated with the smallest root $\lambda^{-}$ of $\det(M^{\lambda})=0$ and
$\big{|}\lambda^{+}\big{\rangle}$ with the $(|W|+1)$-smallest root
$\lambda^{+}$, subjected to the restrictions $\lambda^{+}\notin\sigma(-\gamma
A)$ and $\big{\langle}\lambda^{+}\big{|}\phi_{0}\big{\rangle}\neq 0$.
Eigenvalue $\lambda^{-}$ is always simple but if eigenvalue $\lambda^{+}$ is
not simple, which is uncommon, we must replace
$\big{|}\lambda^{+}\big{\rangle}\big{\langle}\lambda^{+}\big{|}$ with the
eigenprojection
$P^{+}=\sum\big{|}\lambda^{+}\big{\rangle}\big{\langle}\lambda^{+}\big{|}$ in
equation (11), where the sum runs over an orthonormal basis of the
$\lambda^{+}$-eigenspace. The multiplicity of $\lambda^{+}$ is at most $|W|$.

Note that $p_{\text{exact}}(t)\geq p_{\text{approx}}(t)$. The terms of
$p_{\text{approx}}(t)$ are calculated as follows. The value of $\gamma$ is
derived from the equation $a(\gamma)=0$ and $\epsilon$ from
$\sqrt{b(\gamma)}$, as described in Sec. 2.2. Now, let us turn our attention
to calculating $\big{|}\big{\langle}w\big{|}\lambda^{+}\big{\rangle}\big{|}$.
The approach for calculating
$\big{|}\big{\langle}w\big{|}\lambda^{-}\big{\rangle}\big{|}$ follows a
similar pattern. Remember that
$\big{\langle}w\big{|}\lambda^{+}\big{\rangle}\bigr{\rvert}_{w\in W}$ is a
$0$-eigenvector of $M^{\lambda^{+}}$, with entries
$\big{\langle}w\big{|}\lambda^{+}\big{\rangle}$ for each $w\in W$. Given that
$M^{\lambda^{+}}$ is already determined, we can identify a normalized
$0$-eigenvector of $M^{\lambda^{+}}$, which has entries denoted as $u(w)$ for
each $w\in W$. In cases where $\lambda^{+}$ is not a simple eigenvalue, it
becomes necessary to establish an orthonormal basis for the kernel of
$M^{\lambda^{+}}$. Following this,

$\big{\langle}w\big{|}\lambda^{+}\big{\rangle}={c^{+}}\,u(w),$ (12)

where ${c^{+}}$ is a complex number. Using
$\sum_{\ell}\left\|P_{\ell}\big{|}\lambda^{+}\big{\rangle}\right\|^{2}=1$ and
Eq. (5), we obtain

$\frac{1}{\left|{c^{+}}\right|^{2}}=\sum_{\ell=0}^{k}\frac{1}{\left|\lambda^{+}+\gamma\phi_{\ell}\right|^{2}}\,\Big{\|}\sum_{w\in
W}u(w)P_{\ell}\big{|}w\big{\rangle}\Big{\|}^{2}.$

The dominant term is

$\frac{1}{\left|{c^{+}}\right|}=\frac{1}{\epsilon}\,\Big{\|}\sum_{w\in
W}u(w)P_{0}\big{|}w\big{\rangle}\Big{\|}+O(1).$

To calculate $\big{\langle}w\big{|}\lambda^{+}\big{\rangle}$ instead of its
absolute value, we still have to find ${c^{+}}$ instead of
$\left|{c^{+}}\right|$. This is easily solved by rescaling
$\big{|}\lambda^{+}\big{\rangle}$ with a unit complex number
$\big{|}\lambda^{+}\big{\rangle}\rightarrow\mathrm{e}^{\mathrm{i}\theta}\big{|}\lambda^{+}\big{\rangle}$
so that ${c^{+}}\mathrm{e}^{-\mathrm{i}\theta}$ is a positive real number.
After rescaling $\big{|}\lambda^{+}\big{\rangle}$, we have
$\big{\langle}w\big{|}\lambda^{+}\big{\rangle}=|c^{+}|\,u(w)$.

The last terms of $p_{\text{approx}}(t)$ we need to determine are
$\big{|}\big{\langle}\lambda^{\pm}\big{|}\psi(0)\big{\rangle}\big{|}$. We
define $\big{|}\psi(0)\big{\rangle}$ as a normalized eigenvector of $-\gamma
A$ corresponding to the eigenvalue $-\gamma\phi_{0}$. In the special case
where the graph $G(V,E)$ is regular, $\big{|}\psi(0)\big{\rangle}$ is the
uniform superposition and thus becomes an eigenvector with the eigenvalue
$-\gamma d$, where $d$ is the degree of the graph. Setting $\ell=0$ and
applying Eq (5), we derive

$\big{\langle}\psi(0)\big{|}\lambda^{\pm}\big{\rangle}=\mp\frac{1}{\epsilon}\sum_{w\in
W}\big{\langle}\psi(0)\big{|}w\big{\rangle}\big{\langle}w\big{|}\lambda^{\pm}\big{\rangle}.$
(13)

Given that all terms on the right-hand side are assumed to be known, we now
have a method to calculate
$\big{\langle}\lambda^{\pm}\big{|}\psi(0)\big{\rangle}$.

Note that we have calculated all terms of $p_{\text{approx}}(t)$ as given by
Eq. (11). These terms are obtained from Eqs. (12) and (13), while $\epsilon$
and $\gamma$ are calculated using the method described in Sec. 2.2. The
framework described here avoids the need to calculate full expressions for the
eigenvectors $\big{|}\lambda^{\pm}\big{\rangle}$. To determine the
computational complexity of the search algorithm, we still need to identify
the optimal running time, which is the value of $t_{\text{opt}}$ that
corresponds to the first peak of $p_{\text{approx}}(t)$, and the corresponding
success probability, which is $p_{\text{approx}}(t_{\text{opt}})$.

The effectiveness of this framework hinges on the substantial overlap of both
the initial state and the marked states with the space spanned by
$\big{|}\lambda^{\pm}\big{\rangle}$. To analyze this, we can set a small upper
bound for the terms not included in Eq. (11) concerning the initial condition.
These missing terms are upper-bounded by

$\displaystyle\sum_{\lambda\neq\lambda^{\pm}}\big{|}\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}\big{|}^{2}\leqslant\frac{1}{\left(\lambda^{\circ}+\gamma\phi_{0}\right)^{2}}\sum_{\lambda\neq\lambda^{\pm}}\left(\lambda+\gamma\phi_{0}\right)^{2}\big{|}\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}\big{|}^{2},$

where $\lambda^{\circ}$ represents the eigenvalue of $H$ immediately following
$\lambda^{-}$. Using Eq. (5) and taking $\ell=0$, we find
$\left(\lambda+\gamma\phi_{0}\right)\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}=-\sum_{w}\big{\langle}\psi(0)\big{|}w\big{\rangle}\big{\langle}w\big{|}\lambda\big{\rangle}$.
This leads to the upper bound

$\displaystyle\sum_{\lambda\neq\lambda^{\pm}}\big{|}\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}\big{|}^{2}\leqslant\frac{|W|+2}{\left(\lambda^{\circ}+\gamma\phi_{0}\right)^{2}}\sum_{w,w^{\prime}\in
W}\big{\langle}w\big{|}P_{0}\big{|}w^{\prime}\big{\rangle}.$

Typically, the right-hand side tends to decrease. For example, in regular
graphs, the summation on the right-hand side simplifies to $|W|^{2}/N$. If the
gap between the eigenvalue $\lambda^{\circ}$ and $-\gamma\phi_{0}$ is
sufficiently large, such that it diminishes more slowly than $1/\sqrt{N}$,
then the overlap $|\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}|^{2}$ for
the excluded eigenvectors in Eq. (11) approaches zero. If the error approaches
zero asymptotically, we can state that
$p_{\text{exact}}(t)=p_{\text{approx}}(t)+o(1)$ and the framework described in
this work is successful.

There is an interesting case where the success probability
$p_{\text{approx}}(t)$ is the square of a sinusoidal function. This occurs
when the two terms within the summation of Eq. (11) fulfill the following
condition

$\big{\langle}\lambda^{+}\big{|}\psi(0)\big{\rangle}\big{\langle}w\big{|}\lambda^{+}\big{\rangle}=-\big{\langle}\lambda^{-}\big{|}\psi(0)\big{\rangle}\big{\langle}w\big{|}\lambda^{-}\big{\rangle}+o(1)$
(14)

for every $w\in W$. Indeed, by applying Eqs. (11) and (14), we obtain

$p_{\text{approx}}(t)=4\left|\big{\langle}\lambda^{-}\big{|}\psi(0)\big{\rangle}\right|^{2}\sum_{w\in
W}\left|\big{\langle}w\big{|}\lambda^{-}\big{\rangle}\right|^{2}\sin^{2}{\epsilon
t}+o(1)+o(\epsilon t).$ (15)

From this, we can determine the optimal running time as

$t_{\mathrm{run}}=\frac{\pi}{2\epsilon},$ (16)

which shows that the gap between $\lambda^{\pm}$ determines the optimal
running time. A larger gap means a smaller runtime. This expression leads to
the success probability being

$p_{\mathrm{succ}}=4\left|\big{\langle}\lambda^{-}\big{|}\psi(0)\big{\rangle}\right|^{2}\sum_{w\in
W}\left|\big{\langle}w\big{|}\lambda^{-}\big{\rangle}\right|^{2}+o(1).$ (17)

In the next section, we confirm that condition (14) applies to a quantum walk
on the Johnson graph with two marked vertices. This condition is also observed
in cases with one marked vertex [3, 35] and multiple marked vertices [40, 41].
The results of those papers in terms of computational complexity can be fully
reproduced using the asymptotic results of this subsection, in particular
expressions (16) and (17).

##  3 Johnson graphs

For the remainder of this paper, we will apply the general formula outlined in
the previous section to the Johnson graph $G(V,E)=J(n,k)$, with two distinct
marked vertices. The computation can be expanded to accommodate more than two
marked vertices; however, the complexity of the calculations rapidly
escalates. The vertex set $V$ is the set of $k$-subsets of
$[n]=\\{1,2,\dots,n\\}$, and two vertices $v,v^{\prime}\in V$ are adjacent if
and only if $|v\cap v^{\prime}|=k-1$. Note that $J(n,1)$ is the complete graph
$K_{n}$, and that $J(n,2)$ is the triangular graph $T_{n}$, which is strongly
regular. We will assume that $W=\\{w_{1},w_{2}\\}$, where we fix $k$ and let
$n\rightarrow\infty$. In this case, the matrix $M^{\lambda}$ from Eq. (3) is a
two-dimensional matrix denoted by

$M^{\lambda}=\begin{bmatrix}m_{1}&m_{3}\\\ m_{3}&m_{2}\\\ \end{bmatrix},$

where

$\displaystyle m_{1}$
$\displaystyle=\sum_{\ell=0}^{k}\frac{\left\|P_{\ell}\big{|}w_{1}\big{\rangle}\right\|^{2}}{\lambda+\gamma\phi_{\ell}}+1,$
$\displaystyle m_{2}$
$\displaystyle=\sum_{\ell=0}^{k}\frac{\left\|P_{\ell}\big{|}w_{2}\big{\rangle}\right\|^{2}}{\lambda+\gamma\phi_{\ell}}+1,$
$\displaystyle m_{3}$
$\displaystyle=\sum_{\ell=0}^{k}\frac{\big{\langle}w_{1}\big{|}P_{\ell}\big{|}w_{2}\big{\rangle}}{\lambda+\gamma\phi_{\ell}}.$

The eigenvalues $\lambda$ of $H$ are obtained from
$\det(M^{\lambda})=m_{1}m_{2}-m_{3}^{2}=0$.

The number of vertices of $J(n,k)$ is $N=\binom{n}{k}$. The $k+1$ distinct
eigenvalues $\phi_{0}>\phi_{1}>\dots>\phi_{k}$ of $J(n,k)$ are given by

$\phi_{\ell}=(k-\ell)(n-k-\ell)-\ell,$ (18)

and the multiplicity of $\phi_{\ell}$ is $\binom{n}{\ell}-\binom{n}{\ell-1}$
(with the convention that $\binom{n}{-1}=0$). See [42, 36, 43]. For the
Johnson graph $J(n,k)$, it important to remark that $P_{\ell}$ has constant
diagonal entries
$\big{(}\binom{n}{\ell}-\binom{n}{\ell-1}\big{)}/\binom{n}{k}$, so that

$\left\|P_{\ell}\big{|}w_{1}\big{\rangle}\right\|^{2}=\left\|P_{\ell}\big{|}w_{2}\big{\rangle}\right\|^{2}=\frac{\binom{n}{\ell}-\binom{n}{\ell-1}}{\binom{n}{k}}=\frac{k!(n-k)!(n-2\ell+1)}{\ell!(n-\ell+1)!}.$
(19)

In particular, we have $m_{1}=m_{2}$. Let

$\delta=k-|w_{1}\cap w_{2}|,$

which is the distance between $w_{1}$ and $w_{2}$. We note that $m_{3}$
depends on $\delta$. More specifically, it is known that
$\big{\langle}w_{1}\big{|}P_{\ell}\big{|}w_{2}\big{\rangle}$ is written in
terms of a terminating ${}_{3}F_{2}$ hypergeometric series:

$\big{\langle}w_{1}\big{|}P_{\ell}\big{|}w_{2}\big{\rangle}=\left\|P_{\ell}\big{|}w_{1}\big{\rangle}\right\|^{2}{}_{3}F_{2}\\!\left(\left.\\!\\!\\!\begin{array}[]{c}-\ell,-\delta,\ell-n-1\\\
k-n,-k\end{array}\\!\\!\right|1\right).$ (20)

See, e.g., [42, pp. 219–220] and [44, Example 2.3]. From now on, _we assume
that $\delta$ is known in advance._ After analyzing the search algorithm under
this assumption, we will discuss the unrestricted case, in which $\delta$ is
unknown.

###  3.1 An invariant subspace

For the single-marked case discussed in [35], a $(k+1)$-dimensional invariant
subspace of $\mathcal{H}$ played an important role. For the present case, we
can again make use of a similar but more complicated invariant subspace. For
integers $a,b,c$ such that $0\leqslant a\leqslant k-\delta$, $a\leqslant
b\leqslant c$, and $2k-n+\delta+a-b\leqslant
c\leqslant\min\\{k+a-b,\delta+a\\}$, let

$\nu_{a,b,c}=\big{\\{}v\in V:|v\cap w_{1}\cap w_{2}|=a,\,\\{|v\cap
w_{1}|,|v\cap w_{2}|\\}=\\{b,c\\}\big{\\}},$

and set

$\big{|}\nu_{a,b,c}\big{\rangle}=\sum_{v\in\nu_{a,b,c}}\big{|}v\big{\rangle}.$

Let $\mathcal{H}_{\mathrm{inv}}$ denote the subspace of $\mathcal{H}$ spanned
by these (unnormalized) vectors $\big{|}\nu_{a,b,c}\big{\rangle}$. Then, it
follows that $\mathcal{H}_{\mathrm{inv}}$ is invariant under $A$. This can be
shown manually, but the group-theoretic explanation is as follows. When
$n>2k$, the automorphism group of $J(n,k)$ is isomorphic to the symmetric
group $\mathfrak{S}_{n}$ on $n$ letters $[n]=\\{1,2,\dots,n\\}$. Consider the
subgroup $\mathfrak{G}$ of $\mathfrak{S}_{n}$ consisting of the elements that
fix $W$ setwise. The elements of $\mathfrak{G}$ fix each of the sets
$w_{1}\cap w_{2}$ and $[n]\setminus(w_{1}\cup w_{2})$, and either fix or swap
the two sets $w_{1}\setminus w_{2}$ and $w_{2}\setminus w_{1}$. Hence, the
order of $\mathfrak{G}$ is
$|\mathfrak{G}|=(k-\delta)!\times(n-k-\delta)!\times(\delta!)^{2}\times 2$.
The $\nu_{a,b,c}$ are precisely the orbits of $\mathfrak{G}$ on the vertex set
$V$. In particular, this implies that a vector $\mathbf{v}\in\mathcal{H}$ is
$\mathfrak{G}$-invariant (i.e., $g\mathbf{v}=\mathbf{v}$ for all
$g\in\mathfrak{G}$) if and only if $\mathbf{v}$ is a linear combination of the
vectors $\big{|}\nu_{a,b,c}\big{\rangle}$, or equivalently,
$\mathbf{v}\in\mathcal{H}_{\mathrm{inv}}$. For every
$\mathbf{v}\in\mathcal{H}_{\mathrm{inv}}$, since $g\mathbf{v}=\mathbf{v}$ and
$Ag=gA$ for all $g\in\mathfrak{G}$, we have

$g(A\mathbf{v})=A(g\mathbf{v})=A\mathbf{v}\qquad(g\in\mathfrak{G}),$

so that $A\mathbf{v}$ is $\mathfrak{G}$-invariant and thus belongs to
$\mathcal{H}_{\mathrm{inv}}$. We have now shown that
$\mathcal{H}_{\mathrm{inv}}$ is invariant under $A$. Moreover, since
$W=\nu_{k-\delta,k-\delta,k}$, we have

$\left(\sum_{w\in
W}\big{|}w\big{\rangle}\big{\langle}w\big{|}\right)\\!\big{|}\nu_{a,b,c}\big{\rangle}=\delta_{k-\delta,a}\delta_{k-\delta,b}\delta_{k,c}\big{|}\nu_{k-\delta,k-\delta,k}\big{\rangle}.$

Hence, it follows that $\mathcal{H}_{\mathrm{inv}}$ is invariant under $H$ and
thus also $\mathrm{e}^{-\mathrm{i}Ht}$. Note also that, since the sets
$\nu_{a,b,c}$ partition $V$, the sum of the vectors
$\big{|}\nu_{a,b,c}\big{\rangle}$ equals
$\sqrt{N}\big{|}\psi(0)\big{\rangle}$, so that $\big{|}\psi(0)\big{\rangle}$
belongs to $\mathcal{H}_{\mathrm{inv}}$.

From now on, _we will always consider eigenvectors
$\big{|}\lambda\big{\rangle}$ in $\mathcal{H}_{\mathrm{inv}}$._ This
assumption provides us with the following strong constraint:

$\big{\langle}w_{1}\big{|}\lambda\big{\rangle}=\big{\langle}w_{2}\big{|}\lambda\big{\rangle}=\frac{\big{\langle}\nu_{k-\delta,k-\delta,k}\big{|}\lambda\big{\rangle}}{2}.$

For the rest of this section, let us call this common value $\alpha$. The
following is a strengthening of Proposition 1 in this case.

######  Proposition 5.

The following are equivalent: (i) $\lambda\in\sigma(-\gamma A)$; (ii) $-\gamma
A\big{|}\lambda\big{\rangle}=\lambda\big{|}\lambda\big{\rangle}$; (iii)
$\alpha=0$.

###### Proof.

(iii)$\Rightarrow$(ii): Note that $-\gamma
A\big{|}\lambda\big{\rangle}=H\big{|}\lambda\big{\rangle}=\lambda\big{|}\lambda\big{\rangle}$
by the definition of $H$.

(ii)$\Rightarrow$(i): Clear.

(i)$\Rightarrow$(iii): Suppose that $\lambda=-\gamma\phi_{\ell}$. Then, by Eq.
(4), we have

$\alpha\left(P_{\ell}\big{|}w_{1}\big{\rangle}+P_{\ell}\big{|}w_{2}\big{\rangle}\right)=0,$

where we note that $P_{\ell}A=AP_{\ell}=\phi_{\ell}P_{\ell}$. If $\ell=0$ then
$P_{0}\big{|}w_{1}\big{\rangle}=P_{0}\big{|}w_{2}\big{\rangle}=(1/\sqrt{N})\big{|}\psi(0)\big{\rangle}$,
so $\alpha=0$. If $\ell>0$ then it follows from the fact that $J(n,k)$ is a
primitive111A distance-regular graph with diameter $k$ is called _primitive_
if all the distance-$i$ graphs $(i=1,2,\dots,k)$ are connected. distance-
regular graph (provided $n>2k$) that $P_{\ell}\big{|}w_{1}\big{\rangle}$ and
$P_{\ell}\big{|}w_{2}\big{\rangle}$ are linearly independent (cf. [36, Sec.
9.1], [42, p. 137]), so again we have $\alpha=0$, whence (iii). ∎

######  Corollary 6.

$-\gamma\phi_{0}$ is not an eigenvalue of $H$ on $\mathcal{H}_{\mathrm{inv}}$.

###### Proof.

If $\lambda=-\gamma\phi_{0}$ then $\big{|}\psi(0)\big{\rangle}$ and
$\big{|}\lambda\big{\rangle}$ are linearly independent eigenvectors of $A$
with eigenvalue $\phi_{0}$. (The linear independence follows from
$\big{\langle}w_{1}\big{|}\psi(0)\big{\rangle}=\big{\langle}w_{2}\big{|}\psi(0)\big{\rangle}=1/\sqrt{N}\neq
0$ and $\alpha=0$.) But $\phi_{0}$ has multiplicity one since $J(n,k)$ is
connected, a contradiction. ∎

######  Corollary 7.

Suppose that $\lambda\not\in\sigma(-\gamma A)$. Then,
$m_{1}+m_{3}=m_{2}+m_{3}=0$.

###### Proof.

Immediate from Eq. (6) and
$\big{\langle}w_{1}\big{|}\lambda\big{\rangle}=\big{\langle}w_{2}\big{|}\lambda\big{\rangle}=\alpha\neq
0$. ∎

This corollary simplifies the discussions regarding the calculations of
$\lambda^{\pm}$, as it allows us to disregard the scenario where
$m_{1}-m_{3}=0$, which leads to a “bad” eigenvalue (we will revisit this point
later). Additionally, note that the findings of this subsection are extendable
to other families of distance-transitive graphs, such as Hamming graphs.

###  3.2 Calculation of $\lambda^{\pm}$ and related quantities

First, we find the eigenvalue $\lambda^{-}$ of the ground state of $H$. Note
that the adjacency matrix $A$ and the oracle $\sum_{w\in
W}\big{|}w\big{\rangle}\big{\langle}w\big{|}$ are both nonnegative matrices
with respect to the computational basis, and hence so are their matrix
representations with respect to the $\big{|}\nu_{a,b,c}\big{\rangle}$ on
$\mathcal{H}_{\mathrm{inv}}$. Since $\gamma>0$, it follows from the
Perron–Frobenius theorem (see, e.g., [36, 37, 38]) that the eigenvalue
$\lambda^{-}$ is in the interval $(-\infty,-\gamma\phi_{0})$ and has
multiplicity one; see also Proposition 3. Moreover, observe that
$m_{1}+m_{3}$, as a function of $\lambda$, is monotone decreasing on
$(-\infty,-\gamma\phi_{0})$ since
$\left|\big{\langle}w_{1}\big{|}P_{\ell}\big{|}w_{2}\big{\rangle}\right|\leqslant\left\|P_{\ell}\big{|}w_{1}\big{\rangle}\right\|^{2}=\left\|P_{\ell}\big{|}w_{2}\big{\rangle}\right\|^{2}$
by the Cauchy–Schwarz inequality and Eq. (19). Hence, it follows from
Corollary 7 that $\lambda^{-}$ is the _unique_ eigenvalue of $H$ on
$\mathcal{H}_{\mathrm{inv}}$ in $(-\infty,-\gamma\phi_{0})$.

We write

$\displaystyle S_{1}=S_{w_{1}w_{1}}^{(1)}=S_{w_{2}w_{2}}^{(1)},\qquad
S_{1}^{\prime}=S_{w_{1}w_{2}}^{(1)}=S_{w_{2}w_{1}}^{(1)},$ $\displaystyle
S_{2}=S_{w_{1}w_{1}}^{(2)}=S_{w_{2}w_{2}}^{(2)},\qquad
S_{2}^{\prime}=S_{w_{1}w_{2}}^{(2)}=S_{w_{2}w_{1}}^{(2)},$

and

$\lambda=-\gamma\phi_{0}+\epsilon.$

Using the equations of subsection 2.2, $m_{1}+m_{3}$ is given by

$m_{1}+m_{3}=\frac{2}{N\epsilon}+1-\frac{S_{1}+S_{1}^{\prime}}{\gamma}-\frac{S_{2}+S_{2}^{\prime}}{\gamma^{2}}\,\epsilon+O\\!\left(\epsilon^{2}\right).$
(21)

We choose $\gamma$ so that $\epsilon(m_{1}+m_{3})$ has no linear term in
$\epsilon$, i.e.,

$\gamma=S_{1}+S^{\prime}_{1}.$ (22)

We note that $S^{\prime}_{1}$ depends on the distance $\delta$, which we
currently assume is known in advance.

To proceed with the calculations, we need the following expressions for the
sums $S_{1},S_{2},S^{\prime}_{1}$, and $S^{\prime}_{2}$:

$\displaystyle S_{1}=\frac{1}{kn}+O\\!\left(\frac{1}{n^{2}}\right),\qquad
S_{2}=\frac{1}{k^{2}n^{2}}+O\\!\left(\frac{1}{n^{3}}\right),$ (23)
$\displaystyle S^{\prime}_{1}=O\\!\left(\frac{1}{n^{\delta+1}}\right),\qquad
S^{\prime}_{2}=O\\!\left(\frac{1}{n^{\delta+2}}\right).$ (24)

Eq. (23) follows easily from Eqs. (18) and (19). Indeed, for
$0\leqslant\ell\leqslant k$, we have

$\phi_{0}-\phi_{\ell}=\ell(n-\ell+1)=\ell n+O(1),$ (25)

and

$\|P_{\ell}\big{|}w_{1}\big{\rangle}\|^{2}=\frac{k!(n-2\ell+1)}{\ell!(n-\ell+1)\cdots(n-k+1)}=\frac{k!}{\ell!n^{k-\ell}}+O\\!\left(\frac{1}{n^{k-\ell+1}}\right).$

The proof of Eq. (24) is deferred to Appendix A. From Eqs. (23) and (24) it
follows that

$\gamma=\frac{1}{kn}+O\\!\left(\frac{1}{n^{2}}\right).$ (26)

For convenience, set

$\eta=\frac{1}{n}.$

By Eq. (19) again, we have

$\left\|P_{\ell}\big{|}w_{1}\big{\rangle}\right\|^{2}=\frac{k!\eta^{k-\ell}(1-(2\ell-1)\eta)}{\ell!(1-(\ell-1)\eta)\cdots(1-(k-1)\eta)}\qquad(0\leqslant\ell\leqslant
k),$

which is analytic around $\eta=0$. Moreover, it follows from Eq. (20) that
$\big{\langle}w_{1}\big{|}P_{\ell}\big{|}w_{2}\big{\rangle}$ is also analytic
around $\eta=0$. By Eqs. (25) and (26), we have

$\gamma(\phi_{0}-\phi_{\ell})=\frac{\ell}{k}+O(\eta)\qquad(1\leqslant\ell\leqslant
k),$ (27)

and this is also analytic around $\eta=0$. Since the constant term of the
right-hand side is nonzero, it follows from the above comments that
$\epsilon(m_{1}+m_{3})$, as a bivariate function of $\eta$ and
$\epsilon=\lambda+\gamma\phi_{0}$, is analytic around the origin
$(\eta,\epsilon)=(0,0)$. Hence, the power series expansion of
$\epsilon(m_{1}+m_{3})$ centered at the origin converges absolutely and
uniformly on some neighborhood of the origin (see [45, Sec. 2.3]), and
expressed in the form

$\epsilon(m_{1}+m_{3})=\frac{2}{N}-\frac{S_{2}+S^{\prime}_{2}}{{\gamma}^{2}}\,{\epsilon}^{2}+O(\epsilon^{3})$

with respect to $\epsilon$, where we recall that the linear term in $\epsilon$
vanishes, and that

$\frac{2}{N}=2k!\eta^{k}+O(\eta^{k+1}),\qquad\frac{S_{2}+S^{\prime}_{2}}{{\gamma}^{2}}=1+o(1)$
(28)

by Eqs. (23), (24), and (26). We note that the expression $O(\epsilon^{3})$ in
the above expansion is evaluated uniformly in $\eta$ on this neighborhood.
Now, set

$\epsilon^{-}_{0}=-\frac{\sqrt{2}\,\gamma}{\sqrt{N(S_{2}+S^{\prime}_{2})}}=-\frac{\sqrt{2}}{\sqrt{N}}(1+o(1)).$

Pick any scalar $\nu\in(1,2)$, and let $c\in(0,1)$ be such that
$O(\epsilon^{3})$ above is bounded as

$|O(\epsilon^{3})|<|\epsilon|^{1+\nu}2^{-\nu}$

for every $\epsilon\in(-c,c)$. This is possible since
$O(\epsilon^{3})=o(\epsilon^{1+\nu})$ when $1+\nu<3$. Remember that this
evaluation is uniform in $\eta$. Let $n$ be large enough so that
$|\epsilon^{-}_{0}|<c/2$ and $(S_{2}+S^{\prime}_{2})/\gamma^{2}>2/3$; see Eq.
(28). Then $\epsilon^{-}_{0}\pm|\epsilon^{-}_{0}|^{\nu}\in(-c,c)$ and we have

$\displaystyle\big{|}O\big{(}(\epsilon^{-}_{0}\pm|\epsilon^{-}_{0}|^{\nu})^{3}\big{)}\big{|}$
$\displaystyle<\big{|}\epsilon^{-}_{0}\pm|\epsilon^{-}_{0}|^{\nu}\big{|}^{1+\nu}2^{-\nu}$
$\displaystyle<|\epsilon^{-}_{0}|^{\nu}\big{|}\epsilon^{-}_{0}\pm|\epsilon^{-}_{0}|^{\nu}\big{|}$
$\displaystyle<|\epsilon^{-}_{0}|^{\nu}\big{|}2\epsilon^{-}_{0}\pm|\epsilon^{-}_{0}|^{\nu}\big{|}\cdot\frac{2}{3}$
$\displaystyle<\frac{S_{2}+S^{\prime}_{2}}{\gamma^{2}}|\epsilon^{-}_{0}|^{\nu}\big{|}2\epsilon^{-}_{0}\pm|\epsilon^{-}_{0}|^{\nu}\big{|}.$

Note that the right-hand side equals the absolute value of
$2/N-(S_{2}+S^{\prime}_{2})\epsilon^{2}/\gamma^{2}$ for
$\epsilon=\epsilon^{-}_{0}\pm|\epsilon^{-}_{0}|^{\nu}$. We also note that
$2/N-(S_{2}+S^{\prime}_{2})\epsilon^{2}/\gamma^{2}=0$ for
$\epsilon=\epsilon^{-}_{0}$. Therefore, for such large $n$, we have
$\epsilon(m_{1}+m_{3})<0$ for
$\epsilon=\epsilon^{-}_{0}-|\epsilon^{-}_{0}|^{\nu}$ and
$\epsilon(m_{1}+m_{3})>0$ for
$\epsilon=\epsilon^{-}_{0}+|\epsilon^{-}_{0}|^{\nu}$. By the intermediate
value theorem, this shows that there exists
$\epsilon^{-}\in(\epsilon^{-}_{0}-|\epsilon^{-}_{0}|^{\nu},\epsilon^{-}_{0}+|\epsilon^{-}_{0}|^{\nu})$
such that $m_{1}+m_{3}=0$ for $\epsilon=\epsilon^{-}$. In view of our previous
comments, such $\epsilon^{-}$ is unique and we must have

$\lambda^{-}=-\gamma\phi_{0}+\epsilon^{-}.$

This also establishes

$\epsilon^{-}=-\frac{\sqrt{2}}{\sqrt{N}}(1+o(1)),$ (29)

since $|\epsilon^{-}_{0}|^{\nu}=o(\epsilon_{0}^{-})$ when $\nu>1$.

Recall the scalar $\alpha=\alpha^{-}$ for the eigenvalue $\lambda^{-}$, which
is nonzero by Proposition 5. We assume that $\alpha^{-}>0$ after a rescaling
of $\big{|}\lambda^{-}\big{\rangle}$. By Eq. (5) and
$\sum_{\ell=0}^{k}\left\|P_{\ell}\big{|}\lambda^{-}\big{\rangle}\right\|^{2}=1$,
we obtain

$1=(\alpha^{-})^{2}\left(\frac{4}{N(\epsilon^{-})^{2}}+\frac{2(S_{2}+S^{\prime}_{2})}{\gamma^{2}}+O(\epsilon^{-})\right).$

Using Eqs. (28) and (29), we obtain

$\alpha^{-}=\frac{1}{2}+o(1).$ (30)

Recall that $\big{|}\psi(0)\big{\rangle}$ is a $\phi_{0}$-eigenvector of $A$.
By Eq. (5) with $\ell=0$, we also obtain

$\big{\langle}\psi(0)\big{|}\lambda^{-}\big{\rangle}=-\frac{2\alpha^{-}}{\sqrt{N}\,\epsilon^{-}}=\frac{1}{\sqrt{2}}+o(1),$
(31)

where we have also used Eqs. (29) and (30).

We next find the eigenvalue $\lambda^{+}$ for the first excited state of $H$.
On the one hand, by the definition of $H$ and $\big{|}\psi(0)\big{\rangle}$,
we have

$\big{\langle}\psi(0)\big{|}H\big{|}\psi(0)\big{\rangle}=-\gamma\phi_{0}-\frac{2}{N}.$

On the other hand, we also have

$\big{\langle}\psi(0)\big{|}H\big{|}\psi(0)\big{\rangle}=\lambda^{-}\big{|}\big{\langle}\psi(0)\big{|}\lambda^{-}\big{\rangle}\big{|}^{2}+\sum_{\lambda\neq\lambda^{-}}\lambda\big{|}\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}\big{|}^{2},$

where the sum on the right-hand side is over the eigenvalues of $H$ on
$\mathcal{H}_{\mathrm{inv}}$ other than $\lambda^{-}$. By Eqs. (29) and (31),
we have

$\lambda^{-}\big{|}\big{\langle}\psi(0)\big{|}\lambda^{-}\big{\rangle}\big{|}^{2}=-\frac{\gamma\phi_{0}}{2}+o(1),$

where we also note that $\gamma\phi_{0}=1+o(1)$ by Eqs. (18) and (26). Suppose
now that $\lambda^{+}\geqslant-\gamma\phi_{1}$. Then, since
$\sum_{\lambda}\big{|}\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}\big{|}^{2}=1$,
it follows from Eqs. (27) with $\ell=1$ and (31) that

$\sum_{\lambda\neq\lambda^{-}}\lambda\big{|}\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}\big{|}^{2}\geqslant-\gamma\phi_{1}\sum_{\lambda\neq\lambda^{-}}\big{|}\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}\big{|}^{2}=-\frac{\gamma\phi_{1}}{2}+o(1)=-\frac{\gamma\phi_{0}}{2}+\frac{1}{2k}+o(1).$

However, this implies that

$\big{\langle}\psi(0)\big{|}H\big{|}\psi(0)\big{\rangle}\geqslant-\gamma\phi_{0}+\frac{1}{2k}+o(1)>-\gamma\phi_{0}-\frac{2}{N}$

for large $n$, which is a contradiction. (Recall that $k$ is fixed.) Hence,
for large $n$, it follows that $\lambda^{+}<-\gamma\phi_{1}$ and thus
$\lambda^{+}\in(-\gamma\phi_{0},-\gamma\phi_{1})$ by virtue of Corollary 6.
Observe that $m_{1}+m_{3}$ (again as a function of $\lambda$) is also monotone
decreasing on $(-\gamma\phi_{0},-\gamma\phi_{1})$, from which it follows that
$\lambda^{+}$ is the _unique_ eigenvalue of $H$ on
$\mathcal{H}_{\mathrm{inv}}$ in this range. We may now proceed as in the above
discussions, and conclude that

$\lambda^{+}=-\gamma\phi_{0}+\epsilon^{+},$

where

$\epsilon^{+}=\frac{\sqrt{2}}{\sqrt{N}}(1+o(1)).$ (32)

We also obtain the scalar $\alpha=\alpha^{+}$ for the eigenvalue $\lambda^{+}$
as

$\alpha^{+}=\frac{1}{2}+o(1),$ (33)

and

$\big{\langle}\psi(0)\big{|}\lambda^{+}\big{\rangle}=-\frac{2\alpha^{+}}{\sqrt{N}\,\epsilon^{+}}=-\frac{1}{\sqrt{2}}+o(1).$
(34)

Earlier, we referenced a “bad” eigenvalue arising from the condition
$m_{1}-m_{3}=0$, which we have effectively excluded by limiting the dynamics
to $\mathcal{H}_{\mathrm{inv}}$. As a function of
$\lambda=-\gamma\phi_{0}+\epsilon$, the expression $m_{1}-m_{3}$ demonstrates
a monotone decrease over the interval $(-\infty,-\gamma\phi_{1})$. Within this
range, there exists a unique $\lambda$ for which $m_{1}-m_{3}=0$. Following a
similar approach to that in Eq. (21), we derive the following equation:

$m_{1}-m_{3}=1-\frac{S_{1}-S_{1}^{\prime}}{\gamma}-\frac{S_{2}-S_{2}^{\prime}}{\gamma^{2}}\epsilon+O(\epsilon^{2})=\frac{2S_{1}^{\prime}}{\gamma}-\frac{S_{2}-S_{2}^{\prime}}{\gamma^{2}}\epsilon+O(\epsilon^{2}),$

where we have applied Eq. (22). Utilizing Eqs. (23), (24), and (26), we can
approximate the corresponding $\epsilon$ as:

$\epsilon=\frac{2S_{1}^{\prime}\gamma}{S_{2}-S_{2}^{\prime}}=O\\!\left(\frac{1}{n^{\delta}}\right).$

Considering Eqs. (28), (29), and (32), this eigenvalue $\lambda$ exhibits
particularly problematic behavior when $\delta>k/2$, in the sense that
$\lambda\in(\lambda^{-},\lambda^{+})$ for large $n$. Nevertheless, this
adverse behavior does not affect the dynamics since
$\big{\langle}\psi(0)\big{|}\lambda\big{\rangle}=0$.

###  3.3 Computational complexity

Now we apply the general recipe outlined in the previous section to the search
algorithm on $J(n,k)$ by fixing $k$ and letting $n\rightarrow\infty$. Using
Eqs. (30) and (33), we check that
$\big{\langle}w\big{|}\lambda^{+}\big{\rangle}=\big{\langle}w\big{|}\lambda^{-}\big{\rangle}+o(1)$.
Using (31) and (34), we check that
$\big{\langle}\lambda^{+}\big{|}\psi(0)\big{\rangle}=-\big{\langle}\lambda^{-}\big{|}\psi(0)\big{\rangle}+o(1).$
Thus, condition (14) is true.

The probability of finding a marked vertex as a function of time is given by
Eq. (15) and then using Eq. (16) the optimal running time is

$t_{\mathrm{run}}=\frac{\pi\sqrt{N}}{2\sqrt{2}},$

and using Eq. (17) the success probability is

$p_{\mathrm{succ}}=1+o(1).$ (35)

Note that the asymptotic success probability does not depend on $\delta$, the
distance between the two marked vertices $w_{1}$ and $w_{2}$.

We have so far assumed that $\delta$ is known in advance; see Eq. (22). In the
case where we have no prior information on $\delta$, we simply apply the above
search algorithm in turn for $\delta=1,2,\dots,k$. We note that we can check
if the outcome is a marked vertex by applying the oracle for each of the $k$
steps. Hence, the success probability is still given by Eq. (35). The running
time is at most

$\frac{\pi k\sqrt{N}}{2\sqrt{2}}.$

We fix $k$, so this is still of order $O(\sqrt{N})$.

##  4 Final remarks

We have developed a framework to assess analytically the computational
complexity of spatial search algorithms using continuous-time quantum walks on
graphs with multiple marked vertices. This framework is underpinned by four
propositions that not only lay the mathematical foundation but also offer a
practical method for computing the eigenvalues and eigenvectors of the
Hamiltonian. Additionally, these propositions facilitate the determination of
the optimal value for the parameter $\gamma$ in the search algorithm. A key
step in this process involves calculating a basis of eigenvectors of the
kernel of a symmetric matrix, the dimension of which equals the number of
marked vertices. This method applies to any graph whose associated Hamiltonian
exhibits a sufficiently small gap between $\lambda^{\pm}$. In simpler
scenarios, the success probability of the search algorithm can be represented
as $a^{2}\sin^{2}\epsilon t$, with $2\epsilon$ usually being the gap. The
optimal running time is $t=\pi/2\epsilon$, leading to a success probability
$p_{\mathrm{succ}}=a^{2}$. For the search algorithm to achieve optimality,
implying a time complexity of $O(\sqrt{N})$, it is crucial that $\epsilon$
scales as $O(1/\sqrt{N})$ and $a$ maintains an order of $\Omega(1)$.

We demonstrated our framework with an analysis of the spatial search algorithm
on the Johnson graph $J(n,k)$ featuring two marked vertices. Our analysis
indicates that, with $k$ fixed and the distance $\delta$ between the marked
vertices known beforehand, the optimal running time is
$\pi\sqrt{N}/(2\sqrt{2})$, where $N$ is the total number of vertices. In cases
where $\delta$ is not known, the algorithm must be executed $k$ times, each
assuming a different $\delta$. This results in a total running time of at most
$\pi k\sqrt{N}/(2\sqrt{2})$, maintaining a success probability of $1+o(1)$ as
$n$ approaches infinity.

Usually, the condition for the search algorithm be optimal is that the
spectral gap of the Hamiltonian is sufficiently larger than the overlap of the
initial condition with the marked vertex [20]. This condition holds true in
the cases analyzed in the literature when there is only one marked vertex, to
the best of our knowledge. The problem becomes more intricate in the presence
of multiple marked vertices since the time complexity depends on specific
vertex placements in the general case. As discussed above, in Johnson graphs
with two marked vertices, the time complexity is influenced by the distance
between the marked vertices.

The results of this work can accelerate numerical calculations of the
computational complexity of search algorithms on arbitrary graphs. In this
context, certain analytical expressions from Sections 2.2 and 2.3 can be
circumvented. The numerical approach is outlined as follows. Start by
determining numerically $\phi_{0}$ and $\big{|}\phi_{0}\big{\rangle}$. Next,
use the entries of matrix $M^{\lambda}$, as defined in Eq. (3), to identify
$\lambda^{\pm}$ and $\gamma$. Since they need to be found concurrently, we
assign numerical values to both $\gamma$ and $\lambda$ and then check whether
det$(M^{\lambda})=0$. If this is not the case, we change $\gamma$ and
$\lambda$ until locating the roots. Following this, $\epsilon$ is deduced from
$|\lambda^{-}+\gamma\phi_{0}|$. We then we proceed to numerically calculate
$\big{\langle}\lambda^{\pm}\big{|}\phi_{0}\big{\rangle}$ and
$\big{\langle}w\big{|}\lambda^{\pm}\big{\rangle}$ for all $w$.
$\big{\langle}\lambda^{+}\big{|}\phi_{0}\big{\rangle}$ and
$\big{\langle}w\big{|}\lambda^{+}\big{\rangle}$ must be nonzero for at least
one $w$, otherwise $\lambda^{+}$ does not fulfill the required conditions.
Afterwards, we compute the success probability $p(t)$ using Eq. (11). By
plotting $p(t)$, we can evaluate whether the curve resembles the square of a
sinusoidal function and whether the peak is prominent.

## Acknowledgements

The authors thank the editors of ACM Transactions on Quantum Computing for the
invaluable help in improving this paper. The work of P.H.G. Lugão was
supported by CNPq grant number 140897/2020-8. The work of R. Portugal was
supported by FAPERJ grant number CNE E-26/202.872/2018, and CNPq grant number
308923/2019-7. The work of M. Sabri was supported by JST SPRING grant number
JPMJSP2114. The work of H. Tanaka was supported by JSPS KAKENHI grant numbers
JP20K03551 and JP23K03064.

## Appendix

##  Appendix A The proof of Eq. (24)

We first invoke some results from [46] to evaluate the ${}_{3}F_{2}$ series in
Eq. (20). Set

$\phi_{\ell}=\phi_{0}+h\ell(\ell+1+s),\qquad\phi^{*}_{\ell}=\phi_{0}^{*}+s^{*}\ell$

for $0\leqslant\ell\leqslant k$, and

$\alpha_{\ell}=hs^{*}\ell(\ell-k-1)(\ell+r),\qquad\beta_{\ell}=hs^{*}\ell(\ell-k-1)(\ell+r-s-k-1)$

for $1\leqslant\ell\leqslant k$, where

$s=-n-2,\qquad r=k-n-1,$

and $\phi_{0},\phi_{0}^{*},h$, and $s^{*}$ are arbitrary with $h,s^{*}\neq 0$.
The sequence

$\big{(}\phi_{\ell},\phi_{\ell}^{*},\ell=0,\dots,k;\alpha_{\ell^{\prime}},\beta_{\ell^{\prime}},\ell^{\prime}=1,\dots,k\big{)}$

is a _parameter array_ of dual Hahn type; cf. [46, Example 5.12]. Note that
the $\phi_{\ell}$ agree with the eigenvalues of $J(n,k)$ (cf. Eq. (18))
provided that we set $\phi_{0}=k(n-k)$ and $h=1$. Moreover, we have

${}_{3}F_{2}\\!\left.\left(\begin{matrix}-\ell,-\delta,\ell-n-1\\\
k-n,-k\end{matrix}\,\right|1\right)=f_{\delta}(\phi_{\ell}),$

where

$f_{\delta}(x)=\sum_{\nu=0}^{\delta}\frac{(x-\phi_{0})\cdots(x-\phi_{\nu-1})(\phi_{\delta}^{*}-\phi_{0}^{*})\cdots(\phi_{\delta}^{*}-\phi_{\nu-1}^{*})}{\alpha_{1}\cdots\alpha_{\nu}}.$

By [46, Theorem 4.1, Lemma 4.2], we have

$f_{\delta}(x)=\frac{\beta_{1}\cdots\beta_{\delta}}{\alpha_{1}\cdots\alpha_{\delta}}f_{\delta}^{\Downarrow}(x)=\frac{\delta!}{(k-n)_{\delta}}f_{\delta}^{\Downarrow}(x),$

where

$f_{\delta}^{\Downarrow}(x)=\sum_{\nu=0}^{\delta}\frac{(x-\phi_{k})\cdots(x-\phi_{k-\nu+1})(\phi_{\delta}^{*}-\phi_{0}^{*})\cdots(\phi_{\delta}^{*}-\phi_{\nu-1}^{*})}{\beta_{1}\cdots\beta_{\nu}},$

and $(a)_{m}=a(a+1)\cdots(a+m-1)$ denotes the shifted factorial. We have

$f_{\delta}^{\Downarrow}(\phi_{\ell})={}_{3}F_{2}\\!\left.\left(\begin{matrix}\ell-k,-\delta,n-k-\ell+1\\\
1,-k\end{matrix}\,\right|1\right),$

and hence

$_{3}F_{2}\\!\left.\left(\begin{matrix}-\ell,-\delta,\ell-n-1\\\
k-n,-k\end{matrix}\,\right|1\right)=\frac{\delta!}{(k-n)_{\delta}}{}_{3}F_{2}\\!\left.\left(\begin{matrix}\ell-k,-\delta,n-k-\ell+1\\\
1,-k\end{matrix}\,\right|1\right).$ (36)

By Eqs. (18), (19), (20), and (36), we have

$\frac{\big{\langle}w_{1}\big{|}P_{\ell}\big{|}w_{2}\big{\rangle}}{\phi_{0}-\phi_{\ell}}=O\\!\left(\frac{1}{n^{k-\ell+1+\delta-\tau}}\right),\qquad\frac{\big{\langle}w_{1}\big{|}P_{\ell}\big{|}w_{2}\big{\rangle}}{(\phi_{0}-\phi_{\ell})^{2}}=O\\!\left(\frac{1}{n^{k-\ell+2+\delta-\tau}}\right)$

for $1\leqslant\ell\leqslant k$, where $\tau=\min\\{k-\ell,\delta\\}$, and Eq.
(24) follows.

We remark that the above method can be generalized to other families of
$Q$-polynomial distance-regular graphs, again including the Hamming graphs
(see [36, Chap. 9]).

## References

  * [1] E. Farhi and S. Gutmann.  Quantum computation and decision trees.  Phys. Rev. A, 58:915–928, 1998.
  * [2] M. Sipser.  Introduction to the Theory of Computation.  Cengage Learning, 2012.
  * [3] Andrew M. Childs and Jeffrey Goldstone.  Spatial search by quantum walk.  Phys. Rev. A, 70:022314, Aug 2004.
  * [4] A. Ambainis, J. Kempe, and A. Rivosh.  Coins make quantum walks faster.  In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms SODA, pages 1099–1108, 2005.
  * [5] R. Portugal and T. D. Fernandes.  Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians.  Phys. Rev. A, 95:042341, 2017.
  * [6] L. K. Grover.  Quantum mechanics helps in searching for a needle in a haystack.  Phys. Rev. Lett., 79(2):325–328, 1997.
  * [7] P. Benioff.  Space searches with a quantum robot.  AMS Contemporary Math Series, 305, 2002.
  * [8] N. Shenvi, J. Kempe, and K. B. Whaley.  A quantum random walk search algorithm.  Phys. Rev. A, 67(5):052307, 2003.
  * [9] A. M. Childs, E. Farhi, and S. Gutmann.  An example of the difference between quantum and classical random walks.  Quantum Inf. Process., 1(1):35–43, 2002.
  * [10] J. Abhijith and A. Patel.  Spatial search on graphs with multiple targets using flip-flop quantum walk.  Quantum Info. Comput., 18(15–16):1295–1331, 2018.
  * [11] B. Chagas, R. Portugal, S. Boettcher, and E. Segawa.  Staggered quantum walk on hexagonal lattices.  Phys. Rev. A, 98:052310, 2018.
  * [12] G. A. Bezerra, P. H. G. Lugão, and R. Portugal.  Quantum-walk-based search algorithms with multiple marked vertices.  Phys. Rev. A, 103:062202, 2021.
  * [13] S. Chakraborty, L. Novo, A. Ambainis, and Y. Omar.  Spatial search by quantum walk is optimal for almost all graphs.  Phys. Rev. Lett., 116:100501, 2016.
  * [14] Pascal Philipp, Luís Tarrataca, and Stefan Boettcher.  Continuous-time quantum search on balanced trees.  Phys. Rev. A, 93:032305, 2016.
  * [15] Thomas G. Wong.  Spatial search by continuous-time quantum walk with multiple marked vertices.  Quantum Information Processing, 15(4):1411–1443, Apr 2016.
  * [16] Marco Cattaneo, Matteo A. C. Rossi, Matteo G. A. Paris, and Sabrina Maniscalco.  Quantum spatial search on graphs subject to dynamical noise.  Phys. Rev. A, 98:052347, 2018.
  * [17] Xi Li, Hanwu Chen, Yue Ruan, Zhihao Liu, and Wenjie Liu.  Continuous-time quantum walks on strongly regular graphs with loops and its application to spatial search for multiple marked vertices.  Quantum Information Processing, 18(6):195, 2019.
  * [18] Rebekah Herrman and Travis S. Humble.  Continuous-time quantum walks on dynamic graphs.  Phys. Rev. A, 100:012306, 2019.
  * [19] Yunkai Wang, Shengjun Wu, and Wei Wang.  Controlled quantum search on structured databases.  Phys. Rev. Research, 1:033016, 2019.
  * [20] S. Chakraborty, L. Novo, and J. Roland.  Optimality of spatial search via continuous-time quantum walks.  Phys. Rev. A, 102:032214, 2020.
  * [21] Matteo G. A. Paris, Claudia Benedetti, and Stefano Olivares.  Improving quantum search on simple graphs by pretty good structured oracles.  Symmetry, 13(1), 2021.
  * [22] Michele Delvecchio, Caspar Groiseau, Francesco Petiziol, Gil S Summy, and Sandro Wimberger.  Quantum search with a continuous-time quantum walk in momentum space.  Journal of Physics B: Atomic, Molecular and Optical Physics, 53(6):065301, 2020.
  * [23] Kunkun Wang, Yuhao Shi, Lei Xiao, Jingbo Wang, Yogesh N. Joglekar, and Peng Xue.  Experimental realization of continuous-time quantum walks on directed graphs and their application in pagerank.  Optica, 7(11):1524–1530, 2020.
  * [24] Claudia Benedetti, Dario Tamascelli, Matteo G.A. Paris, and Andrea Crespi.  Quantum spatial search in two-dimensional waveguide arrays.  Phys. Rev. Applied, 16:054036, 2021.
  * [25] Dengke Qu, Samuel Marsh, Kunkun Wang, Lei Xiao, Jingbo Wang, and Peng Xue.  Deterministic search on star graphs via quantum walks.  Phys. Rev. Lett., 128:050501, 2022.
  * [26] M. Szegedy.  Quantum speed-up of Markov chain based algorithms.  In Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’04, pages 32–41, Washington, 2004.
  * [27] F. Magniez, A. Nayak, J. Roland, and M. Santha.  Search via quantum walk.  SIAM Journal on Computing, 40(1):142–164, 2011.
  * [28] Frédéric Magniez, Ashwin Nayak, Peter C. Richter, and Miklos Santha.  On the hitting times of quantum versus random walks.  Algorithmica, 63(1–2):91–116, jun 2012.
  * [29] H. Krovi, F. Magniez, M. Ozols, and J. Roland.  Quantum walks can find a marked element on any graph.  Algorithmica, 74:851–907, 2016.
  * [30] Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis.  Quadratic Speedup for Finding Marked Vertices by Quantum Walks, page 412–424.  Association for Computing Machinery, New York, NY, USA, 2020.
  * [31] S. Chakraborty, L. Novo, and J. Roland.  Finding a marked node on any graph via continuous-time quantum walks.  Phys. Rev. A, 102:022227, 2020.
  * [32] Simon Apers, Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland.  Quadratic speedup for spatial search by continuous-time quantum walk.  arXiv:2112.12746, 2021.
  * [33] R.D. Somma and G. Ortiz.  Quantum Approach to Classical Thermodynamics and Optimization, pages 1–20.  Lecture Notes in Physics, vol 802. Springer, Berlin, Heidelberg, 2010\.
  * [34] Thomas G. Wong.  Quantum walk search on Johnson graphs.  Journal of Physics A: Mathematical and Theoretical, 49(19):195303, 2016.
  * [35] H. Tanaka, M. Sabri, and R. Portugal.  Spatial search on Johnson graphs by continuous-time quantum walk.  Quantum Information Processing, 21(2):74, Jan 2022.
  * [36] A. E. Brouwer, A. M. Cohen, and A. Neumaier.  Distance-Regular Graphs.  Modern Surveys in Mathematics. Springer, Berlin, 1989.
  * [37] A. E. Brouwer and W. H. Haemers.  Spectra of Graphs.  Springer, New York, 2012.
  * [38] Roger A. Horn and Charles R. Johnson.  Matrix Analysis.  Cambridge University Press, Cambridge, 2nd edition, 2013.
  * [39] Rajendra Bhatia.  Matrix Analysis, volume 169.  Springer, 1997.
  * [40] Thomas G. Wong, Luís Tarrataca, and Nikolay Nahimov.  Laplacian versus adjacency matrix in quantum walk search.  Quantum Information Processing, 15(10):4029–4048, 2016.
  * [41] P. H. G. Lugão and R. Portugal.  Quantum search by continuous-time quantum walk on $t$-designs.  arXiv:310.14141, 2023.
  * [42] E. Bannai and T. Ito.  Algebraic Combinatorics I.  Benjamin/Cummings, Menlo Park, CA, 1984.
  * [43] E. R. van Dam, J. H. Koolen, and H. Tanaka.  Distance-regular graphs.  Electronic Journal of Combinatorics, Dynamic Surveys, DS22, 2016\.
  * [44] W. J. Martin and H. Tanaka.  Commutative association schemes.  European Journal of Combinatorics, 30(6):1497–1525, 2009.
  * [45] Steven G. Krantz.  Function theory of several complex variables.  AMS Chelsea Publishing, Providence, 2nd edition, 1992.
  * [46] Paul Terwilliger.  Two linear transformations each tridiagonal with respect to an eigenbasis of the other; comments on the parameter array.  Designs, Codes and Cryptography, 34(2-3):307–332, 2005.