# Of Shadows and Gaps in Spatial Search

Ada Chan Department of Mathematics and Statistics, York University. Chris
Godsil Department of Combinatorics and Optimization, University of Waterloo.
Christino Tamon Department of Computer Science, Clarkson University. Contact:
<EMAIL_ADDRESS>Weichen Xie Department of Mathematics, Clarkson University

###### Abstract

Spatial search occurs in a connected graph if a continuous-time quantum walk
on the adjacency matrix of the graph, suitably scaled, plus a rank-one
perturbation induced by any vertex will unitarily map the principal
eigenvector of the graph to the characteristic vector of the vertex. This
phenomenon is a natural continuous-time analogue of Grover search. The spatial
search is said to be optimal if it occurs with constant fidelity and in time
inversely proportional to the shadow of the target vertex on the principal
eigenvector. Extending a result of Chakraborty et al. (Physical Review A,
102:032214, 2020), we prove a simpler characterization of optimal spatial
search. Based on this characterization, we observe that some families of
distance-regular graphs, such as Hamming and Grassmann graphs, have optimal
spatial search. We also show a matching lower bound on time for spatial search
with constant fidelity, which extends a bound due to Farhi and Gutmann for
perfect fidelity. Our elementary proofs employ standard tools, such as Weyl
inequalities and Cauchy determinant formula.

Keywords: Quantum walk, spatial search, spectral gap, perturbation.

##  1 Introduction

In the seminal work [7], Grover described a quantum algorithm with a provable
quadratic speedup for the ubiquitous search problem. It was realized later
that his algorithm can be viewed as a discrete-time quantum walk on the
complete graph [1, 14]. In another fundamental work, Farhi and Gutmann [6]
proposed a continuous-time analog of Grover search. Their work was generalized
by Childs and Goldstone [5] to arbitrary graphs where the problem is known as
spatial search.

Figure 1: Grover search in continuous-time (see Farhi and Gutmann [6]): a
continuous-time quantum walk with $H=\gamma A(K_{n})+e_{w}e_{w}^{T}$ can
perfectly transfer the density matrix $E_{1}=\frac{1}{n}J_{n}$ to the target
state $e_{w}e_{w}^{T}$, for some $\gamma>0$, in time $\frac{\pi}{2}\sqrt{n}$.
Here, $e_{w}$ denote the unit vector associated to vertex $w$ of the clique.

Suppose $G$ is an undirected and connected graph on $n$ vertices with
normalized adjacency matrix $A$ whose spectral decomposition is given by
$A=\sum_{r=1}^{d}\theta_{r}E_{r}$, where
$1=\theta_{1}>\theta_{2}>\ldots>\theta_{d}\geq 0$ and $E_{r}$ is the
orthogonal projection onto the eigenspace corresponding to $\theta_{r}$. We
say $G$ has optimal spatial search if for any vector $w$ (which may correspond
to the characteristic vector of a vertex of $G$), the continuous-time quantum
walk

$\rho(t)=e^{-itH}\rho(0)e^{itH}$

with the time-independent Hamiltonian $H=\gamma A+{w}{w}^{\dagger}$, for a
scaling factor $\gamma>0$, maps the density matrix $\rho(0)=E_{1}$ to the
target state ${w}{w}^{\dagger}$ with a constant fidelity, that is,

$f(t):=\operatorname{Tr}({w}{w}^{\dagger}\rho(t))=\Omega_{n}(1),$

in time $t=O_{n}(1/\epsilon_{1})$, where $\epsilon_{1}=\left\lVert
E_{1}w\right\rVert$ is the shadow of the target vertex on the principal
eigenspace of $G$.

Farhi and Gutmann [6] showed that the complete graphs have spatial search
(which recovers Grover’s result in the continuous-time setting). They also
proved a time lower bound of $\Omega_{n}(\sqrt{n})$ for any continuous-time
quantum algorithm with unit fidelity on vertex-transitive graphs. As our first
result, we strengthen their time lower bound to $\Omega_{n}(1/\epsilon_{1})$
which holds for constant fidelity (instead of perfect). This lower bound
justifies the requirement that the optimal time is $O_{n}(1/\epsilon_{1})$.

Chakraborty et al. [3] observed a striking property: a constant spectral gap
$\Delta_{2}$ is sufficient for optimal spatial search. Here,
$\Delta_{2}=\theta_{1}-\theta_{2}$ is the distance between the two largest
normalized eigenvalues of the graph. In particular, this implies that random
graphs exhibit spatial search property almost surely. But, this does not
explain why the $n$-cube has spatial search (studied by Childs and Goldstone
[5]) since the spectral gap vanishes as $n$ grows.

Subsequently, Chakraborty et al. [4] improved the observation from [3] by
showing a characterization of optimal spatial search under the assumption of

$\epsilon_{1}\ll\frac{S_{1}S_{2}}{S_{3}}\ \ \mbox{ and }\ \
\epsilon_{1}\ll\sqrt{S_{2}}\Delta_{2},$ (1)

where $S_{k}=\sum_{r=2}^{d}\left\lVert
E_{r}w\right\rVert^{2}(\theta_{1}-\theta_{r})^{-k}$, for $k=1,2,3$, are
spectral parameters related to the graph $G$. Another crucial observation made
in [4] is that $S_{1}$ is the best choice for the scaling parameter $\gamma$.
As stated in [4], the unconditional characterization of graphs with optimal
spatial search is a longstanding open question.

In this work, we improve the result of Chakraborty et al. [4] by showing a
characterization of optimal spatial search under the simpler assumption

$\epsilon_{1}\ll\sqrt{S_{1}}\Delta_{2},$

also under the choice of $\gamma=S_{1}$. We show that our assumption is
asymptotically similar to the second condition in Equation (1) for the
relevant ranges of interest. Our improvement is obtained through tighter
estimates on the leading eigenvalue perturbations derived from a determinant
formula of Cauchy. We also observe a critical condition (hidden in previous
analyses) for the strict interlacing between pairs of the two largest
eigenvalues of the matrices, before and after perturbation. For this, we
explicitly require the second largest eigenvalue of the graph belong to the
eigenvalue support of the target vertex, and then appeal to Weyl inequalities
to provide strict interlacing.

We then apply the characterization to provide new examples of graphs with
optimal spatial search and to offer alternative proofs for existing families.
For example, we observe that the Hamming graphs $H(n,q)$, for any constant
$q$, have optimal spatial search. As a special case, this include the binary
$n$-cube $H(n,2)$ which was observed by Childs and Goldstone [5]. For another
example, we observe that strongly regular graphs have optimal spatial search
since they also have constant spectral gap. This confirms the observation of
Janmark et al. [9] obtained using degenerate perturbation theory.

For distance regular graphs with larger diameter, Wong [17] and then Tanaka et
al. [15] proved that the Johnson graphs $J(n,k)$, for constant $k\geq 3$, have
spatial search. Since the constant spectral gap condition holds for Johnson
graphs, this provides an alternative and immediate proof that they have
optimal spatial search. Moreover, we also observe that Grassmann graphs and,
in fact, most bounded diameter distance-regular graphs with classical
parameters have optimal spatial search (see Figure 2). Both of there are again
consequences of the constant spectral gap condition.

Our original motivation for this work was to understand obstructions to
optimal spatial search. To this end, we found a collection of necessary
conditions for spatial search which are largely based on techniques used in
[4]. Aside from being a crucial ingredient for proving the tight
characterization, these necessary conditions provide asymptotic explanations
why certain families of graphs lack the spatial search property. For example,
they can be used to show explicitly why cycles lack optimal spatial search – a
well-known folklore result. These conditions can potentially be adapted to
other classes such as a small Cartesian product of cycles.

The proofs we employ are elementary as they only use basic tools from matrix
theory which do not appeal to perturbative methods. We nevertheless adopt
standard asymptotic arguments commonly used in random graphs and complexity of
algorithms.

##  2 Background

We assume the standard inner product $\langle v,w\rangle$ over
$\mathbb{C}^{n}$. All vectors are assumed normalized under the $2$-norm
defined by $\left\lVert w\right\rVert=\sqrt{\langle w,w\rangle}$. The set of
all $n\times n$ matrices with complex entries is denoted
$\operatorname{Mat}_{n}(\mathbb{C})$. As with vectors, we define the $2$-norm
of a matrix as $\left\lVert A\right\rVert=\sqrt{\langle A,A\rangle}$, where
$\langle A,B\rangle=\operatorname{Tr}(A^{\dagger}B)$ is the inner product
between matrices. The spectrum $\operatorname{Spec}(A)$ of a matrix $A$ is the
set of its eigenvalues. In this work, we will focus primarily on Hermitian
matrices whose eigenvalues are guaranteed to be real. We adopt the notation
$\lambda_{i}(A)$ to represent the $i$th largest eigenvalue of the matrix $A$.
We call a Hermitian matrix normalized if its spectrum lies in $[0,1]$ and $1$
is a simple eigenvalue; so, in this case
$1=\lambda_{1}(A)>\lambda_{2}(A)\geq\ldots\geq\lambda_{n}(A)\geq 0$.

In stating the spectral decomposition of a Hermitian matrix, say
$A=\sum_{r=1}^{d}\theta_{r}E_{r}$, we always assume the distinct eigenvalues
are listed in decreasing order, that is,
$\theta_{1}>\theta_{2}>\ldots>\theta_{d}$. Recall that $E_{r}$ is the
orthogonal projection onto the eigenspace corresponding to eigenvalue
$\theta_{r}$ where $E_{r}$ is Hermitian with $E_{r}^{2}=E_{r}$,
$\sum_{r=1}^{d}E_{r}=I$, and $E_{r}E_{s}=E_{r}$ if $r=s$ and is $0$ otherwise.
The eigenvalue support of a vector $w\in\mathbb{C}^{n}$ with respect to $A$ is
defined as

$\operatorname{Supp}_{A}(w)=\\{\theta_{r}:\left\lVert E_{r}w\right\rVert\neq
0\\},$ (2)

which is the set of eigenvalues whose eigenspaces are not fully contained in
the subspace $w^{\perp}$. For each positive integer $k$, we let

$S_{k}=\sum_{r=2}^{d}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{(\theta_{1}-\theta_{r})^{k}}.$ (3)

These are spectral parameters which will play an important role in
characterizing optimal spatial search. They originally appeared in Childs and
Goldstone [5]. Further background on matrix theory may be found in Horn and
Johnson [8].

#### Asymptotics

We use the standard asymptotic notation to compare the relative order of
magnitude of two sequences of numbers $f_{n}$ and $g_{n}$ depending on a
parameter $n\rightarrow\infty$. Our main source is Janson et al. [10]. We
assume $f_{n},g_{n}>0$ for sufficiently large $n$.

  * •

$f_{n}=O_{n}(g_{n})$ as $n\rightarrow\infty$ if there exist constants
$c,n_{0}>0$ such that $f_{n}\leq cg_{n}$ for $n\geq n_{0}$. We write
$f_{n}\lesssim g_{n}$ if $f_{n}=O_{n}(g_{n})$.

  * •

$f_{n}=\Omega_{n}(g_{n})$ as $n\rightarrow\infty$ if there exist constants
$c,n_{0}>0$ such that $f_{n}\geq cg_{n}$ for $n\geq n_{0}$. We write
$f_{n}\gtrsim g_{n}$ if $f_{n}=\Omega_{n}(g_{n})$.

  * •

$f_{n}=\Theta_{n}(g_{n})$ as $n\rightarrow\infty$ if $f_{n}=O(g_{n})$ and
$f_{n}=\Omega(g_{n})$. We write $f_{n}\asymp g_{n}$ if $f_{n}=\Theta(g_{n})$.

  * •

$f_{n}=o_{n}(g_{n})$ if $f_{n}/g_{n}\rightarrow 0$ as $n\rightarrow\infty$. We
write $f_{n}\ll g_{n}$ if $f_{n}=o(g_{n})$.

  * •

$f_{n}=\omega_{n}(g_{n})$ if $g_{n}/f_{n}\rightarrow 0$ as
$n\rightarrow\infty$. We write $f_{n}\gg g_{n}$ if $f_{n}=\omega(g_{n})$.

  * •

$f_{n}\sim g_{n}$ if $f_{n}/g_{n}\rightarrow 1$ as $n\rightarrow\infty$.

We omit the expression “as $n\rightarrow\infty$” when it is clear from
context. Given that most results are asymptotic, we assume that $n$ is
sufficiently large without explicitly stating this.

Our focus is on a family of graphs $\\{G_{n}\\}_{n=1}^{\infty}$ instead of
individual graphs, and hence most assertions are asymptotic in nature and will
depend on $n$ as it tends to $\infty$. When it is clear, we simply write
$G_{n}$ for the family of graphs, and even simply $G$ if $n$ is understood
from context. Given a graph $G=(V,E)$ that is undirected, its adjacency matrix
$A(G)$ is a matrix whose $(u,v)$-entry is $1$ if $(u,v)\in E$, and is $0$
otherwise. In this work, we will allow the adjacency matrix be a Hermitian
matrix whose nonzero entries are complex valued, and will denote it as $H(G)$.
For example, this may include the case of signed graphs ($\pm 1$ entries) or
complex oriented graphs ($\pm i$ entries).

A continuous-time quantum walk on $G$ with a Hermitian adjacency matrix $H(G)$
is governed by the Schrödinger equation defined by

$\rho^{\prime}(t)=-i[H(G),\rho(t)]$ (4)

where $\rho(t)$ is a positive semidefinite matrix of unit trace (also called a
density matrix). The solution of the above equation is given by

$\rho(t)=e^{-itH(G)}\rho(0)e^{itH(G)}.$

We adopt the density matrix formulation of the Schrödinger evolution since it
leads to simpler analyses overall (as global phase factors disappear, for
example) and it can be easily generalized to more realistic settings. For more
background on quantum information, please see Nielsen and Chuang [12]

Given that spatial search is heavily influenced by the seminal work [7], in
the rest of this paper we will call a graph with the optimal spatial search
property Groverian.

###### 2.1 Definition

Let $\\{G_{n}\\}$ be a family of graphs with normalized adjacency matrix
$H(G_{n})$ where $E_{1}$ is the orthogonal projection onto its principal
eigenspace. We say $G_{n}$ is $\gamma$-Groverian if for any
$w\in\mathbb{C}^{n}$ with $\left\lVert E_{1}w\right\rVert\neq 0$, the density
matrix evolution defined by

$\rho(t)=U(t)\rho(0)U(t)^{-1},\ \hskip 21.68121pt\ \mbox{ with
$\rho(0)=E_{1}$},$

where $U(t)=\exp(-it(\gamma H(G_{n})+{w}{w}^{\dagger}))$, there is a time
$\tau=O_{n}(1/\left\lVert E_{1}w\right\rVert)$ so that the fidelity satisfies

$f(\tau):=\operatorname{Tr}({w}{w}^{\dagger}\rho(\tau))=\Omega_{n}(1).$ (5)

The family of graphs is Groverian if it is $\gamma$-Groverian for some
$\gamma>0$. It is perfectly Groverian if $f(\tau)=1-o_{n}(1)$.

The condition on time is the quadratic speedup requirement that is the
hallmark signature of Grover search. This is because the probability of
measuring $w$ given the state $E_{1}$ is $\left\lVert E_{1}w\right\rVert^{2}$,
and hence generating $w$ has a geometric time of $1/\left\lVert
E_{1}w\right\rVert^{2}$.

Given that most of our statements hold for Hermitian matrices, we will view
graphs largely through their Hermitian adjacency matrices. To that end, we fix
a convenient terminology to capture a triplet of a Hermitian matrix, a unit
norm vector and a positive scalar that will play a central role in all of our
assertions.

###### 2.2 Assumption

We call $(H,w,\gamma)$ a tuplet if the following (notational) assumptions
hold.

  1. (a)

$H\in\operatorname{Mat}_{n}(\mathbb{C})$ is a normalized Hermitian matrix
whose spectral decomposition is $H=\sum_{r}\theta_{r}E_{r}$. Recall that as
$H$ is normalized, its eigenvalues lie in $[0,1]$ and $1$ is a simple
eigenvalue.

  2. (b)

$w\in\mathbb{C}^{n}$ is a vector with unit norm which satisfies $\left\lVert
E_{1}w\right\rVert\neq 0$ and $\left\lVert E_{1}w\right\rVert=o_{n}(1)$.

  3. (c)

$\gamma\in\mathbb{R}$ is a positive scalar whereby the perturbed matrix
$\gamma H+{w}{w}^{\dagger}$ has the spectral decomposition
$\sum_{p}\zeta_{p}F_{p}$.

##  3 Time Lower Bounds

We motivate the condition on time in Definition 2.1. Farhi and Gutmann [6]
proved that spatial search with fidelity $1$ on a vertex-transitive graph
requires time $\Omega_{n}(\sqrt{n})$. We extend their result to show a time
lower bound of $\Omega_{n}(1/\left\lVert E_{1}w\right\rVert)$ for constant
fidelity which applies to arbitrary graphs. Note that $\left\lVert
E_{1}w\right\rVert=1/\sqrt{n}$ for vertex-transitive graphs whenever $w$
denote the characteristic vector of a vertex. This matching lower bound
justifies the choice of the optimal time.

###### 3.1 Theorem

Let $(H,w,\gamma)$ be a tuplet where $H$ is $\gamma$-Groverian at time $\tau$.
Then, $\tau=\Omega_{n}(1/\left\lVert E_{1}w\right\rVert)$.

###### Proof.

Let $H_{w}=H_{0}+{w}{w}^{\dagger}$, where $H_{0}=\gamma H$. We compare two
density matrix evolutions given by

$\rho^{\prime}_{w}(t)=-i[H_{w},\rho_{w}(t)],\ \ \
\rho^{\prime}_{0}(t)=-i[H_{0},\rho_{0}(t)]$ (6)

with $\rho_{w}(0)=\rho_{0}(0)=E_{1}$. Note $\rho_{0}(t)=E_{1}$ for all $t$.
Assume for now that the fidelity is perfect or
$\rho_{w}(\tau)={w}{w}^{\dagger}$. We will remove this assumption later.

The proof proceeds by analyzing bounds on
$\left\lVert\rho_{w}(t)-\rho_{0}(t)\right\rVert^{2}$. First, by taking
derivative, we have

$\frac{d}{dt}\left\lVert\rho_{w}(t)-\rho_{0}(t)\right\rVert^{2}=-2\langle\rho_{w}(t),\rho_{0}(t)\rangle^{\prime}.$

From the product rule and Equation (6), we see that

$\displaystyle\langle\rho_{w}(t),\rho_{0}(t)\rangle^{\prime}$ $\displaystyle=$
$\displaystyle\langle\rho_{w}(t),\rho^{\prime}_{0}(t)\rangle+\langle\rho^{\prime}_{w}(t),\rho_{0}(t)\rangle$
$\displaystyle=$ $\displaystyle i\langle[H_{w},\rho_{w}(t)],E_{1}\rangle$
$\displaystyle=$ $\displaystyle i\langle w,[E_{1},\rho_{w}(t)]w\rangle.$

Now, notice that

$\displaystyle|\langle w,[E_{1},\rho_{w}(t)]w\rangle|$ $\displaystyle\leq$
$\displaystyle 2|\langle w,E_{1}\rho_{w}(t)w\rangle|,\ \mbox{ as
$|x^{\dagger}[A,B]x|\leq 2|x^{\dagger}(AB)x|$}$ $\displaystyle\leq$
$\displaystyle 2\left\lVert
E_{1}w\right\rVert\left\lVert\rho_{w}(t)w\right\rVert,\ \mbox{ since $|\langle
a,b\rangle|\leq\left\lVert a\right\rVert\left\lVert b\right\rVert$}$
$\displaystyle\leq$ $\displaystyle 2\left\lVert E_{1}w\right\rVert,\ \hskip
14.45377pt\mbox{ because $\left\lVert\rho_{w}(t)w\right\rVert\leq 1$.}$

Putting these together, we get

$\frac{d}{dt}\left\lVert\rho_{w}(t)-\rho_{0}(t)\right\rVert^{2}\ \leq\
4\left\lVert E_{1}w\right\rVert.$

By the Fundamental Theorem of Calculus, we obtain

$\left\lVert\rho_{w}(\tau)-\rho_{0}(\tau)\right\rVert^{2}\ =\
\int_{0}^{\tau}\left(\frac{d}{dt}\left\lVert\rho_{w}(t)-\rho_{0}(t)\right\rVert^{2}\right)dt\
\leq\ 4\left\lVert E_{1}w\right\rVert\tau.$ (7)

Since $\rho_{w}(\tau)={w}{w}^{\dagger}$, we have
$\left\lVert\rho_{w}(\tau)-\rho_{0}(\tau)\right\rVert^{2}=2(1-\left\lVert
E_{1}w\right\rVert^{2})$, and therefore

$1-\left\lVert E_{1}w\right\rVert^{2}\ \leq\ 2\left\lVert
E_{1}w\right\rVert\tau,$

which yields the lower bound $\tau=\Omega_{n}(1/\left\lVert
E_{1}w\right\rVert)$.

Finally, we remove the assumption $\rho_{w}(\tau)={w}{w}^{\dagger}$. Suppose
that $\left\lVert\rho_{w}(\tau)-{w}{w}^{\dagger}\right\rVert^{2}\leq\delta$,
for some $\delta\in(0,1)$. Our strategy is to reduce this case to the former
case by using the following inequality.

###### 3.2 Fact

(Triangle Inequality for Squared Norm) For matrices
$A,B,C\in\operatorname{Mat}_{n}(\mathbb{C})$,

$\left\lVert A-C\right\rVert^{2}\leq 2\left\lVert
A-B\right\rVert^{2}+2\left\lVert B-C\right\rVert^{2}.$

###### Proof.

Squaring the triangle inequality, we get

$\left\lVert A-C\right\rVert^{2}\leq\left\lVert
A-B\right\rVert^{2}+\left\lVert B-C\right\rVert^{2}+2\left\lVert
A-B\right\rVert\left\lVert B-C\right\rVert.$

Now, observe $0\leq(\left\lVert A-C\right\rVert-\left\lVert
B-C\right\rVert)^{2}$. ∎

Applying Fact 3.2, we see that

$2\left\lVert\rho_{w}(\tau)-\rho_{0}(\tau)\right\rVert^{2}\geq\left\lVert{w}{w}^{\dagger}-\rho_{0}(\tau)\right\rVert^{2}-2\left\lVert\rho_{w}(\tau)-{w}{w}^{\dagger}\right\rVert^{2}\geq\left\lVert{w}{w}^{\dagger}-\rho_{0}(\tau)\right\rVert^{2}-2\delta.$

Thus, we have

$\left\lVert\rho_{w}(\tau)-\rho_{0}(\tau)\right\rVert^{2}\ \geq\
(1-\left\lVert E_{1}w\right\rVert^{2}-\delta)$

which can be combined with Equation (7) to obtain
$\tau=\Omega_{n}(1/\left\lVert E_{1}w\right\rVert)$. ∎

##  4 Interlacing

We review some relevant tools from matrix theory and prove a few preliminary
results.

###  4.1 Weyl Inequalities

A theorem of Weyl on eigenvalue interlacing is key to our analysis. Given that
we restate the theorem slightly, we prove it for completeness.

###### 4.1 Lemma

(Subspace intersection, Lemma 4.2.3 in [8])
Let $W_{1},\ldots,W_{k}$ be subspaces of $\mathbb{C}^{n}$ and let $d=\dim
W_{1}+\ldots+\dim W_{k}-(k-1)n$. If $d\geq 1$, then
$\dim(\bigcap_{i=1}^{k}W_{i})\geq d$. In particular, there is a unit vector in
$W_{1}\cap\ldots\cap W_{k}$.

###### Proof.

Note that $\dim(W_{1}\cap W_{2})+\dim(W_{1}+W_{2})=\dim W_{1}+\dim W_{2}$,
which implies $\dim(W_{1}\cap W_{2})\geq\dim W_{1}+\dim W_{2}-n$. So, if $\dim
W_{1}+\dim W_{2}-n\geq 1$, then $W_{1}\cap W_{2}$ contains a nonzero vector.
The claim follows by induction. ∎

###### 4.2 Theorem

(Weyl Interlacing, restatement of Lemma 4.3.1 in [8])
Let $A,B$ be two $n\times n$ Hermitian matrices. For $i=1,\ldots,n$, we have

$\lambda_{i}(A+B)\ \leq\ \lambda_{i-j}(A)+\lambda_{j+1}(B),\ \ \mbox{
$j=0,\ldots,i-1$}$ (8)

with equality if and only if there is $v\neq 0$ so that
$(A+B)v=\lambda_{i}(A+B)v$, $Av=\lambda_{i-j}(A)v$, and
$Bv=\lambda_{j+1}(B)v$, and we have

$\lambda_{i+j}(A)+\lambda_{n-j}(B)\ \leq\ \lambda_{i}(A+B),\ \ \mbox{
$j=0,\ldots,n-i$}$ (9)

with equality if and only if there is $v\neq 0$ so that
$(A+B)v=\lambda_{i}(A+B)v$, $Av=\lambda_{i+j}(A)v$, and
$Bv=\lambda_{n-j}(B)v$.

###### Proof.

For $i=1,\ldots,n$, let $z_{i}$, $x_{i}$, and $y_{i}$ be orthonormal
eigenvectors of $A$, $B$, and $A+B$, respectively, corresponding to their
$i$th largest eigenvalues.

We define $W_{1}=\operatorname{span}\\{z_{i-j},\ldots,z_{n}\\}$,
$W_{2}=\operatorname{span}\\{x_{j+1},\ldots,x_{n}\\}$, and
$W_{3}=\operatorname{span}\\{y_{1},\ldots,y_{i}\\}$. Let $d_{1}=\dim
W_{1}=n-i+j+1$, $d_{2}=\dim W_{2}=n-j$, and $d_{3}=\dim W_{3}=i$. Since
$\dim(W_{1}\cap W_{2}\cap W_{3})=d_{1}+d_{2}+d_{3}-\dim(W_{1}+W_{2}+W_{3})\geq
d_{1}+d_{2}+d_{3}-2n=1$, the subspace $W_{1}\cap W_{2}\cap W_{3}$ contains a
nonzero vector $v$. For any nonzero $v\in W_{1}\cap W_{2}\cap W_{3}$, we have

$\lambda_{i}(A+B)\leq v^{\dagger}(A+B)v\leq\lambda_{i-j}(A)+\lambda_{j+1}(B),\
\mbox{ for $j=0,\ldots,i-1$. }$ (10)

Equality is achieved for $i,j$ if and only if there is a nonzero $v\in
W_{1}\cap W_{2}\cap W_{3}$ for which $(A+B)v=\lambda_{i}(A+B)v$,
$Av=\lambda_{i-j}(A)v$, and $Bv=\lambda_{j+1}(B)v$.

For the second inequality, observe that $\lambda_{i}(-A)=-\lambda_{n-i+1}(A)$.
Therefore,

$-\lambda_{n-i+1}(A+B)=\lambda_{i}(-A-B)\leq\lambda_{i-j}(-A)+\lambda_{j+1}(-B)=-\lambda_{n-i+j+1}(A)-\lambda_{n-j}(B)$
(11)

which implies

$\lambda_{n-i+j+1}(A)+\lambda_{n-j}(B)\leq\lambda_{n-i+1}(A+B).$ (12)

Now, rename $n-i+1$ to $i$ and keep $j$ (and hence $n-i+j+1$ to $i+j$). This
yields

$\lambda_{i+j}(A)+\lambda_{n-j}(B)\leq\lambda_{i}(A+B),\ \mbox{ for
$j=0,\ldots,n-i$. }$ (13)

Equality is achieved for $i,j$ if and only if there is a nonzero $v\in
W_{1}\cap W_{2}\cap W_{3}$ for which $(A+B)v=\lambda_{i}(A+B)v$,
$Av=\lambda_{i+j}(A)v$, and $Bv=\lambda_{n-j}(B)v$ with
$W_{1}=\operatorname{span}\\{z_{1},\ldots,z_{i+j}\\}$,
$W_{2}=\operatorname{span}\\{x_{1},\ldots,x_{n-j}\\}$, and
$W_{3}=\operatorname{span}\\{y_{i},\ldots,y_{n}\\}$. ∎

###### 4.3 Lemma

(Strict Interlacing) Let $H$ be a normalized $n\times n$ Hermitian matrix with
spectral decomposition $H=\sum_{r}\theta_{r}E_{r}$. Let $w\in\mathbb{C}^{n}$
be vector with unit norm where
$\theta_{1},\theta_{2}\in\operatorname{Supp}_{H}(w)$. Then for any $\gamma>0$,
the two largest eigenvalues of $\gamma H+{w}{w}^{\dagger}$ are simple and they
strictly interlace the two largest eigenvalues of $\gamma H$.

###### Proof.

We apply Theorem 4.2 with $A=\gamma H$ and $B={w}{w}^{\dagger}$. Note
$\lambda_{1}(H)=\lambda_{1}({w}{w}^{\dagger})=1$ are simple eigenvalues, and
$\lambda_{j}({w}{w}^{\dagger})=0$ for $j=2,\ldots,n$. From Equation (9), with
$i=1$ and $j=0$, we get

$\lambda_{1}(\gamma H)+\lambda_{n}({w}{w}^{\dagger})=\lambda_{1}(\gamma
H)\leq\lambda_{1}(\gamma H+{w}{w}^{\dagger}).$ (14)

Similarly, from Equation (8), with $i=2$ and $j=1$, we get

$\lambda_{2}(\gamma H+{w}{w}^{\dagger})\leq\lambda_{1}(\gamma
H)+\lambda_{2}({w}{w}^{\dagger})=\lambda_{1}(\gamma H).$ (15)

Both of the inequalities above are strict since $\lambda_{1}(H)$ is simple and
$E_{1}w\neq 0$ implies ${w}{w}^{\dagger}z_{1}\neq 0$ where $z_{1}$ is the
principal eigenvector with ${z_{1}}{z_{1}}^{\dagger}=E_{1}$.

Next, we apply Theorem 4.2 with $i=2$ and $j=0$ in Equation (9), to get

$\lambda_{2}(\gamma H)+\lambda_{n}({w}{w}^{\dagger})=\lambda_{2}(\gamma
H)\leq\lambda_{2}(\gamma H+{w}{w}^{\dagger}).$ (16)

Since $\theta_{2}\in\operatorname{Supp}_{H}(w)$, there exists an eigenvector
$z_{2}$ corresponding to $\lambda_{2}(H)$ so that ${w}{w}^{\dagger}z_{2}\neq
0$. For any nonzero vector $v$ from the subspace $W_{1}\cap W_{2}\cap W_{3}$
(as constructed in the proof of Theorem 4.2), with
$W_{1}=\operatorname{span}\\{{z_{1}},{z_{2}}\\}$, we always have
${w}{w}^{\dagger}z_{2}\neq 0$ and hence the inequality in Equation (16) is
strict. ∎

###  4.2 Cauchy’s Equality

The next formula due to Cauchy can be derived from the determinant of bordered
matrices (see [8]).

###### 4.4 Lemma

(Cauchy) For any $n\times n$ matrix $A$, any vectors $x,y\in\mathbb{C}^{n}$,
we have

$\det(A+xy^{\dagger})=\det(A)+y^{\dagger}\operatorname{Adj}(A)x.$ (17)

Moreover, if $A$ is nonsingular, then

$\det(A+xy^{\dagger})=\det(A)(1+y^{\dagger}A^{-1}x).$ (18)

We apply the above lemma to provide sharper estimates for the case when
$\gamma=S_{1}$ on the locations of the two largest perturbed eigenvalues
relative to the unperturbed principal eigenvalue.

###### 4.5 Proposition

Let $(H,w,S_{1})$ be a tuplet where $\epsilon_{1}=\left\lVert
E_{1}w\right\rVert$. Then

$\epsilon_{1}^{2}\ <\ \zeta_{1}-S_{1}\ \lesssim\ \sqrt{S_{1}}\epsilon_{1}.$
(19)

Moreover, if $\theta_{2}\in\operatorname{Supp}_{H}(w)$, then

$0\ <\ S_{1}-\zeta_{2}\ \lesssim\ \sqrt{S_{1}}\epsilon_{1}.$ (20)

###### Proof.

Let $\tilde{H}=S_{1}H+{w}{w}^{\dagger}$ and $\Delta_{r}=1-\theta_{r}$, for all
$r$. Note that $\phi(\tilde{H},t)=\det((tI-S_{1}H)-{w}{w}^{\dagger})$.
Applying Lemma 4.4 and assuming $m_{r}$ is the multiplicity of $\theta_{r}$,
we get

$\displaystyle\phi(\tilde{H},t)$ $\displaystyle=$ $\displaystyle\det(tI-
S_{1}H)(1-{w^{\dagger}}{(tI-S_{1}H)^{-1}w})$ $\displaystyle=$
$\displaystyle\left(\prod_{r}(t-S_{1}\theta_{r})^{m_{r}}\right)\left(1-\sum_{r}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{(t-S_{1}\theta_{r})}\right).$

The bound $\zeta_{1}-S_{1}>\epsilon_{1}^{2}$ follows by verifying that
$\phi(\tilde{H},S_{1}+\epsilon_{1}^{2})$ is negative. Observe that if
$\phi(\tilde{H},S_{1}+\beta)>0$, then $\zeta_{1}-S_{1}\leq\beta$. We write the
condition $\phi(\tilde{H},S_{1}+\beta)>0$ as

$1\ >\ \sum_{r}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{S_{1}\Delta_{r}+\beta}\ =\
\frac{\epsilon_{1}^{2}}{\beta}+\sum_{r\neq 1}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{S_{1}\Delta_{r}+\beta}.$

Because $\Delta_{r}\leq 1$, for each $r$, it follows that
$(1+\beta/S_{1})^{-1}$ is an upper bound for the sum $\sum_{r\neq
1}\left\lVert E_{r}w\right\rVert^{2}/(S_{1}\Delta_{r}+\beta)$. So, to satisfy
the previous inequality, it suffices to require

$1\ >\ \frac{\epsilon_{1}^{2}}{\beta}+\frac{1}{1+\beta/S_{1}}.$

After straightforward calculations, we obtain
$\beta^{2}-\epsilon_{1}^{2}\beta-S_{1}\epsilon_{1}^{2}>0$. The roots of this
quadratic equation are given by

$\beta_{\pm}=\frac{1}{2}(\epsilon_{1}^{2}\pm\sqrt{\epsilon_{1}^{4}+4S_{1}\epsilon_{1}^{2}}).$

The positive root is given by $\beta_{+}=O_{n}(\sqrt{S_{1}}\epsilon_{1})$,
since $\epsilon_{1}\ll 1$, which proves Equation (19).

We denote $\delta_{-}=\zeta_{2}-S_{1}$. By Lemma 4.3, $|\delta_{-}|>0$. Now,
observe that if $\phi(\tilde{H},S_{1}-\beta)>0$ then $|\delta_{-}|\leq\beta$.
As above, we write the condition $\phi(\tilde{H},S_{1}-\beta)>0$ as

$1\ <\ \sum_{r}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{S_{1}\Delta_{r}-\beta}\ =\
-\frac{\epsilon_{1}^{2}}{\beta}+\sum_{r\neq 1}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{S_{1}\Delta_{r}-\beta}.$

This yields

$\sum_{r\neq 1}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{S_{1}\Delta_{r}}\frac{1}{1-\beta/(S_{1}\Delta_{r})}\
>\ 1+\frac{\epsilon_{1}^{2}}{\beta}.$

As $\Delta_{r}\leq 1$, for $r\geq 2$, we note that $1/(1-\beta/S_{1})$ is an
upper bound for the expression on the left-hand side. Therefore, we may
require instead

$\frac{1}{1-\beta/S_{1}}\ >\ 1+\frac{\epsilon_{1}^{2}}{\beta}$

which simplifies to $\beta^{2}+\epsilon_{1}^{2}\beta-S_{1}\epsilon_{1}^{2}\ >\
0$. The maximum root of the quadratic polynomial is given by

$\beta=\frac{1}{2}(-\epsilon_{1}^{2}+\sqrt{\epsilon_{1}^{4}+4S_{1}\epsilon_{1}^{2}})\
\sim\ \sqrt{S_{1}}\epsilon_{1}$

which proves Equation (20). ∎

##  5 Necessary Gaps

We describe necessary conditions for graphs to be Groverian, but first we
derive some useful preliminary observations. Our analysis borrows heavily
ideas from Chakraborty et al. [4].

Given a tuplet $(H,w,\gamma)$, for each $p$, we have $(\gamma
H+{w}{w}^{\dagger})F_{p}=\zeta_{p}F_{p}$ or

${w}{w}^{\dagger}F_{p}=(\zeta_{p}I-\gamma H)F_{p},$ (21)

which implies

$\left\lVert F_{p}w\right\rVert^{2}w=(\zeta_{p}I-\gamma H)F_{p}w.$ (22)

If $\zeta_{p}\not\in\operatorname{Spec}(\gamma H)$ holds, it clearly
guarantees

$\frac{F_{p}w}{\left\lVert F_{p}w\right\rVert^{2}}=(\zeta_{p}I-\gamma
H)^{-1}w,$ (23)

which further yields

$\frac{1}{\left\lVert F_{p}w\right\rVert^{2}}=\sum_{r}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{(\zeta_{p}-\gamma\theta_{r})^{2}}.$ (24)

Moreover, Equation (23) yields an expression of unity

$1=\sum_{r=1}^{d}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\zeta_{p}-\gamma\theta_{r}}.$ (25)

Returning to Equation (22), after multiplying both sides by $E_{1}$, we derive

$\left\lVert F_{p}w\right\rVert^{2}E_{1}w=(\zeta_{p}-\gamma)E_{1}F_{p}w.$ (26)

By Theorem 4.2, since $\left\lVert E_{1}w\right\rVert\neq 0$, we have strict
interlacing where $\zeta_{2}<\gamma<\zeta_{1}$. Furthermore,
$\gamma\neq\zeta_{r}$, for all $r=1,\ldots,n$. This allows us to write

$E_{1}F_{p}w\ =\ \frac{\left\lVert
F_{p}w\right\rVert^{2}}{\zeta_{p}-\gamma}E_{1}w,\ \ \ \mbox{ $p=1,\ldots,m$.}$
(27)

Now, analyzing the fidelity of of the quantum walk with the Hamiltonian
$\tilde{H}=\gamma H+{w}{w}^{\dagger}$, we get

$f(t)\ =\ \operatorname{Tr}(ww^{\dagger}e^{-it\tilde{H}}E_{1}e^{it\tilde{H}})\
=\ \sum_{p,q}^{n}e^{-it(\zeta_{p}-\zeta_{q})}w^{T}F_{p}E_{1}F_{q}w.$ (28)

Replacing $E_{1}F_{q}w$ using Equation (27), we get instead

$f(t)\ =\ \left\lVert
E_{1}w\right\rVert^{2}\left|\sum_{p}e^{-it\zeta_{p}}\frac{\left\lVert
F_{p}w\right\rVert^{2}}{(\zeta_{p}-\gamma)}\right|^{2}.$ (29)

By triangle inequality, the above becomes

$f(t)\ \leq\ \left\lVert E_{1}w\right\rVert^{2}\left(\sum_{p}\frac{\left\lVert
F_{p}w\right\rVert^{2}}{|\zeta_{p}-\gamma|}\right)^{2}.$ (30)

Finally, at the time of origin $t=0$, we get another expression of unity,

$1\ =\ \left|\frac{\left\lVert
F_{1}w\right\rVert^{2}}{\zeta_{1}-\gamma}-\sum_{p\neq 1}\frac{\left\lVert
F_{p}w\right\rVert^{2}}{\gamma-\zeta_{p}}\right|.$ (31)

Using the above observations, we are ready to show some necessary conditions
for a graph $G$ to be Groverian. In the next theorem, we show some conditions
on $\left\lVert E_{1}w\right\rVert$ in relation to the eigenvalue gaps between
the largest unperturbed eigenvalue of $\gamma H(G)$ and the perturbed
eigenvalues $\zeta_{m}$ of $\gamma H(G)+{w}{w}^{\dagger}$. In particular, for
a graph $G$ to be Groverian, $\left\lVert E_{1}w\right\rVert$ must be
asymptotically equal to the first gap $\delta_{+}:=\zeta_{1}-\gamma$, it must
be asymptotically greater or equal to the second gap
$\delta_{-}:=\gamma-\zeta_{2}$, and it must be asymptotically equal to some
gap $\gamma-\zeta_{m}$, for some $m\geq 2$, but not necessarily the second
gap. Recall that by strict interlacing, we know that
$\gamma\theta_{2}<\zeta_{2}<\gamma<\zeta_{1}$, where $\theta_{2}$ is the
second largest eigenvalue of $H(G)$.

###### 5.1 Theorem

For a tuplet $(H,w,\gamma)$, suppose one of the following conditions hold:

  1. (i)

$\left\lVert E_{1}w\right\rVert\not\asymp\zeta_{1}-\gamma$, or

  2. (ii)

$\left\lVert E_{1}w\right\rVert\ll\gamma-\zeta_{2}$, or

  3. (iii)

$\gamma-\zeta_{m-1}\ll\left\lVert E_{1}w\right\rVert\ll\gamma-\zeta_{m}$, for
some $m\geq 3$,

Then, $H$ is not $\gamma$-Groverian.

###### Proof.

We treat each condition as a separate case.

Case (i): Assume that $\delta_{+}:=\zeta_{1}-\gamma\not\asymp\epsilon_{1}$.
From Equation (30), we apply Equation (31) to obtain the following upper bound

$f(t)\leq\left\lVert E_{1}w\right\rVert^{2}\left(\frac{2\left\lVert
F_{1}w\right\rVert^{2}}{\delta_{+}}-1\right)^{2},$ (32)

which shows that fidelity goes to zero if $\epsilon_{1}\ll\delta_{+}$. For the
opposite direction, apply Equation (24) with $p=1$ to get

$\frac{1}{\left\lVert F_{1}w\right\rVert^{2}}\ =\
\sum_{r=1}^{d}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{(\zeta_{1}-\gamma\theta_{r})^{2}}.$

But, the sum is bounded from below by its first term, and so $\left\lVert
F_{1}w\right\rVert^{2}\leq\delta_{+}^{2}/\left\lVert E_{1}w\right\rVert^{2}$.
Returning to Equation (32) and using the preceding upper bound,

$f(t)\leq\left(\frac{2\delta_{+}}{\left\lVert E_{1}w\right\rVert}-\left\lVert
E_{1}w\right\rVert\right)^{2},$ (33)

which shows that fidelity goes to zero if $\delta_{+}\ll\left\lVert
E_{1}w\right\rVert$.

Case (ii): Let $\delta_{-}:=\zeta_{2}-\gamma$. We start with Equation (30) and
use Equation (31) to rewrite a term in the upper bound as

$\sum_{p}\frac{\left\lVert
F_{p}w\right\rVert^{2}}{|\gamma-\zeta_{p}|}-1=2\left(\frac{\left\lVert
F_{2}w\right\rVert^{2}}{|\delta_{-}|}+\sum_{p\geq 3}\frac{\left\lVert
F_{p}w\right\rVert^{2}}{\gamma-\zeta_{p}}\right).$ (34)

Since $|\delta_{-}|\leq\gamma-\zeta_{p}$ for each $p\geq 2$, we derive an
upper bound on the fidelity,

$f(t)\leq\left(\frac{2\left\lVert
E_{1}w\right\rVert}{|\delta_{-}|}(1-\left\lVert
F_{1}w\right\rVert^{2})+\left\lVert E_{1}w\right\rVert\right)^{2},$ (35)

which shows that fidelity tends to zero if $\left\lVert
E_{1}w\right\rVert\ll|\delta_{-}|$.

Case (iii): Starting with Equation (21), after multiplying by $E_{1}$, we
derive

$E_{1}{w}{w}^{\dagger}F_{p}=(\zeta_{p}-\gamma)E_{1}F_{p}.$

Taking a product with itself but for index $q$, we get

$\left\lVert
E_{1}w\right\rVert^{2}F_{p}{w}{w}^{\dagger}F_{q}=(\zeta_{p}-\gamma)(\zeta_{q}-\gamma)F_{p}E_{1}F_{q}.$

Upon taking the trace, this yields

$\left\lVert E_{1}w\right\rVert^{2}\left\lVert
F_{p}w\right\rVert^{2}=(\zeta_{p}-\gamma)^{2}\langle F_{p},E_{1}\rangle.$ (36)

By Equation (28), we have

$\sum_{p,q}e^{-it(\zeta_{p}-\zeta_{q})}w^{\dagger}F_{p}E_{1}F_{q}w=\sum_{p,q}e^{-it(\zeta_{p}-\zeta_{q})}\frac{\left\lVert
E_{1}w\right\rVert}{\zeta_{p}-\gamma}\frac{\left\lVert
E_{1}w\right\rVert}{\zeta_{q}-\gamma}\left\lVert
F_{p}w\right\rVert^{2}\left\lVert F_{q}w\right\rVert^{2},$

where we have used Equation (27) twice (for both $p$ and $q$). Now, note we
may apply Equation (36) to “flip” one of the ratios as follows:

$\sum_{p,q}e^{-it(\zeta_{p}-\zeta_{q})}\frac{\left\lVert
E_{1}w\right\rVert}{\zeta_{p}-\gamma}\frac{\zeta_{q}-\gamma}{\left\lVert
E_{1}w\right\rVert}\left\lVert F_{p}w\right\rVert^{2}\langle
F_{q},E_{1}\rangle.$

This allows us to partition the sums around $m$ based on whether
$\epsilon_{1}\ll\zeta_{p}-\gamma$ or $\epsilon_{1}\gg\zeta_{p}-\gamma$. In all
cases, the corresponding terms tend to $0$ as $n\rightarrow\infty$. ∎

###  5.1 Failure around $S_{1}$

We describe necessary conditions on $\gamma$ relative to $S_{1}$. First, we
show failure whenever $\gamma$ is too large relative to $S_{1}$.

###### 5.2 Theorem

For a tuplet $(H,w,\gamma)$, if $\left\lVert E_{1}w\right\rVert
S_{1}\ll\gamma-S_{1}$, then $H$ is not $\gamma$-Groverian.

###### Proof.

Starting with Equation (25) with $p=1$, we see

$1\ =\ \sum_{r=1}^{n}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\zeta_{1}-\gamma\theta_{r}}\ =\ \frac{\left\lVert
E_{1}w\right\rVert^{2}}{\delta_{+}}+\sum_{r=2}^{n}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\gamma(1-\theta_{r})+\delta_{+}}\ \leq\
\frac{\left\lVert E_{1}w\right\rVert^{2}}{\delta_{+}}+\frac{S_{1}}{\gamma}.$

After minor rearrangements, we obtain

$\delta_{+}\ \leq\ \left\lVert E_{1}w\right\rVert^{2}\frac{\gamma}{\gamma-
S_{1}}\ =\ \left\lVert E_{1}w\right\rVert^{2}\left(1+\frac{S_{1}}{\gamma-
S_{1}}\right)\ \ll\ \left\lVert E_{1}w\right\rVert(1+o_{n}(1))$ (37)

which proves the claim by appealing to Theorem 5.1, case (i). ∎

Next, we show failure conditions when $\gamma$ is centered around $S_{1}$. We
will use this later to show that cycles are not Groverian.

###### 5.3 Theorem

Let $(H,w,\gamma)$ be a tuplet where $\left\lVert
E_{r}w\right\rVert^{2}=O_{n}(\left\lVert E_{1}w\right\rVert^{2})$ for all
$r\geq 2$. Let

$I_{\alpha}=\\{r\geq 2:\gamma<\left\lVert
E_{1}w\right\rVert^{\alpha}(1-\theta_{r})^{-1}\\}.$

If $\gamma=S_{1}(1+o_{n}(1))$ and $|I_{\alpha}|\geq 3$, for some
$\alpha\in(1,2)$, then $H$ is not $\gamma$-Groverian.

###### Proof.

Let $\epsilon_{1}=\left\lVert E_{1}w\right\rVert$. By Theorem 5.1, it suffices
to show $\delta_{+}\ll\epsilon_{1}$, where $\delta_{+}=\zeta_{1}-\gamma$. Let
$\Delta_{r}=1-\theta_{r}$. Our plan is to prove
$\delta_{+}=O_{n}(\epsilon_{1}^{\alpha})$ for the given $\alpha\in(1,2)$. By
Lemma 4.4, it is enough to show $\phi(H,\gamma+\epsilon_{1}^{\alpha})>0$ or
equivalently

$1\ >\ \sum_{r=1}^{d}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\gamma\Delta_{r}+\epsilon_{1}^{\alpha}}\ =\
\epsilon_{1}^{2-\alpha}+\frac{1}{\gamma}\sum_{r\geq 2}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}+(\epsilon_{1}^{\alpha}/\gamma)}.$

Let us focus on the last summation. After splitting the summation into two
parts, we may bound each part from above as follows,

$\sum_{r\geq 2}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}+(\epsilon_{1}^{\alpha}/\gamma)}\leq\sum_{\begin{subarray}{c}r\geq
2:\\\ \Delta_{r}<\epsilon_{1}^{\alpha}/\gamma\end{subarray}}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{2\Delta_{r}}+\sum_{\begin{subarray}{c}r\geq 2:\\\
\Delta_{r}\geq\epsilon_{1}^{\alpha}/\gamma\end{subarray}}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}}.$

So, to prove the claim, it suffices to show that

$1\ >\ \epsilon_{1}^{2-\alpha}+\frac{1}{\gamma}\sum_{r\geq 2}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}}-\frac{1}{2\gamma}\sum_{\begin{subarray}{c}r\geq
2:\\\ \Delta_{r}<\epsilon_{1}^{\alpha}/\gamma\end{subarray}}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}}.$ (38)

Assume $\gamma=S_{1}+\beta$ for some $\beta=o_{n}(S_{1})$. Then,

$1\ >\
\epsilon_{1}^{2-\alpha}+\frac{1}{1+(\beta/S_{1})}\left(\frac{1}{S_{1}}\sum_{r\geq
2}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}}\right)-\frac{1}{2\gamma}\sum_{\begin{subarray}{c}r\geq
2:\\\ \gamma<\epsilon_{1}^{\alpha}/\Delta_{r}\end{subarray}}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}}$ (39)

which implies

$1+o_{n}(1)\ \leq\ \frac{1}{2\gamma}\sum_{\begin{subarray}{c}r\geq 2:\\\
\gamma<\epsilon_{1}^{\alpha}/\Delta_{r}\end{subarray}}\frac{\epsilon_{1}^{\alpha}}{\Delta_{r}}.$
(40)

Now, the claim follows as $|I_{\alpha}|\geq 3$. ∎

###  5.2 Perfect Fidelity

When the fidelity is perfect, we show that the principal perturbed eigenspace
must have a significant overlap with the subspace spanned by the principal
eigenspace and the target state.

###### 5.4 Theorem

Let $(H,w,\gamma)$ be a tuplet. If $H$ is perfectly $\gamma$-Groverian, then
the principal eigenvector of $\gamma H+{w}{w}^{\dagger}$ is an equal
superposition of $w$ and the principal eigenvector of $H$, up to $o_{n}(1)$
terms.

###### Proof.

Let $z_{1}$ and $y_{1}$ be the principal eigenvectors of $H$ and $\gamma
H+{w}{w}^{\dagger}$, respectively. Starting with Equation (32) and then
applying Equation (27) with $p=1$, we get

$f(t)\ \leq\ 4\frac{\left\lVert
F_{1}w\right\rVert^{4}}{\delta_{+}^{2}}\left\lVert E_{1}w\right\rVert^{2}\ =\
4\left\lVert E_{1}F_{1}w\right\rVert^{2}\ =\ 4|\langle
y_{1},z_{1}\rangle|^{2}|\langle y_{1},w\rangle|^{2}.$

If $f(t)=1-o_{n}(1)$, we obtain $1-o_{n}(1)\leq 2|\langle
y_{1},z_{1}\rangle||\langle y_{1},w\rangle|$. Since $|\langle
y_{1},z_{1}\rangle|^{2}+|\langle y_{1},w\rangle|^{2}\leq 1+o_{n}(1)$, we have
$0\leq(|\langle y_{1},z_{1}\rangle|-|\langle y_{1},w\rangle|)^{2}=o_{n}(1)$,
which proves the claim. ∎

##  6 Sufficient Gap

In this section, we prove our optimal characterization of $S_{1}$-Groverian
graphs under a simpler assumption. First, we justify that the choice of
$\gamma=S_{1}$ is almost best possible. By Equation (25) with $p=1$, we have

$1=\frac{\left\lVert E_{1}w\right\rVert^{2}}{\delta_{+}}+\sum_{r\neq
1}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\delta_{+}+\gamma\Delta_{r}}=\left\lVert
E_{1}w\right\rVert+\sum_{r\neq 1}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\delta_{+}+\gamma\Delta_{r}}$

as $\left\lVert E_{1}w\right\rVert\asymp\delta_{+}$ is a necessary condition
due to Theorem 5.1$(i)$. Therefore,

$1-\left\lVert E_{1}w\right\rVert\asymp\frac{1}{\gamma}\sum_{r\neq
1}\frac{\left\lVert E_{r}w\right\rVert^{2}}{\Delta_{r}}\frac{1}{1+(\left\lVert
E_{1}w\right\rVert/\gamma\Delta_{r})}.$

If $\gamma\gtrsim\sqrt{S_{1}}$, since $\left\lVert
E_{1}w\right\rVert\ll\sqrt{S_{1}}\Delta_{2}$, we have $\left\lVert
E_{1}w\right\rVert/\gamma\Delta_{r}=o_{n}(1)$. This shows

$\gamma(1-\left\lVert E_{1}w\right\rVert)\asymp\sum_{r\neq 1}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}}\frac{1}{1+(\left\lVert
E_{1}w\right\rVert/\gamma\Delta_{r})}=S_{1}(1+o_{n}(1)).$

As $\left\lVert E_{1}w\right\rVert=o_{n}(1)$, we have $\gamma\asymp S_{1}$.

The next theorem is our main characterization for optimal spatial search for
$\gamma=S_{1}$.

###### 6.1 Theorem

Let $(H,w,\gamma)$ be a tuplet where
$\theta_{2}\in\operatorname{Supp}_{H}(w)$. If $\left\lVert
E_{1}w\right\rVert\ll\sqrt{S_{1}}\Delta_{2}$, then $H$ is $S_{1}$-Groverian if
and only if $S_{2}/S_{1}^{2}\asymp 1$.

###### Proof.

For the sake of brevity, let $\epsilon_{1}=\left\lVert E_{1}w\right\rVert$. By
Lemma 4.3, we know that $\zeta_{1}$ and $\zeta_{2}$ are simple and
$\zeta_{1},\zeta_{2}\not\in\operatorname{Spec}(S_{1}H)$. Therefore, let
$y_{1}$ and $y_{2}$ be their corresponding eigenvectors. Define
$\delta_{+}=\zeta_{1}-S_{1}$ and $\delta_{-}=\zeta_{2}-S_{1}$. Also, let
$\Delta_{r}=1-\theta_{r}$. Using Equation (25) with $p=1,2$, we derive

$1\ =\ \sum_{r=1}^{d}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\zeta_{p}-S_{1}\theta_{r}}\ =\
\frac{\epsilon_{1}^{2}}{\delta_{\pm}}+\sum_{r=2}^{d}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{S_{1}\Delta_{r}}\frac{1}{1+\delta_{\pm}/(S_{1}\Delta_{r})}.$
(41)

Note $(1+\alpha)^{-1}=1-\alpha+\alpha^{2}(1+\alpha)^{-1}$ holds for all
$\alpha\neq-1$. Using $\alpha=\delta_{\pm}/(S_{1}\Delta_{r})$, after
reorganizing and cancelling terms, we arrive at

$\frac{\epsilon_{1}^{2}}{\delta_{\pm}^{2}}\ =\
\frac{1}{S_{1}^{2}}\sum_{r=2}^{d}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}^{2}}\frac{S_{1}\Delta_{r}}{\delta_{\pm}+S_{1}\Delta_{r}}.$
(42)

###### 6.2 Lemma

$\epsilon_{1}^{2}/\delta_{\pm}^{2}\sim S_{2}/S_{1}^{2}$.

###### Proof.

Proposition 4.5 shows that $|\delta_{\pm}|=O_{n}(\sqrt{S_{1}}\epsilon_{1})$,
and as $\epsilon_{1}\ll\sqrt{S_{1}}\Delta_{2}$, we get $|\delta_{\pm}|\ll
S_{1}\Delta_{2}$. Applying this to Equation (42) proves the claim. ∎

###### 6.3 Lemma

$2\epsilon_{1}^{2}/\delta_{+}^{2}\sim 1/\left\lVert F_{1}w\right\rVert^{2}$
and $2\epsilon_{1}^{2}/\delta_{-}^{2}\sim 1/\left\lVert
F_{2}w\right\rVert^{2}$.

###### Proof.

We apply Equation (24) to $\zeta_{1}$ and $\zeta_{2}$, and after some
rearrangements, we get

$\frac{1}{\left\lVert
F_{p}w\right\rVert^{2}}=\frac{\epsilon_{1}^{2}}{\delta_{\pm}^{2}}+\frac{1}{S_{1}^{2}}\sum_{r=2}^{d}\frac{\left\lVert
E_{r}w\right\rVert^{2}}{\Delta_{r}^{2}}\frac{1}{(1+\delta_{\pm}/(S_{1}\Delta_{r}))^{2}}\
\ \ \mbox{ ($p=1,2$).}$ (43)

Proposition 4.5 shows that $|\delta_{\pm}|=O_{n}(\sqrt{S_{1}}\epsilon_{1})$,
which combined with the assumption $\epsilon_{1}\ll\sqrt{S_{1}}\Delta_{2}$
yields $|\delta_{\pm}|\ll S_{1}\Delta_{2}$. Applying this to Equation (43), we
obtain

$\frac{1}{\left\lVert F_{p}w\right\rVert^{2}}\ =\
\frac{\epsilon_{1}^{2}}{\delta_{\pm}^{2}}+\frac{S_{2}}{S_{1}^{2}}(1+o_{n}(1))\
\sim\ \frac{2\epsilon_{1}^{2}}{\delta_{\pm}^{2}}\ \ \ \mbox{ ($p=1,2$),}$ (44)

as $\epsilon_{1}^{2}/\delta_{\pm}^{2}\sim S_{2}/S_{1}^{2}$ by Lemma 6.2. ∎

###### 6.4 Lemma

If $t=O_{n}(\sqrt{S_{2}}/S_{1}\epsilon_{1})$, then
$f(t)=\Omega_{n}(S_{1}/\sqrt{S_{2}})$.

###### Proof.

By Equation (26), we have $E_{1}F_{p}w=\left\lVert
F_{p}w\right\rVert^{2}E_{1}w/(\zeta_{p}-S_{1})$. For $p=1,2$, using Lemma 6.3
to replace $\left\lVert F_{p}w\right\rVert^{2}$, we obtain

$\left\lVert E_{1}F_{p}w\right\rVert=\left\lVert
F_{p}w\right\rVert^{2}\frac{\left\lVert
E_{1}w\right\rVert}{|\delta_{\pm}|}\sim\frac{|\delta_{\pm}|}{2\epsilon_{1}}.$
(45)

Let $\delta=(\zeta_{1}-\zeta_{2})/2$. Then, the fidelity is given by

$\displaystyle f(t)$ $\displaystyle=$
$\displaystyle\operatorname{Tr}({w}{w}^{\dagger}\sum_{p,q}e^{-it(\zeta_{p}-\zeta_{q})}F_{p}E_{1}F_{q})$
$\displaystyle=$ $\displaystyle\sum_{p,q}e^{-it(\zeta_{p}-\zeta_{q})}\langle
E_{1}F_{p}w,E_{1}F_{q}w\rangle$ $\displaystyle=$
$\displaystyle\sum_{p,q}e^{-it(\zeta_{p}-\zeta_{q})}\left\lVert
E_{1}w\right\rVert^{2}\frac{\left\lVert
F_{p}w\right\rVert^{2}}{\zeta_{p}-S_{1}}\frac{\left\lVert
F_{q}w\right\rVert^{2}}{\zeta_{q}-S_{1}}$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1-\cos(2\delta
t))\frac{\delta^{2}}{\epsilon_{1}^{2}}+\epsilon_{1}^{2}\sum_{p,q\neq
1,2}e^{-it(\zeta_{p}-\zeta_{q})}\frac{\left\lVert
F_{p}w\right\rVert^{2}}{S_{1}-\zeta_{p}}\frac{\left\lVert
F_{q}w\right\rVert^{2}}{S_{1}-\zeta_{q}}$ $\displaystyle\geq$
$\displaystyle\frac{\delta^{2}}{\epsilon_{1}^{2}},\ \ \ \mbox{ by setting
$t=\frac{\pi}{2}\delta^{-1}$.}$

Now, note that
$\delta=\frac{1}{2}(\delta_{+}+|\delta_{-}|)\asymp\epsilon_{1}$. ∎

We have shown that if $S_{1}^{2}/S_{2}=\Theta_{n}(1)$ then $H$ is
$S_{1}$-Groverian. It remains to show the converse.

###### 6.5 Lemma

If $f(t)=\Omega_{n}(1)$, for some $t=O_{n}(1/\epsilon_{1})$, then
$S_{2}/S_{1}^{2}=\Theta_{n}(1)$.

###### Proof.

We prove the contrapositive. If $S_{2}/S_{1}^{2}\not\asymp 1$, or
equivalently, $\epsilon_{1}^{2}\not\asymp\delta_{+}^{2}$ by Lemma 6.2, then
$H$ is not Groverian by Theorem 5.1$(i)$. Note
$\epsilon_{1}^{2}\asymp\delta_{+}^{2}$ if and only if
$\epsilon_{1}\asymp\delta_{+}$. ∎

Lemma 6.4 and 6.5 completes the proof of the theorem. ∎

Remarks. We now compare Theorem 6.1 in the context of the known results in [3,
4]. Notice that Theorem 6.1 implies the main result (Lemma 1) in Chakraborty
et al. [3]. Their result requires the constant gap condition
$\Delta_{2}=\Omega_{n}(1)$ which is a stronger assumption because of the
following observation. In what follows, we denote $\epsilon_{1}=\left\lVert
E_{1}w\right\rVert$ and $\epsilon_{2}=\left\lVert E_{2}w\right\rVert$.

###### 6.6 Fact

Suppose $\epsilon_{1}=o_{n}(1)$. If $\Delta_{2}=\Omega_{n}(1)$, then
$S_{1}\Delta_{2}=\Theta_{n}(1)$.

###### Proof.

Note $\epsilon_{2}^{2}+\Delta_{2}(1-\epsilon_{1}^{2}-\epsilon_{2}^{2})\leq
S_{1}\Delta_{2}\leq 1-\epsilon_{1}^{2}$. The upper bound
$S_{1}\Delta_{2}=O_{n}(1)$ holds immediately. If $\epsilon_{2}=o_{n}(1)$, then
$S_{1}\Delta_{2}=\Omega_{n}(1)$ follows as $\Delta_{2}=\Omega_{n}(1)$.
Otherwise, $S_{1}\Delta_{2}=\Omega_{n}(1)$ holds from
$\epsilon_{2}=\Omega_{n}(1)$. ∎

We also note the following relation between $S_{1}$ and $S_{2}$.

###### 6.7 Fact

$S_{1}^{2}/S_{2}\leq 1-\epsilon_{1}^{2}$.

###### Proof.

Consider a random variable $Z$ where $Z=1/\Delta_{r}$ with probability
$\epsilon_{r}^{2}/(1-\epsilon_{1}^{2})$, for $r=2,\ldots,d$. Then,
$\mathbb{E}[Z]=S_{1}/(1-\epsilon_{1}^{2})$ and
$\mathbb{E}[Z^{2}]=S_{2}/(1-\epsilon_{1}^{2})$. Now,
$\mathbb{E}[Z^{2}]\geq\mathbb{E}[Z]^{2}$ since variance is always nonnegative.
∎

Next, observe that $S_{1}\geq 1-\epsilon_{1}^{2}$. If $S_{1}\leq 1$, then both
$S_{1}$ and $\sqrt{S_{1}}$ are constant; otherwise, $\sqrt{S_{1}}\leq S_{1}$.
To summarize, it is clear that $\sqrt{S_{1}}\lesssim
S_{1}\lesssim\sqrt{S_{2}}$.

As for the main result in Chakraborty et al. [4], their theorem requires the
assumption $\epsilon_{1}\ll S_{1}S_{2}/S_{3}$ and
$\epsilon_{1}\ll\sqrt{S_{2}}\Delta_{2}$. In Theorem 6.1, we replace these two
assumptions with a single assumption $\epsilon_{1}\ll\sqrt{S_{1}}\Delta_{2}$.
The latter assumption is only slightly stronger than
$\epsilon_{1}\ll\sqrt{S_{2}}\Delta_{2}$ since under the regime of interest,
namely, $S_{2}/S_{1}^{2}=\Theta_{n}(1)$, they are asymptotically equivalent.

##  7 Examples

We analyze some examples of well-known families of graphs (see Figure 2). In
order to simplify the calculations, we normalize the matrices as
$H/\left\lVert H\right\rVert$ which places the eigenvalues in $[-1,1]$
(instead of $[0,1]$). Since the two normalizations are equal up to a factor of
$2$, this will not affect our asymptotic conclusions. As before, we denote
$\epsilon_{1}=\left\lVert E_{1}w\right\rVert$, where $E_{1}$ is the orthogonal
projection onto the principal eigenspace of $H$ and $w$ is the target vertex.

Graph Family | Groverian? | $\epsilon_{1}$ | $\Delta_{2}$ | $S_{1}$ | Comment
---|---|---|---|---|---
Clique $K_{n}$ | Yes | $n^{-1/2}$ | 1 | 1 | $\Delta_{2}=1$
Expander | Yes | $n^{-1/2}$ | 1 | - | $\Delta_{2}=1$
Strongly Regular Graph | Yes | $n^{-1/2}$ | 1 | - | $\Delta_{2}=1$
Hamming $H(n,q)$ | Yes | $q^{-n/2}$ | $1/n$ | 1 | $\epsilon_{1}\ll\sqrt{S_{1}}\Delta_{2}$
Johnson $J(n,k)$ | Yes | $n^{-k/2}$ | $1/k$ | 1 | $\Delta_{2}=1$
Grassmann $G_{q}(n,k)$ | Yes | $q^{-{k(n-k)/2}}$ | $1-1/q$ | - | $\Delta_{2}=1$
Distance Regular Graph with |  |  |  |  |
classical parameters $(d,q,\alpha,\beta)$ | Yes | $1/\sqrt{|V(G)|}$ | $1-1/q+\alpha/q\beta$ | - | $\Delta_{2}=1$
Cycle $C_{n}$ | No | $n^{-1/2}$ | $n^{-2}$ | $n$ | $\epsilon_{1}\not\ll\sqrt{S_{1}}\Delta_{2}$
Figure 2: Examples of graph families and $S_{1}$-Groverian (or optimal spatial
search) properties. Assume $q,k,d$ are constants and $\alpha\ll\beta$. The
expressions involving $\epsilon_{1}$, $\Delta_{2}$, and $S_{1}$ are asymptotic
in nature. Some entries are missing as they do not impact the property.

#### Cliques

The normalized eigenvalues of $K_{n}$ are $1$ (with multiplicity $1$) and
$-1/(n-1)$ (with multiplicity $n-1$). So, cliques are Groverian (in fact,
perfectly) since $\Delta_{2}$ is constant. This was, of course, the original
observation of Farhi and Gutmann [6].

#### Expanders

A graph $G=(V,E)$ is called an $(n,d,c)$-expander if $G$ has $n$ vertices,
maximum degree $d$, and for each set of vertices $W$ of size $|W|\leq n/2$, we
have $|N(W)|\geq c|W|$, where $N(W)$ is the set of vertices not in $W$ but is
adjacent to some vertex in $W$. Here, $c$ is called the expansion which is
required to be constant. It is known that if $G$ is $d$-regular on $n$
vertices, then it is a $(n,d,\Delta_{2}/2)$-expander provided
$\Delta_{2}=\Theta_{n}(1)$ (see [2]). So, expanders are Groverian since
$\Delta_{2}$ is constant. This is the main observation of Chakraborty et al.
[3].

#### Strongly Regular Graphs

A graph $G_{n}$ is called strongly regular with parameter $(n,k,a,c)$ if it is
a $k$-regular on $n$ vertices where every pair of adjacent vertices have $a$
common neighbors and every pair of non-adjacent vertices have $c$ common
neighbors. Let $\theta_{1}>\theta_{2}$ be the non-principal eigenvalues. Then,
$k-c=\theta_{1}(-\theta_{2})$, which implies $\theta_{1}=(k-c)/(-\theta_{2})$.
If $G_{n}$ is primitive but not a conference graph, then $-\theta_{2}\geq 2$.
Therefore, $\theta_{1}\leq(k-c)/2<k/2$. This shows that $\Delta_{2}$ is
constant. On the other hand, if $G_{n}$ is a conference graph then $k=(n-1)/2$
and $\theta_{1}=(\sqrt{n}-1)/2$ which implies $\Delta_{2}=1-o_{n}(1)$. Thus,
strongly regular graphs are Groverian. This provides an alternative proof of
the result due to Janmark et al. [9].

#### Hamming graphs

The Hamming graph $H(n,q)$, with $q$ is constant, has
$(\mathbb{Z}/q\mathbb{Z})^{n}$ as its vertices where two $n$-tuples are
connected if they differ in exactly one dimension. As $H(n,q)$ has $q^{n}$
vertices with eigenvalues $\theta_{r}=n(q-1)-qr$ with multiplicity
$m_{r}=\binom{n}{r}(q-1)^{r}$, for $r=0,\ldots,n$, we have
$\Delta_{2}=qn/(q-1)\sim 1/n$ and $\epsilon_{1}=1/q^{n/2}$. Since
$S_{1}=\Theta_{n}(1)$, the Hamming graph $H(n,q)$ is Groverian as
$\epsilon_{1}\ll\sqrt{S_{1}}\Delta_{2}$. To see why $S_{1}=\Theta_{n}(1)$,
notice that

$S_{1}=\frac{1}{q^{n}}\sum_{r=0}^{n}\binom{n}{r}\frac{n(q-1)}{rq}(q-1)^{r}\sim\frac{1}{q^{n}}\sum_{r}\binom{n+1}{r+1}(q-1)^{r}\asymp
1.$

For the $n$-cube or $H(n,2)$, this was observed by Childs and Goldstone [5].

#### Johnson graphs

The Johnson graph $J(n,k)$ has as its vertices the set of $k$-subsets of
$\\{1,\ldots,n\\}$, denoted $\binom{[n]}{k}$, where two $k$-subsets $A$ and
$B$ are connected if $|A\cap B|=k-1$. So, $J(n,k)$ has $\binom{n}{k}$ vertices
with eigenvalues $\theta_{r}=(k-r)(n-k-r)-r$ with multiplicity
$m_{r}=\binom{n}{r}-\binom{n}{r-1}$, for $r=0,\ldots,k$. Notice
$\epsilon_{1}=1/\sqrt{\binom{n}{k}}\sim n^{-k/2}$ and

$\Delta_{2}=\frac{\theta_{0}-\theta_{1}}{\theta_{0}-\theta_{k}}=\frac{n}{k(n-k+1)}\sim\frac{1}{k}$

which is constant if $k$ is. As $\Delta_{2}=\Omega_{n}(1)$, this shows that
$J(n,k)$, for $k\geq 3$, is Groverian. This recovers the results of Wong [17]
and Tanaka et al. [15].

Figure 3: Some distance-regular graphs that are Groverian: Hamming graphs
$H(n,q)$ and Grassmann graphs $G_{q}(n,k)$, where $q$ and $k$ are constants.
Left: Hamming graph $H(3,3)$. Right: Grassmann graph $G_{2}(4,2)$.

#### Grassmann graphs

The Grassmann graph $G_{q}(n,k)$ has as its vertices the set of $k$-subspaces
of the vector space $\mathbb{F}_{q}^{n}$ where two $k$-subspaces $A$ and $B$
are connected if $\dim(A\cap B)=k-1$. We assume $n\geq 2k$. The number of
vertices of $G_{q}(n,k)$ is

$N=\mbox{$\begin{bmatrix}{n}\\\ {k}\end{bmatrix}_{q}$}\sim q^{k(n-k)}.$

The eigenvalues are given by

$\theta_{r}=q^{r+1}\mbox{$\begin{bmatrix}{k-r}\\\
{1}\end{bmatrix}_{q}$}\mbox{$\begin{bmatrix}{n-k-r}\\\
{1}\end{bmatrix}_{q}$}-\mbox{$\begin{bmatrix}{r}\\\ {1}\end{bmatrix}_{q}$}\sim
q^{n-r-1}$

with multiplicity

$m_{r}=\mbox{$\begin{bmatrix}{n}\\\
{r}\end{bmatrix}_{q}$}-\mbox{$\begin{bmatrix}{n}\\\ {r-1}\end{bmatrix}_{q}$},$

for $r=0,\ldots,k$. Notice $\epsilon_{1}=1/\sqrt{N}$ and the normalized
eigenvalue gap is

$\Delta_{2}=1-\frac{\theta_{1}}{\theta_{0}}\sim 1-\frac{1}{q},$

which is constant if $q$ is. As $\Delta_{2}=\Omega_{n}(1)$, this shows that
$G_{q}(n,k)$, for $k\geq 3$, is Groverian.

#### Distance-regular graphs with classical parameters

The eigenvalues of distance-regular graphs with classical parameters
$(d,q,\alpha,\beta)$ are given in Jurišić and Vidali [11] (see Lemma 2). In
particular, $\theta_{0}=[d]_{q}\beta$ and
$\theta_{1}=[d-1]_{q}(\beta-\alpha)-1$, which implies

$\Delta_{2}=1-\frac{[d-1]_{q}(\beta-\alpha)-1}{[d]_{q}\beta}\sim
1-\frac{1}{q}+\frac{1}{q}\frac{\alpha}{\beta}$

is constant provided $\alpha\ll\beta$.

#### Cycles

The results from Section 5 can be used to prove that cycles are not Groverian.
The normalized eigenvalues of $C_{n}$ are given by
$\theta_{r}=\frac{1}{2}(1+\cos(2\pi(r-1)/n))$, $r=1,\ldots,n$. Using
$\cos(x)\sim 1-x^{2}/2$, we have $\Delta_{r}\sim r^{2}/n^{2}$, for small
positive values of $r$. Since $C_{n}$ is a circulant, $\epsilon_{r}\sim
1/\sqrt{n}$ for all $r=1,\ldots,n$. Note that

$S_{1}=\frac{1}{n}\sum_{r=1}^{n-1}\frac{1}{1-\cos(2\pi r/n)}\sim
2\int_{2\pi/n}^{\pi-2\pi/n}\frac{dx}{1-\cos(x)}=2\cot(\pi/n)=\Theta_{n}(n).$

Next, we show spatial search fails as $\gamma$ ranges over all values.

Case (i). $\gamma=S_{1}+\omega_{n}(\sqrt{n})$: Notice Theorem 5.2 applies
since $\sqrt{n}=\epsilon_{1}S_{1}\ll\gamma-S_{1}=\omega_{n}(\sqrt{n})$.

Case (ii). $\gamma=S_{1}\pm o_{n}(n)$: Here, Theorem 5.3 applies since
$\epsilon_{1}^{\alpha}/\Delta_{r}>S_{1}+\beta$ holds, for $\alpha\in(1,2)$.
With $|\beta|=o_{n}(n)$, evidently $n^{-\alpha/2}\times n^{2}\ \gg\ cn\pm
o_{n}(n)$.

Case (iii). $\gamma=O_{n}(\sqrt{n})$: To apply Theorem 5.3, we rewrite
Equation (38) as

$\frac{1}{2}\sum_{\begin{subarray}{c}r\geq 2:\\\
\Delta_{r}<\epsilon_{1}^{\alpha}/\gamma\end{subarray}}\frac{\epsilon_{r}^{2}}{\Delta_{r}}\
>\ \gamma\epsilon_{1}^{2-\alpha}+S_{1}-\gamma,$ (46)

since $\gamma>0$. Because $\gamma=O_{n}(\sqrt{n})$, $S_{1}=O_{n}(n)$, and
$\epsilon_{1}=1/\sqrt{n}$, the right-hand side is at most $O_{n}(n)$. Next, we
determine the set of indices $r$ so that
$\Delta_{r}<\epsilon_{1}^{\alpha}/\gamma$ which are included in the summation.
The smallest the upper bound $\epsilon_{1}^{\alpha}/\gamma$ can be is
$1/n^{1/2+\alpha/2}$. We have

$\Delta_{r}\sim\frac{r^{2}}{n^{2}}\ll\frac{1}{n^{1/2+\alpha/2}},\ \ \ \mbox{
for $r=O_{n}(1)$.}$

Thus, if we restrict the indices for which $r\leq B$, for a large enough
constant $B$, we get

$\sum_{\begin{subarray}{c}r\geq 2:\\\
\Delta_{r}<\epsilon_{1}^{\alpha}/\gamma\end{subarray}}\frac{\epsilon_{r}^{2}}{\Delta_{r}}\
\geq\ \sum_{r=2}^{B}\frac{\epsilon_{r}^{2}}{\Delta_{r}}\ \sim\
\sum_{r=2}^{B}\frac{n^{-1}}{r^{2}n^{-2}}\ \gtrsim\ \frac{n}{B}\ =\
\Omega_{n}(n).$

Thus, Equation (46) is satisfied provided $B$ is large enough; whence spatial
search fails.

Figure 4: Sparsity is not a good indicator: for prime $p$, $C_{p}$ is not
Groverian, but $C_{p}$ with the extra “matching” $x\mapsto x^{-1}\pmod{p}$ is
Groverian (as it is an expander, see Vadhan [16]). Left: $C_{13}$. Right: the
nonsimple $3$-regular expander $C_{13}$ plus the modular inverse matching.

##  8 Concluding remarks

We conclude with some open questions from the present work:

  1. 1.

Is the Groverian property determined by spectra? Moreover, is the condition
$\epsilon_{1}\ll\sqrt{S_{1}}\Delta_{2}$ necessary for optimal
characterization?

  2. 2.

Can a family of graphs be Groverian with non-constant $S_{1}$? To the best of
our knowledge, all families of graphs known to be Groverian satisfy
$S_{1}=\Theta_{n}(1)$.

  3. 3.

When is the Groverian property (almost) periodic?

  4. 4.

How robust is the Groverian property against noise? Regev and Schiff [13] had
ruled this out for the discrete-time case.

## Acknowledgments

We thank Tom Wong for helpful comments and Andris Ambainis for answering our
questions about [3]. C.T. and W.X. would also like to thank Warren Lord for
his insightful comments.

## References

  * [1] A. Ambainis.  Quantum walk algorithm for element distinctness.  SIAM J. Computing 37(1):210-239, 2007.
  * [2] N. Alon and J. Spencer.  The Probabilistic Method.  Wiley and Sons, 3rd edition, 2011.
  * [3] S. Chakraborty, L. Novo, Y. Omar, and A. Ambainis.  Spatial search by quantum walk is optimal for almost all graphs.  Physical Review Letters, 116:100501, 2016.
  * [4] S. Chakraborty, L. Novo, and J. Roland.  On the optimality of spatial search by continuous-time quantum walk.  Physical Review A, 102:032214, 2020.
  * [5] A. Childs and J. Goldstone.  Spatial search by quantum walk.  Physical Review A, 70:022314, 2004.
  * [6] E. Farhi and S. Gutmann.  Analog analogue of a digital quantum computation.  Physical Review A, 57(4):2403, 1998.
  * [7] L. Grover.  Quantum mechanics help in searching for a needle in a haystack.  Physical Review Letters, 79:325, 1997.
  * [8] R. Horn and C. Johnson.  Matrix Analysis.  Cambridge University Press, second edition, 2013.
  * [9] J. Janmark, D. Meyer, and T. Wong.  Global symmetry is not necessary for fast quantum search.  Physical Review Letters, 112:210502, 2014.
  * [10] S. Janson, T. Łuczak, and A. Ruciński.  Random Graphs.  Wiley and Sons, 2000.
  * [11] S. Jurišić and J. Vidali.  Restrictions on classical distance-regular graphs.  Journal of Algebraic Combinatorics, 46:571–588, 2017.
  * [12] M. Nielsen and I. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2000.
  * [13] O. Regev and L. Schiff.  Impossibility of a Quantum Speed-Up with a Faulty Oracle.  Proc. 35th International Colloquium on Automata, Languages, and Programming, 773-781, 2008.
  * [14] M. Szegedy.  Quantum speed-up for Markov chain based algorithms.  Proc. 45th Ann. IEEE FOundations of Computer Science, 32-41, 2004.
  * [15] H. Tanaka, M. Sabri, and R. Portugal.  Spatial search on Johnson graphs by continuous-time quantum walk.  arXiv:2108.01992 [math.CO], 2021.
  * [16] S. Vadhan.  Pseudorandomness.  Foundations and Trends in Theoretical Computer Science, Vol. 7, Nos. 1-3, 1-336, 2012.
  * [17] T. Wong.  Quantum walk search on Johnson graphs.  Journal of Physics A: Mathematical and Theoretical, 49(19):195303, 2016.


# Challenges for Inclusion in Software Engineering: The Case of the Emerging
Papua New Guinean Society

Raula Gaikovina Kula, Christoph Treude, Hideaki Hata, Sebastian Baltes, Igor
Steinmacher, Marco Aurélio Gerosa, Winifred Kula Amini NAIST, University of
Adelaide, Shinshu University, Federal University of Technology Paraná Northern
Arizona University, PNG Digital ICT Cluster<EMAIL_ADDRESS>{christoph.treude<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Software plays a central role in modern societies, with its high economic
value and potential for advancing societal change. In this paper, we
characterise challenges and opportunities for a country progressing towards
entering the global software industry, focusing on Papua New Guinea (PNG). By
hosting a Software Engineering workshop, we conducted a qualitative study by
recording talks (n=3), employing a questionnaire (n=52), and administering an
in-depth focus group session with local actors (n=5). Based on a thematic
analysis, we identified challenges as barriers and opportunities for the PNG
software engineering community. We also discuss the state of practices and how
to make it inclusive for practitioners, researchers, and educators from both
the local and global software engineering community.

###### Index Terms:

Inclusion, emerging society, software engineering.

##  I Introduction

Advances in technology have the potential to transform societies [1]. As a
society currently undergoing technological, economic, and social
transformations, Papua New Guinea (PNG) is entering the digital age and
showing signs of an emerging local software engineering community. In 2018, a
local PNG software development team won the annual APEC App Challenge
(https://www.apec.org/Press/Features/2018/0530_app). Such progress paves the
way for local economic development, with opportunities for young and talented
individuals to develop software in areas such as natural resources, finance,
healthcare, and education. These developments also open the local society to
the global software engineering (SE).

Following the work by Reijswoud et al. [2] carried out in 2009, we set out to
conduct a qualitative study with the local community in PNG, exploring the
current situation and possible future directions in that emerging software
development society. The goal of this study is to answer the research
question, what are the challenges (as barriers and opportunities) for Software
Engineering (SE) in an emerging society? To answer this question, we organised
a workshop in PNG and conducted an empirical analysis based on three recorded
talks, 52 questionnaire responses, and a focus group session with five
participants. Through thematic analysis, we derived five themes that affect
software engineering in emerging societies such as PNG. From that analysis, we
distilled a set of local as well as global implications.

Figure 1: Overview of the thematic approach for the study Figure 2: Summary of
the three data sources, from which information was collected for the study.

##  II Papua New Guinea as an Emerging Society

According to the World Bank [3], PNG has a population of over 9.1 million
(2020) with a diversity of geographic and natural resources. The country also
has an overall economic growth performance consistent with the real Gross
Domestic Product (GDP) per capita, averaging 4% since the mid-2000s. Sound
macroeconomic management and more efficient service delivery are critical to
ensure that development benefits reach a higher number of Papua New Guineans,
particularly given that 87% of Papua New Guineans live in rural areas. The
growth trajectory and abundant resources provide a reliable platform for
greater economic engagement with Asia and further abroad. The country’s
economy is currently dominated by resource-driven sectors, such as
agricultural, forestry, and fishing sectors and the minerals and energy
extraction sector. The World Bank report states that the population is highly
dispersed and fragmented, as a result of the mountainous and archipelagic
geography, low urbanization rate (13 percent), high ethnolinguistic diversity
(840 distinct language groups), and social identities that are primarily
small-scale, hence sharing the political economy characteristics of resource-
rich states.

PNG’s emergence into the digital age may foster access to life-enhancing
services in areas such as health and education. It may also catalyze
innovation and economic growth, with the promise of new jobs and increased tax
revenues (https://www.gsma.com/r/mobileeconomy/pacific-islands/). Like other
emerging nations, PNG’s Internet connectivity remains comparatively low, but
is continuously improving. From 2010 until 2013, the Internet penetration
increased from 1.3% to 6.5%. Since 2013, Internet penetration has jumped from
6.5% to 30% in 2018. This penetration is, however, significantly lower than in
neighbour countries like Fiji (84% in 2018). This situation is about to
improve with a new submarine fibre-optic cable connection to Australia
(https://oxfordbusinessgroup.com/news/how-png-achieving-faster-more-reliable-
internet-access). The formal economy is divided into two sectors, state and
non-state institutions. However, PNG’s informal economy was valued at 12
billion kina (US$3.5 billion), which is equivalent to approximately one-fifth
of the GDP and about 60% of the non-resource GDP [4]. Considering the large
number of people participating in the informal economy, the PNG government has
begun to invest in Small to Medium Enterprises (SMEs) to advocate for
financial inclusion (https://oxfordbusinessgroup.com/analysis/growth-
unchained-new-technologies-coupled-infrastructure-upgrades-are-expanding-
access-financial). For example, since mid-2017, banks have actively promoted
the distributed ledger technology blockchain for providing alternate forms of
financial services. Progress, however, has been slow. As of mid-2018, only
about 9.2% of the population has access to some form of digital wallet. The
PNG government has begun to invest in SMEs to advocate for financial
inclusion.

###  II-A The Software Engineering Perspective: BRIDGES

Based on the underlying research goal, we conducted a qualitative study
involving local actors from the emerging local software engineering community.
To this end, we organized and hosted the International Workshop on BRIdging
the Divides with Globally Engineered Software (BRIDGES) at https://naist-
se.github.io/BRIDGES2019/. The workshop was run by the University of Papua New
Guinea (UPNG) and Nara Institute of Science and Technology (NAIST).
Recruitment was through UPNG, as well as open invitations sent to the local
high schools, and all state and non-state institutions located in Port
Moresby. We formally invited a representative from the PNG government. The
workshop and survey were conducted in English as the main form of
communication. The workshop was held for three days in Port Moresby, the
capital city of PNG and the largest urban city in the Pacific region, with a
population estimated at over 350 thousand.

TABLE I: Demographics of invited speakers (S1-S3), questionnaire responses (Q1-Q52) and participants in the focus group (P1-P5) ID | Man/Women | Demographic | Sector
---|---|---|---
S1 | Man | Business Officer | State Institution
S2 | Man | Chief Executive Officer | Government
S3 | Woman | Project Manager | Non-state Institution
Q1-Q23 | - | High School Students | State Institution
Q24-Q35 | - | Professionals (IT) | Non-state Institution
Q36-Q45 | - | Startup associates | SMEs
Q46-Q52 | - | Students (Undergrad) | State Institution
P1 | Woman | Managerial (IT) | Non-state Institution
P2 | Man | Managerial (Non-IT) | Non-state Institution
P3 | Woman | Student (Undergrad) | State Institution
P4 | Woman | Entrepreneur (CEO) | SMEs
P5 | Man | IT Consultant | Non-state Institution

##  III Study Design

Illustrated in Figure 1, we use our research question to structure our
analysis, based on the thematic analysis framework proposed by Braun and
Clarke [5]. Figure 2 shows the list of questions that were used in our study.
Each data source is described below:

  1. 1.

Workshop Talks (n=3): The BRIDGES Workshop talks given by local SE community
members were recorded. All three talks ranged from 25 to 30 minutes each and
included interactive discussions with the audience afterwards. We recruited
these three presenters as they represent different sectors in PNG, including
government (S2) - Department of Higher Education Research, Science and
Technology, non-state - an Internet Service Provider (S3), and financial
institution (S1).

  2. 2.

Questionnaire-based Survey (n=52): We handed the questionnaire out to all
BRIDGES workshop participants and to the participants of a startup meetup that
was organized on the same day. The questionnaire was composed of workshop
participants’ demographics and their perceptions related to education, tools
and infrastructure. As shown in Table I, we received 52 responses, with the
majority of responses from high school or undergraduate students that attended
the event. The professionals include staff that work in the IT department, as
well as managers and system analysts of their institutions.

  3. 3.

Focus Group Discussion (n=5): After an analysis of the survey responses and
workshop talks, the authors decided to organize a semi-structured focus group
session. Participants were recruited from the workshop attendees and those
that filled out the survey. The authors also made sure to incorporate diverse
backgrounds and perspectives (professional and student, women and men, working
in management and consulting, from IT and non-IT fields, and in large
institutions and startups). This in-depth focus group “round table” discussion
took place two days after we collected the survey responses, lasting 1 hour
and 41 minutes.

For data analysis, we used transcripts of the talks and the survey responses
to gather insights on the state of practice, then used the focus group for a
deeper exploration based on the survey results. Our initial coding started
with the analysis of the focus group, as it contained the largest content of
information. This resulted in a total of 79 codes, including codes such as
“not enough developers and designers” and “outside of Port Moresby, most
education related to computers and IT is theory.” The next round of coding
then included the analysis and was merged with and reinforced by the codes
generated from the workshop talks and the responses of the survey. The first
four authors collaboratively conducted the initial round of analysis, while
the remaining three authors were used as validity checks to ensure that the
analysis was consistent throughout.

TABLE II: Themes which emerged from the data analysis

| Theme | # Focus Group | # Codes
---|---|---|---
|  | Contributions |
Barriers | Limited dedicated SE training | 4 | 25
| Establish trust in local SE | 3 | 4
Opportunities | Investment potential in local SE | 4 | 9
| Market focused on | 4 | 29
| customising off-the-shelf |  |
| Early stages of | 3 | 4
| technological leapfrogging |  |

Table II summarises the themes which emerged from our analysis, together with
the number of codes and number of focus group participants which contributed
to each theme. As the table shows, each theme relates to codes that were
assigned to quotes from at least three of the five focus group participants.
An additional eight codes from the original annotation were used to inform the
discussion of implications, cf. Section V. Each theme was further augmented
with data from the analysis of the survey responses and talks.

We sent a follow-up survey to 28 participants (i.e., the focus group
participants, invited speakers, and survey participants who left their contact
details) to further assess the credibility of our themes. Seven participants
responded to the survey (response rate of 25%).

##  IV Findings

We identified the following themes as barriers and opportunities for the PNG
SE community.

###  IV-A Limited software engineering training (Barrier)

With an adult literacy rate of 63.4% as of 2015 (taken from
https://knoema.com/atlas/Papua-New-Guinea/topics/Education/Literacy/Adult-
literacy-rate), education unsurprisingly plays a large role in the advancement
of PNG as an emerging society. The needs around software development education
were summarised by one of our focus group participants as follows:

> “I think we need specialised skills. From a graduate perspective, when we
> come out of uni, we only know the basics, we learn the general
> stuff—networking and programming, everything […] From where I’m working now,
> there are IT people in the organisation, but I think they lack the
> specialised skill in software engineering so they can support the
> organisation and build something, build a system, instead of just the
> general knowledge of everything.” –P3

In the survey, we asked participants about one thing they would change
regarding software development education in PNG. Six professionals mentioned
changing the education system either by teaching coding early (in primary or
high school) or by offering higher-education courses dedicated to software
development. Researchers and practitioners should be involved in designing an
updated curriculum:

> “It’s just they’re learning stuff that’s not up-to-date to where the
> industry is today. The other thing is, a research-backed and industry-backed
> curriculum that’s developed so that when our students graduate, they go out
> with the skills that are relevant to the world today.” –P4

In an emerging society that has only recently reached the new frontiers of the
digital age due to its developing education base, finding mentors within the
country is challenging:

> “Nobody’s done it before us. Without mentors, everything is pioneering, it’s
> the first time.” –P1

Participants mentioned several online education websites, including
FreeCodeCamp, O’Reilly, Udacity, and Coursera, which can serve as a substitute
for formal education in some situations.

###  IV-B Establish trust in local software engineers (Barrier)

Taken together, the limited dedicated software engineering training and
investment in the local software engineering workforce lead to trust issues in
the abilities of the local workforce—a classic “chicken-and-egg” problem:
Trust will only increase once the workforce is well-educated. Still, at the
moment, investment goes to foreign entities rather than the local workforce,
as P4 highlights:

> “If we tender for a project, like let’s say the government, they’re likely
> to get another firm outside, not a Papua New Guinean firm.” –P4

Developing trust in the local software engineering workforce is as much a
cultural issue as it is an educational issue:

> “The problem we have not only in PNG but in the Pacific Islands is we don’t
> trust our own […] we need to pay for someone to be an international person
> to join us so that they can trust us. […] Because we don’t trust our own
> qualification. It comes down to that. […] The mentality is the answers are
> always outside rather than inside, so they would pay larger amounts of money
> for someone outside rather than trusting someone inside.” –P1

###  IV-C Market focused on customising off-the-shelf software (Opportunity)

As a result of limited capacity as well as company and government policies to
buy off-the-shelf software, the market for software developers in PNG is
relatively small and provides more opportunities for customisation than
developing software from scratch:

> “A lot of the bigger companies […] buy off-the-shelf products. […] The
> products are normally standard off-the-shelf, and then they would be
> customised, but usually the vendor would provide the software development to
> the company; and the in-house software development team would have very
> minimal software development. They would most likely develop the intranet
> for the internal company or the website.” –P1

Overseas companies, often from nearby Australia, are attempting to fill this
gap, but this comes with costs related to software security, for example:

> “Most of the technology companies that do come in—most of the tenders for
> many of these large projects, not just large projects, but any sort of
> custom software development project—are overseas. There’s a lack of local
> capacities, and support and maintenance are provided by those companies off-
> shore as well. […] Security is a big issue. If people in the company don’t
> understand how the system is built, especially if it’s a custom one, then
> you never know how the system is properly protected.” –P4

While this could create a potential for the local software development market,
such potential often remains untapped, and even startups focus on the
customisation of existing technologies:

> “So the opportunity is for us to develop it based on our rules or the way we
> do business, but because we don’t have enough software developers or
> designers, we can’t be able to design systems that are fit for purpose.” –P1

###  IV-D Early stages of technological leapfrogging (Opportunity)

Technological leapfrogging refers to the transit of countries from the
condition of relative underdevelopment to that of an advanced industrial and
technological state in a relatively short span of time [6]. This process
typically follows three steps: (1) importing and absorbing highly modern
technology, (2) replicating, producing, and improving the imported technology,
and (3) moving on to innovations on one’s own. Our data suggest that PNG
currently finds itself at the early stages of such technological leapfrogging.

> “Education is a big a thing. In PNG, amongst average Papua New Guineans,
> their idea of technology is just the Internet or Facebook or whatever they
> use.” –P4

To move further along the path to technological leapfrogging will require
improved digital technology and digital literacy, as evidenced by this
anecdote from one of our focus group participants:

> “Last year, when I was in another province of PNG, we ran a one week
> workshop for girls in ICT there. So we got girls from throughout that
> province from the high schools. And there were about 25 girls and three of
> the girls that attended had never touched a computer before. And they were
> literally scared to touch a computer because they thought they would break
> something. So not everyone has access to digital technology. […] So access
> to digital technology is one, and then digital literacy is another thing.”
> –P4

A side effect of limited digital literacy is the tendency to try to run before
one can crawl, e.g., by investing in the latest technologies despite a lack of
foundational knowledge and experience. Investments into the latest
technologies do not necessarily trickle down to the software engineering
community:

> “A lot of our CEOs are traveling overseas, and they’re reading a lot of
> these in-flight magazines. So there’s a lot of content on Blockchain. So
> right now there’s so much money being pumped in here to bring Blockchain
> software developers into the country. […] But it’s not being translated
> down, we don’t understand how we could use Blockchain when the Internet’s
> not that good, and we don’t have the software engineering community.” –P1

A large barrier that is frequently mentioned in the talks, the survey
responses, and the focus group is the high cost and low speed of the Internet
infrastructure. Mobile Internet access, which is most commonly used, costs
around 150 Papua New Guinean Kina per month (approx. US$45) for 30GB,
unlimited access costs around 850 Kina per month (approx. US$250).
Participants pointed to the general potential of “open source software” and
“learning online”.

> “There is no point in building a big highway (internet cable), [when] there
> are no cars (applications) to ride on that highway. We hope this workshop
> can give our people incentive to build software to put the cars on this
> road. We hope our people can build software that puts traffic on what we are
> building.” –S1

S1 belongs to the state-owned entity that has been commissioned by the
government to build a fibre-based network that will connect all 22 provinces
across PNG, enabling the implementation of data centers that are expected to
benefit the business, education, and healthcare sectors.

###  IV-E Investment potential in local software engineers (Opportunity)

Boardrooms of Papua New Guinean companies were characterised as “non-techy” by
the participants of our focus group:

> “If you see our executives, they are all fifty-plus, they are all old-
> school, they don’t understand that tech plays an essential role in this day
> and age. […] Our IT guys are lower down in the hierarchy, so they’re not
> sitting with management.” –P2

As a consequence, companies do not invest in training through software
engineering internships or joint courses with industry. While such internships
exist in the mining sector, and mechanical and system engineering have
internships and graduate programs, there are no internships in IT or software
engineering:

> “So when it comes to software, because the people at the top don’t
> understand, we don’t design the software according to what the requirements
> are, so it usually comes out not the way we expect it to.” –P1

##  V State of Practice

As part of the follow-up survey, we find that participants strongly confirm
statements relating to three of our five themes, but interestingly, there was
no consistent agreement about the use of global technology, such as open
source and global platforms like GitHub and Stack Overflow (early stages of
technological leapfrogging) and whether dedicated SE training was up-to-date
(training). We now synthesize insights from our work to focus on lowering
barriers and seeking opportunities for SE in PNG.

###  V-A For the PNG ICT Industry

Our work covers the professionals that are both from the state, non-state and
SMEs. Similar to other resource-rich countries, non-state institutions rely on
state-intuitions and donor organizations to drive change. Hence, we identify
three practices the all institutions could follow to enable inclusion into the
global software engineering community. This would be in the form of offering
more (i) training, (ii) internships and (iii) lowering the barrier for SMEs.
Conducting short-term training to help onboarding local developers to create a
local workforce capable of fulfilling the technical needs is an important
step. It would directly address the theme of ‘limited dedicated SE training’
and indirectly enable the market to not solely focus on customising off-the-
shelf software if custom solutions can be built in PNG. Moreover, a qualified
local workforce will help ‘establish trust in local SE’ and lowering the
barriers for startup companies will help with the ‘investment potential in
local SE’.

At the level of PNG practitioners, our findings indicate that supporting local
actors in an emerging society to become members of the global software
development community can contribute to the sustainability of software
engineering. Such engagement could, for example, happen in the context of
open-source software, through contribution and knowledge-sharing with global
platforms such as GitHub and Stack Overflow.

###  V-B For the Global Research Community

Similarly to Craggs and Rashid [7], we identified trust as a crucial concept
in our study. Further research is needed on how to establish trust in the
local workforce in an emerging society, taking the important role of training
investment into account. More work is needed to understand what the predictors
are for the success of such programs in a given society. Inclusion in the
global SE should be encouraged, for example, participation in international
conferences leading to exposure to cutting edge technology. Researchers should
explore how global communication channels and social media can be leveraged as
practices to help include the local SE communities from emerging societies.
For example, PNG participants were invited to attend a Mining Software
Repositories conference under the widening participation program (details at
https://2021.msrconf.org/attending/widening-participation-program) for
inclusion.

###  V-C For Educators (both local and global)

Our findings indicate a need to update the existing education curricula
related to SE. In-line with the PNG ICT industry implications, the focus for
the state and non-state institutions should be on upgrading the capacity of
local educators, and importing foreign education. Non-state institutions
should advice that education of the local ICT should be a higher priority than
simply offshoring work, which becomes costly in the long run. Global
initiatives such as Google Summer of Code (GSoC) are partly aimed at emerging
societies, and have found large uptake in some of them.

##  VI Outlook

Recent literature has recognized that existing software engineering (SE)
processes, methods and practice are not suitable for the direct application in
emerging countries [8]. Reports from Ethiopia [9], Iran [10], Serbia [11], and
Sub-Saharan Africa [12] highlight different problems that affect the success
of software development industry in these countries; in particular they
mention low infrastructure [9, 12], lack of financial resources [10, 11], and
social and environmental factors [12]. We can see that most of the reported
problems are similar to those we uncovered in this paper.

There are also initiatives in place aiming to strengthen the software and
Information Technology industry in a way to benefit these countries. There are
several ICT4D (Information and Communications Technologies for Development)
initiatives aimed at bridging the digital divide by ensuring equitable access
to up-to-date communications technologies. One example is the Health
Information Systems Programme (HISP) for developing countries
(https://www.mn.uio.no/ifi/english/research/networks/hisp/).

When we look at the literature focusing on software development industry in
developing and underdeveloped countries, several studies show that government
support is essential for the growth of a local ecosystem, by supporting
education and infrastructure initiatives, for example [10, 11]. Other authors
specifically point to Open Source Software (OSS) as a trigger to the software
industry in an emerging country [13, 14]. PNG has not embraced these
advantages offered by OSS yet, as we could notice analyzing the work of Van
Reijswoud et al. [2]. In addition to the strategies mentioned above, we saw
that one of the main strategies to foster the local software industry is
reshaping education in emerging countries (e.g., [8, 15].)

The emerging society of PNG has only recently reached the digital age
frontiers, with early signs of a local SE community. While we cannot claim
generalisation of our results beyond PNG, we expect that our insights can be
transferred to similar emerging societies. Our future work will focus on
testing our assumptions in a wider context, especially in the area of Global
Software Development, to solve trust issues in distributed teams, and
communication issues across different cultures.

## Acknowledgements

We would like to thank all the participants and organizers of the BRIDGES at
https://naist-se.github.io/BRIDGES2019/, from NAIST and the University of PNG.
Furthermore, the event was supported by Oil Search, PNG DataCo, PNG Science
and Technology Council Secretariat, Nasfund Papua New Guinea and PNG Digital
ICT Cluster.

## References

  * [1] M. Castells, _The Rise of the Network Society_ , 2nd ed. Wiley-Blackwell, 2010.
  * [2] V. Van Reijswoud _et al._ , “The power to change: Adopting free and open source software in papua new guinea,” _Contemporary PNG Studies_ , vol. 10, p. 40, 2009.
  * [3] Worldbank, “Overview of papua new guinea,” https://www.worldbank.org/en/country/png/overview, 2008, accessed: 2019-10-25.
  * [4] GSMA. (2019) Sleeping giant at the heart of png economy. https://tinyurl.com/y6m3pzay. Accessed: 2019-10-25.
  * [5] V. Braun and V. Clarke, “Using thematic analysis in psychology,” _Qualitative research in psychology_ , vol. 3, no. 2, pp. 77–101, 2006.
  * [6] M. Bhagavan, “Technological leapfrogging by developing countries,” _EOLSS: Paris, France_ , 2001.
  * [7] B. Craggs and A. Rashid, “Trust beyond computation alone: Human aspects of trust in blockchain technologies,” in _ICSE-SEIS 2019_ , 2019.
  * [8] R. Osman, “Teaching software engineering in developing countries: a position paper,” in _COMPSAC 2012_ , 2012.
  * [9] D. Teka, Y. Dittrich, and M. Kifle, “Usability challenges in an ethiopian software development organization,” in _CHASE 2016_ , 2016.
  * [10] E. Khaksar and A. Khaksar, “Study of the software industry problems in iran,” _American Journal of Systems and Software_ , vol. 3, no. 1, pp. 20–23, 2015\.
  * [11] M. Stefanovic, M. Matijevic, and G. Devedzic, “Ict industry in serbia: Condition and improvement by qms,” _World Journal of Science, Technology and Sustainable Development_ , vol. 7, no. 1, pp. 73–90, 2010.
  * [12] A. Mursu, H. A. Soriyan, K. Olufokunbi, and M. Korpela, “Information systems development in a developing country: Theoretical analysis of special requirements in nigeria and africa,” in _HICSS 2000_.
  * [13] D. Gakh, “Open source software to support the education processes in software development in post-soviet countries,” in _INTERNET-EDUCATION-SCIENCE 2018_ , 2018.
  * [14] G. Camara and F. Fonseca, “Information policies and open source software in developing countries,” _Journal of the American society for information science and technology_ , vol. 58, no. 1, pp. 121–132, 2007.
  * [15] K. Garg and V. Varma, “Software engineering education in india: Issues and challenges,” in _CSEE &T 2008_, 2008.