# Quantum walk based state transfer algorithms on the complete $M$-partite
graph

S. Skoupý and M. Štefaňák  Department of Physics, Faculty of Nuclear Sciences
and Physical Engineering, Czech Technical University in Prague, Břehová 7, 115
19 Praha 1 - Staré Město, Czech Republic

###### Abstract

We investigate coined quantum walk search and state transfer algorithms,
focusing on the complete $M$-partite graph with $N$ vertices in each
partition. First, it is shown that by adding a loop to each vertex the search
algorithm finds the marked vertex with unit probability in the limit of a
large graph. Next, we employ the evolution operator of the search with two
marked vertices to perform a state transfer between the sender and the
receiver. We show that when the sender and the receiver are in different
partitions the algorithm succeeds with fidelity approaching unity for a large
graph. However, when the sender and the receiver are in the same partition the
fidelity does not reach exactly one. To amend this problem we propose a state
transfer algorithm with an active switch, whose fidelity can be estimated
based on the single vertex search alone.

##  I Introduction

Quantum walks [1] are quantum mechanical analogues of random walks. Their
dynamics can be formulated either in discrete time steps [2], as we consider
in the present paper, or in continuous time [3]. Both have found promising
applications in quantum information processing [4], notably in quantum spatial
search where an unsorted database is represented by a graph. The solution to
the search problem corresponds to a marked vertex, where the local dynamics is
different from the non-marked vertices. Usually, the initial state of the walk
is taken as the equal weight superposition of all basis states. The walk is
evolved coherently for $T$ steps, after which we perform a measurement which
collapses the state of superposition and the walker is found on a single
vertex. On various graphs quantum walk is capable of finding the marked vertex
with sufficiently high probability in a number of steps that grows with the
square root of the number of vertices $n$, i.e., the complexity is the same as
for the abstract Grover search algorithm [5] which is known to be optimal.
Initially, the investigation was mostly focused on graphs with some degree of
symmetry or regularity. Continuous time quantum walks were shown to be optimal
[6] for a complete graph, hypercube and lattices of dimensions greater than 4.
Discrete time quantum walks with coins [7] are also optimal on these graphs
[8, 9, 10, 11], in addition, they are optimal for lattices of dimensions
greater than 2 [9]. Scattering quantum walk [12, 13, 14], which represents an
alternative equivalent formulation of the coined quantum walk [15, 16], can
perform optimal search e.g., on a star graph or a complete $M$-partite graph
[17]. However, high symmetry is not required for the optimal performance of
the quantum walk search [18, 19, 20]. In fact, it was shown [21] that
continuous the time quantum walk is optimal on Erdös-Renyi random graphs as
long as the probability of an edge existing between any pair of vertices is
greater than $\left(\log^{\frac{3}{2}}n\right)/n$. However, on scale-free
networks [22] the application of quantum walk search appears to be limited
since the optimal run-time depends on the centrality of the marked node [23].
More recently [24] several sufficient and necessary conditions for continuous
time quantum walk search to be optimal were derived.

For the search algorithm (SA) it is not required that we find the marked
vertex with unit probability. As long as the success probability is constant,
we can repeat the SA several times depending on our error tolerance to find
the marked vertex with high probability without changing the overall
complexity of the algorithm. Even if the success probability is of the order
of $1/\log n$, as for the discrete time quantum walk on the 2D lattice [9], we
can use amplitude amplification [25] which increases the run-time of the SA by
a factor of $\sqrt{\log n}$. There are several graphs where the quantum walk
SA is exactly equivalent to the Grover search, e.g., the star graph [17],
which means that the success probability is unity. It is interesting that for
the discrete time quantum walks the success probability of the SA can be often
increased close to unity by adding loops of appropriate weights at each
vertex. This was found originally for the complete graph [9] and the hypercube
[10]. Later investigations [26, 27, 28, 29, 30] found that this result is much
more generic and the optimal weight of the loop depending on the size of the
graph and degree of the vertex was identified. Recently, it was proven that
adding loops improves the success probability of the SA on all regular locally
arc-transitive graphs [31].

Quantum walks were also applied to the task of state transfer [32] between two
vertices of a graph. In this context the initial state of the walk is
localized on the sender vertex and we want to transfer it with high
probability to the receiver vertex. Provided that the location of the sender
and the receiver vertices are known, we can globally design the dynamics such
that the walker is transferred from one to the other. This approach was
investigated on different graphs such as circle [33, 34], 2D lattice [35],
regular graphs [36] or more general networks [37]. When the sender and the
receiver don’t know each other’s position they can perform state transfer by
modifying the local coins at their own vertices, i.e., by implementing the
evolution operator of the SA for two marked vertices. This approach was
proposed for state transfer on lattices [38] and further analyzed on various
types of finite graphs, e. g. on cycles and their variants [39, 40], star and
complete graph with loops [41], complete bipartite graph [42], circulant
graphs [43] or butterfly network [44]. Similar approach can be also applied
for finding a path in a maze formed by star graphs [45] or trees [46].

We consider the state transfer algorithm (STA) following the second approach,
i.e., based on the evolution operator of the SA with two marked vertices. For
the STA it is desirable that we succeed in the first attempt, i.e., the
fidelity of state transfer should be ideally one. Natural candidates for
graphs where STA works with unit fidelity are those where also the SA succeeds
with certainty. Indeed, the graphs considered in [41, 42] were chosen exactly
based on this idea. However, in this paper we show an example of a graph where
the SA works with certainty yet in some instance the STA does not have unit
fidelity.

We investigate search and state transfer on the complete $M$-partite graph
with $N$ vertices in each partition, i.e., the graph has $n=NM$ vertices.
Search on the complete $M$-partite graph was already investigated in [17] in
the framework of the scattering quantum walk. In the coined walk the success
probability of SA reaches $\frac{1}{2}$. We show that by adding a loop to each
vertex the success probability tends to one for a large graph. Our approach is
based on dimensional reduction [47, 48, 49, 19]. First, we find an exact
invariant subspace $\cal I$ where the state of the algorithm evolves. Next, we
investigate the eigenvectors of the evolution operator in the limit of a large
graph $M\to\infty$ and $N\to\infty$ and determine those which have non-
vanishing overlap with the initial state. These eigenvectors form an
orthonormal basis of the relevant part of the invariant subspace. For the SA,
we find an exact invariant subspace with dimension 8, and in the asymptotic
limit the relevant part is three-dimensional. We then investigate the
evolution operator of the search with two marked vertices for the sake of
state transfer. There are two possible configurations - either sender and
receiver are in the same partition or not. In the first case, we find an exact
invariant subspace with dimension 11, while in the second case it has
dimension 22. To simplify the calculations, we employ the symmetry of the
graph which allows us to exchange the sender and the receiver vertex, or the
whole partitions containing them in the latter case. This symmetry splits the
invariant subspace $\cal I$ further into two closed subspaces - $\cal I_{+}$
in which the search with two marked vertices evolves, and the complementary
subspace $\cal I_{-}$ needed for the state transfer. In the configuration
where the sender and the receiver are in the same partition, the subspace
$\cal I_{+}$ has dimension 8 and the complementary subspace $\cal I_{-}$ is
three-dimensional. For the second configuration the subspaces have dimensions
12 and 10, respectively. Nevertheless, in the limit of a large graph only five
eigenvectors of the evolution operator remain relevant in both configurations
- three in the subspace $\cal I_{+}$ and two in $\cal I_{-}$. The
corresponding eigenvalues can be also determined analytically. We show that
when the sender and the receiver are in different partitions the phases of the
relevant eigenvalues are harmonic. Hence, state transfer is achieved with unit
fidelity. However, when the sender and the receiver are in the same partition,
the phases are not harmonic, and the fidelity of state transfer is less than
one. To fix this issue we propose an STA with an active switch, where
initially only the sender vertex is marked, and after some number of steps the
marking is switched to the receiver vertex. The fidelity reachable by this STA
can be estimated based on the properties of the search for a single vertex. We
show that STA with an active switch achieves perfect state transfer on the
complete $M$-partite graph in the limit of large $N$ and $M$ for both
configurations of the sender and the receiver vertex, and discuss its
applicability on other graphs.

The paper is organized as follows: In Section II we describe discrete time
quantum walks with coin on finite graphs and introduce the quantum walk search
and state transfer algorithms. In Section III search on the complete
$M$-partite graph with one marked vertex is investigated in detail. Section IV
is devoted to the STA. The cases of sender and receiver vertices being in the
same or different partitions are analyzed in Section IV.1 and Section IV.2,
respectively. In Section V we consider a STA with an active switch. We
conclude and provide an outlook in Section VI.

##  II Preliminaries

In this section we overview the general design of the search and the state
transfer algorithms based on the discrete-time quantum walks with coins [8],
[9] and [38]. Before we turn to the algorithms, we describe the discrete time
quantum walks with coins. Let us start with Hilbert space of the walk. Having
a graph $G=\left(V,E\right)$ the corresponding Hilbert space ${\cal H}_{G}$
can be decomposed as a direct sum

${\cal H}_{G}=\bigoplus_{v}{\cal H}_{v},$

of local Hilbert spaces at each vertex $v\in V$. The orthonormal basis in
${\cal H}_{v}$ is given by vectors $\mathinner{|{v,w}\rangle}$ such that there
is an edge between vertex $v$ and $w$

${\cal H}_{v}={\rm Span}\left\\{|v,w\rangle|w\in V,\left\\{v,w\right\\}\in
E\right\\}.$

In the basis state $\mathinner{|{v,w}\rangle}$ the first index $v$ describes
the actual position of the walker, while the second index $w$ describes the
direction of propagation of the walker. Movement of the walker is achieved by
application of the flip-flop shift operator $\hat{S}$, which is defined in the
following way

$\displaystyle\hat{S}|v,w\rangle=|w,v\rangle.$ (1)

To generate a nontrivial evolution a coin operator $\hat{C}$ is applied at
every step before the shift takes place. The coin operator can be decomposed
into a direct sum

$\hat{C}=\bigoplus_{v}\hat{C}_{v}^{(l)},$

where $\hat{C}_{v}^{(l)}$ acts locally at a vertex $v$, i.e., it is a unitary
operator on ${\cal H}_{v}$. The evolution operator $\hat{U}$ of one step of
the walk is then given by

$\displaystyle\hat{U}=\hat{S}\hat{C}.$ (2)

The main idea of search and state transfer algorithms is to apply one local
coin operator at the marked vertices and different local coin operator at the
other vertices of the graph. Marked vertices are those that we want to find or
between which we want transfer the walker. Usually, the local coin that is
used at non-marked vertices is the Grover operator [5]

$\displaystyle\hat{G}_{v}^{(l)}=2|\Omega_{v}\rangle\langle\Omega_{v}|-\hat{I}_{v}^{(l)},$
(3)

where $\hat{I}_{v}^{(l)}$ is an identity operator at the subspace ${\cal
H}_{v}$ and $|\Omega_{v}\rangle$ is an equal weight superposition of all basis
states at the vertex $v$ given by

$\displaystyle|\Omega_{v}\rangle=\frac{1}{\sqrt{d\left(v\right)}}\sum_{\begin{subarray}{c}w\\\
\left\\{v,w\right\\}\in E\end{subarray}}|v,w\rangle.$ (4)

Here $d(v)$ denotes the degree of the vertex $v$, which is also the dimension
of the subspace ${\cal H}_{v}$. The coin operator of the SA with one marked
vertex $m$ reads

$\displaystyle\hat{C}_{m}=\bigoplus_{\begin{subarray}{c}v\in V\\\ v\neq
m\end{subarray}}\hat{G}_{v}^{(l)}\oplus\hat{C}_{m}^{(l)}$ (5)

where $\hat{C}_{m}^{(l)}$ is the local coin operator at the marked vertex. A
usual choice for the marked coin is either a simple phase shift by $\pi$
(i.e., $\hat{C}_{m}^{(l)}=-\hat{I}_{m}^{(l)}$), or the Grover operator
followed by a phase shift by $\pi$ (i.e.,
$\hat{C}_{m}^{(l)}=-\hat{G}_{m}^{(l)}$). In the present paper we consider the
latter case. Using the coin operator (5) we obtain the evolution operator of
the SA

$\hat{U}_{m}=\hat{S}\hat{C}_{m}.$

The steps of the SA are:

  1. 1.

Initialize the walk in the equal weight superposition of all basis states

$\displaystyle|\Omega\rangle=\frac{1}{\sqrt{\sum\limits_{v\in
V}d(v)}}\sum_{v\in V}\sqrt{d(v)}|\Omega_{v}\rangle.$ (6)

  2. 2.

Apply the evolution operator $\hat{U}_{m}$ $t$-times. The state of the walk
after $t$ steps is given by

$|\phi\left(t\right)\rangle=\hat{U}_{m}^{t}\mathinner{|{\Omega}\rangle}.$

  3. 3.

Measure the walk.

The probability to find the walker at the marked vertex is given by the
summation over all basis states in the subspace ${\cal H}_{m}$

$\displaystyle P_{m}(t)=\sum_{\begin{subarray}{c}w\\\ \left\\{m,w\right\\}\in
E\end{subarray}}|\langle m,w|\phi\left(t\right)\rangle|^{2}.$ (7)

The optimal number of steps $T$ providing high success probability depends on
the structure of the graph.

In the case of STA we consider $2$ parties, sender and receiver sitting at
vertices $s$ and $r$, respectively, which want to establish communication
between each other. The sender and the receiver have access only to their
local Hilbert spaces ${\cal H}_{s}$ and ${\cal H}_{r}$, respectively. Typical
STA [38, 41, 42] uses the evolution operator of the search for two marked
vertices

$\hat{U}_{s,r}=S\hat{C}_{s,r},$

where we apply the same local coins at both marked vertices at the same time

$\displaystyle\hat{C}_{s,r}=\bigoplus_{\begin{subarray}{c}v\in V\\\ v\neq
s,r\end{subarray}}\hat{G}_{v}^{(l)}\oplus\hat{C}_{s}^{(l)}\oplus\hat{C}_{r}^{(l)}.$
(8)

However, the initial state of STA is different — it starts localized at the
sender vertex in some state $\mathinner{|{s}\rangle}$. Standard choice is the
equal weight superposition of all basis states at the vertex $s$, i.e.,
$\mathinner{|{s}\rangle}=\mathinner{|{\Omega_{s}}\rangle}$. The steps of the
STA are the following:

  1. 1.

Sender initializes the walk at its vertex in the state
$\mathinner{|{s}\rangle}$.

  2. 2.

The evolution operator $\hat{U}_{s,r}$ is applied $t$-times. The state of the
walk after $t$ steps is given by

$|\phi\left(t\right)\rangle=\hat{U}_{s,r}^{t}\mathinner{|{s}\rangle}.$

  3. 3.

Receiver measures the walk at its vertex.

The fidelity of the STA, i.e., the probability that the receiver finds the
walker at its vertex, is given by

$\displaystyle{\cal F}(t)=\sum_{\begin{subarray}{c}w\\\
\left\\{r,w\right\\}\in E\end{subarray}}|\langle
r,w|\phi\left(t\right)\rangle|^{2}.$ (9)

The number of steps $T^{(st)}$ required to achieve state transfer with high
fidelity depends again on the size and the structure of the graph. In contrast
to the SA it is desirable that the STA performs with high fidelity in a single
run. In such a case we talk about perfect state transfer.

##  III Search on the complete M-partite graph

Consider the complete $M$-partite graph (with $M>2$). Complete $M$-partite
graph is a graph that has the set of vertices $V$ divided into $M$ subsets,
where vertices have no edges between them, but are connected to all vertices
in other subsets. We label the vertices of the graph as $v_{\alpha}$, where
$\alpha=1,\ldots,M$ denotes the partition. The basis states of the quantum
walk are therefore given by $\mathinner{|{v_{\alpha},w_{\beta}}\rangle}$,
$\alpha\neq\beta$. We also limit ourselves to the case where all parts have
the same size $N$, thus the whole graph has $n=MN$ vertices. This choice
greatly simplifies the construction of the invariant subspace. The graph is
$d$-regular with the vertex degree

$d=N(M-1).$

Without loss of generality we assume that the marked vertex is in the first
partition.

Search on the complete $M$-partite graph was investigated in [17] in the
framework of the scattering quantum walk. The difference between the two
formulations is that in the coined walk the walker lives on the vertices,
while in the scattering walk it lives on the edges. The results of [17] can be
adopted for the coined quantum walk with a single modification. Namely, for
the evaluation of the success probability (7) we consider only the overlap
with the states where the walker is at the marked vertex, i.e., of the form
$\mathinner{|{m_{1},k_{\alpha}}\rangle}$, $k=1,\ldots,N$, $\alpha=2,\ldots,M$,
which form the basis of the local Hilbert space at marked vertex ${\cal
H}_{m}$. The equal weight superposition of such states corresponds to the
state $\mathinner{|{w_{2}}\rangle}$ in [17]. This gives us the success
probability of $\frac{1}{2}$ for a large graph. Note that with probability
close to $\frac{1}{2}$ we would find the walker in some state
$\mathinner{|{k_{\alpha},m_{1}}\rangle}$, $k=1,\ldots,N$, $\alpha=2,\ldots,M$,
i.e., where the walker is at the vertex $k_{\alpha}$ and would move to the
marked vertex after the application of the shift $\hat{S}$. In the scattering
walk framework these states are also considered in the evaluation of the
success probability. Nevertheless, we focus on the coined formulation. In the
end our goal is to investigate the state transfer between vertices where the
coined formulation is more natural, since sender and receiver are considered
to be restricted to their local Hilbert spaces ${\cal H}_{s}$ and ${\cal
H}_{r}$, respectively.

We show that one can improve the success probability of the coined walk search
by adding one loop at each vertex. This is done by adding basis states
$\mathinner{|{v_{\alpha},v_{\alpha}}\rangle}$ corresponding to the loop at
each vertex, i.e. the dimension of the local Hilbert spaces ${\cal
H}_{v_{\alpha}}$ increases by one. Moreover, we modify the local coin operator
(3) by replacing the state $\mathinner{|{\Omega_{v_{\alpha}}}\rangle}$ (4)
with the state $\mathinner{|{\Omega_{v_{\alpha}}(l)}\rangle}$ given by

$\mathinner{|{\Omega_{v_{\alpha}}(l)}\rangle}=\frac{1}{\sqrt{d+l}}\left(\sum_{\begin{subarray}{c}\beta=1\\\
\beta\neq\alpha\end{subarray}}^{M}\sum_{k=1}^{N}\mathinner{|{{v_{\alpha}},k_{\beta}}\rangle}+\sqrt{l}\mathinner{|{{v_{\alpha}},{v_{\alpha}}}\rangle}\right),$

where $l$ is the weight of the loop. Note, however, that the initial state of
the SA remains the same as before, i.e., we prepare the system in the equal
weight superposition (6) of all basis states excluding the states
corresponding to the loops. According to [29, 31] the optimal weight $l$ of
the loops is given by

$l=\frac{d}{NM}={1-\frac{1}{M}}.$ (10)

Since we focus on the limit of a large graph we put $l=1$. This choice
corresponds to the local coin operator being the Grover operator (3) of
dimensions $d+1$, except for the marked vertex where we include an additional
phase shift by $\pi$. First, we show that the SA evolves in an 8-dimensional
invariant subspace ${\cal I}$. We note that in principle the dimension of the
exact invariant subspace can be reduced further, since the evolution operator
restricted on $\cal I$ still has some degenerate eigenvalues. However, the
construction of the basis would not be as intuitive and the ensuing
calculations will not simplify. Second, we consider a limit of a large graph
which effectively reduces the dimension of the invariant subspace to three.

Let us begin with the construction of the basis of the invariant subspace
${\cal I}$. The numerical simulations indicate that the state of the walk
$\mathinner{|{\phi(t)}\rangle}$ evolves periodically close to a state
corresponding to the loop on the marked vertex
$\mathinner{|{m_{1},m_{1}}\rangle}$. Hence, we consider this desired target
state of the SA as the first basis vector of the invariant subspace

$\mathinner{|{\nu_{1}}\rangle}=\mathinner{|{m_{1},m_{1}}\rangle}.$ (11)

Next, we add an equal weight superposition of all edges leaving the marked
vertex

$|\nu_{2}\rangle=\frac{1}{\sqrt{d}}\sum_{\alpha=2}^{M}\sum_{k=1}^{N}|m_{1},k_{\alpha}\rangle.$
(12)

Concerning the non-marked vertices in the first partition, we add two states
corresponding to a superposition of all loops and a superposition of all edges
leaving the first partition

$\displaystyle|\nu_{3}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{(N-1)}}\sum_{j\neq m}^{N}|j_{1},j_{1}\rangle,$
$\displaystyle|\nu_{4}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d(N-1)}}\sum_{j\neq
m}^{N}\sum_{\alpha=2}^{M}\sum_{k=1}^{N}|j_{1},k_{\alpha}\rangle.$

Next, we consider the edges leading to the first partition from the outside
and ending either on the marked or non-marked vertex, and construct the
following two basis states

$\displaystyle|\nu_{5}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d}}\sum_{\alpha=2}^{M}\sum_{k=1}^{N}|k_{\alpha},m_{1}\rangle,$
(13) $\displaystyle|\nu_{6}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d(N-1)}}\sum_{j\neq
m}^{N}\sum_{\alpha=2}^{M}\sum_{k=1}^{N}|k_{\alpha},j_{1}\rangle.$

These states can be obtained by applying the shift operator on
$\mathinner{|{\nu_{2}}\rangle}$ and $\mathinner{|{\nu_{4}}\rangle}$. To
complete the basis we consider the states corresponding to the superposition
of all edges between the vertices outside of the first partition

$|\nu_{7}\rangle=\frac{1}{\sqrt{d(d-N)}}\sum_{\begin{subarray}{c}\alpha,\beta=2\\\
\beta\neq\alpha\end{subarray}}^{M}\sum_{j,k=1}^{N}|j_{\alpha},k_{\beta}\rangle$

and the superposition of all remaining loops

$|\nu_{8}\rangle=\frac{1}{\sqrt{d}}\sum_{\alpha=2}^{M}\sum_{k=1}^{N}|k_{\alpha},k_{\alpha}\rangle.$

Clearly, the initial state of the SA (6) lies in ${\cal I}$ and has the
following form

$\displaystyle\mathinner{|{\Omega}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{MN}}\left[|\nu_{2}\rangle+|\nu_{5}\rangle+\sqrt{d-N}|\nu_{7}\rangle+\right.$
(14)
$\displaystyle\left.+\sqrt{N-1}(\mathinner{|{\nu_{4}}\rangle}+\mathinner{|{\nu_{6}}\rangle})\right].$

By direct calculation one can show that the evolution operator $\hat{U}_{m}$
of the SA acts on the basis states according to

$\displaystyle\hat{U}_{m}\mathinner{|{\nu_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left((d-1)\mathinner{|{\nu_{1}}\rangle}-2\sqrt{d}\mathinner{|{\nu_{5}}\rangle}\right),$
$\displaystyle\hat{U}_{m}\mathinner{|{\nu_{2}}\rangle}$ $\displaystyle=$
$\displaystyle-\frac{1}{d+1}\left(2\sqrt{d}\mathinner{|{\nu_{1}}\rangle}+(d-1)\mathinner{|{\nu_{5}}\rangle}\right),$
$\displaystyle\hat{U}_{m}\mathinner{|{\nu_{3}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left((1-d)\mathinner{|{\nu_{3}}\rangle}+2\sqrt{d}\mathinner{|{\nu_{6}}\rangle}\right),$
$\displaystyle\hat{U}_{m}\mathinner{|{\nu_{4}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{d}\mathinner{|{\nu_{3}}\rangle}+(d-1)\mathinner{|{\nu_{6}}\rangle}\right),$
$\displaystyle\hat{U}_{m}\mathinner{|{\nu_{5}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left((1-d)\mathinner{|{\nu_{2}}\rangle}+2\sqrt{N-1}\mathinner{|{\nu_{4}}\rangle}+\right.$
$\displaystyle\left.+2\sqrt{d-N}\mathinner{|{\nu_{7}}\rangle}+2\mathinner{|{\nu_{8}}\rangle}\right),$
$\displaystyle\hat{U}_{m}\mathinner{|{\nu_{6}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{N-1}\mathinner{|{\nu_{2}}\rangle}-(d+3-2N)\mathinner{|{\nu_{4}}\rangle}+\right.$
$\displaystyle+2\sqrt{(d-N)(N-1)}\mathinner{|{\nu_{7}}\rangle}+$
$\displaystyle\left.+2\sqrt{N-1}\mathinner{|{\nu_{8}}\rangle}\right),$
$\displaystyle\hat{U}_{m}\mathinner{|{\nu_{7}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{d-N}\mathinner{|{\nu_{2}}\rangle}+\right.$
$\displaystyle\left.+2\sqrt{(d-N)(N-1)}\mathinner{|{\nu_{4}}\rangle}+\right.$
$\displaystyle\left.+(d-1-2N)\mathinner{|{\nu_{7}}\rangle}+2\sqrt{d-N}\mathinner{|{\nu_{8}}\rangle}\right),$
$\displaystyle\hat{U}_{m}\mathinner{|{\nu_{8}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\mathinner{|{\nu_{2}}\rangle}+2\sqrt{N-1}\mathinner{|{\nu_{4}}\rangle}+\right.$
(15)
$\displaystyle\left.+2\sqrt{d-N}\mathinner{|{\nu_{7}}\rangle}+(1-d)\mathinner{|{\nu_{8}}\rangle}\right).$

Hence, $\cal I$ is indeed an invariant subspace of the SA and the state of the
walk $\mathinner{|{\phi(t)}\rangle}$ remains in $\cal I$ for all $t$. Its
evolution is determined by the eigenvalues and eigenvectors of $\hat{U}_{m}$,
which is in the invariant subspace represented by an $8\times 8$ unitary
matrix with matrix elements given by (15). While it is possible to diagonalize
this matrix analytically, the procedure is rather onerous and the resulting
expressions are quite lengthy. Nevertheless, the analysis can be considerably
simplified in the limit of a large graph, i.e., when $N\to\infty$ and
$M\to\infty$. As we can see from the expansion (14) for large $N$ and $M$ the
initial state of the algorithm tends to $\mathinner{|{\nu_{7}}\rangle}$.
Hence, the only eigenvectors of the evolution operator $\hat{U}_{m}$, which
remain relevant in the asymptotic limit, are those which have non-vanishing
overlap with $\mathinner{|{\nu_{7}}\rangle}$. It turns out that there are only
three such states and their asymptotic form is given by

$\displaystyle\mathinner{|{\psi_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(\mathinner{|{\nu_{7}}\rangle}-\mathinner{|{\nu_{1}}\rangle}),$
$\displaystyle\mathinner{|{\psi_{2}^{(\pm)}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{2}(\mathinner{|{\nu_{1}}\rangle}+\mathinner{|{\nu_{7}}\rangle}\pm
i(\mathinner{|{\nu_{5}}\rangle}-\mathinner{|{\nu_{2}}\rangle})).$ (16)

It can be shown that for the other eigenvectors of $\hat{U}_{m}$ the overlap
with the initial state decreases at least as $O(1/\sqrt{NM})$. Let us turn to
the eigenvalues. The eigenvector $\mathinner{|{\psi_{1}}\rangle}$ corresponds
to $\lambda_{1}=1$. For $\mathinner{|{\psi_{2}^{(\pm)}}\rangle}$ the
eigenvalues have the form

$\lambda_{2}^{(\pm)}=e^{\pm i\omega_{2}}.$

From the characteristic polynomial of $\hat{U}_{m}$ we find that
$\cos\omega_{2}$ is given by the largest root of the quadratic equation

$\displaystyle
x^{2}-\left(1-\frac{N}{d+1}\right)x-\frac{(d+1)(N-2)+N-3}{{(d+1)}^{2}}=0.$

This leads us to

$\displaystyle\omega_{2}$ $\displaystyle=$
$\displaystyle\arccos\left(1-\frac{1+NM-\sqrt{N^{2}M^{2}-6NM+4N+5}}{2{(d+1)}}\right)$
(17) $\displaystyle\approx$ $\displaystyle\frac{2}{\sqrt{NM}}.$

From the relations (16) we express the initial and the target state of the SA
in terms of the eigenvectors of the evolution operator as

$\displaystyle\mathinner{|{\Omega}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\mathinner{|{\psi_{1}}\rangle}+\frac{1}{2}\left(\mathinner{|{\psi_{2}^{(+)}}\rangle}+\mathinner{|{\psi_{2}^{(-)}}\rangle}\right),$
$\displaystyle\mathinner{|{\nu_{1}}\rangle}$ $\displaystyle=$
$\displaystyle-\frac{1}{\sqrt{2}}\mathinner{|{\psi_{1}}\rangle}+\frac{1}{2}\left(\mathinner{|{\psi_{2}^{(+)}}\rangle}+\mathinner{|{\psi_{2}^{(-)}}\rangle}\right).$
(18)

The state after $t$ iterations of the SA reads

$\mathinner{|{\phi(t)}\rangle}=\frac{1}{\sqrt{2}}\mathinner{|{\psi_{1}}\rangle}+\frac{1}{2}\left(e^{i\omega_{2}t}\mathinner{|{\psi_{2}^{(+)}}\rangle}+e^{-i\omega_{2}t}\mathinner{|{\psi_{2}^{(-)}}\rangle}\right).$
(19)

The success probability (7) of the SA after $t$ steps can be expressed in the
form

$P_{m}(t)=|\langle\nu_{1}|\phi(t)\rangle|^{2}+|\langle\nu_{2}|\phi(t)\rangle|^{2}.$
(20)

From (19) and (18) we see that the probability to find the walker in the
target state $\mathinner{|{\nu_{1}}\rangle}$ is given by

$|\langle\nu_{1}|\phi(t)\rangle|^{2}=\sin^{4}\left(\frac{\omega_{2}t}{2}\right).$
(21)

The probability to find the walker in the state
$\mathinner{|{\nu_{2}}\rangle}$ reads

$|\langle\nu_{2}|\phi(t)\rangle|^{2}=\frac{1}{4}\sin^{2}\left(\omega_{2}t\right).$
(22)

Put together we obtain the overall success probability of the SA

$P_{m}(t)=\sin^{2}\left(\frac{\omega_{2}t}{2}\right).$ (23)

We see that for $t=\frac{\pi}{\omega_{2}}$ the state of the SA is very close
to the target state $\mathinner{|{\nu_{1}}\rangle}$. Hence, the number of
steps needed to find the marked vertex with probability close to one is given
by

$T=\frac{\pi}{\omega_{2}}\approx\frac{\pi\sqrt{NM}}{2}+O\left(\frac{1}{\sqrt{NM}}\right).$
(24)

For illustration we plot in Figure 1 the probability to find the marked vertex
(23) as a function of the number of steps for a graph with $N=40$ and $M=100$.

Figure 1: Overall success probability of SA (black dots) and the probability
to find the walker in the target state $\mathinner{|{\nu_{1}}\rangle}$ (blue
squares) as a function of the number of steps $t$ for $N=40$ and $M=100$. Red
curves correspond to the analytical results (dashed line to eq. (21) and full
line to eq. (23) ). Green diamonds denote the probability that the walker is
on the marked vertex but not in the loop, which follows the curve (22). The
success probability is close to one after $T\approx 100$ steps, in accordance
with (24).

We note that the result (23) holds in the limit of large $N$ and $M$. To
investigate how quickly does the success probability at the optimal time (24)
approaches unity we performed numerical simulations for various values of $N$
and $M$. The simulations indicate that the success probability is essentially
independent of $N$ and with $M$ it scales according to

$P_{m}(T)=1-O\left(\frac{1}{M}\right).$

The results are illustrated in Figure 2.

Figure 2:  Overall success probability of SA as a function of the number of
partitions $M$ for $N=10$ (gray circles), $N=50$ (blue triangles) and $N=100$
(brown diamonds). For a given $N$ and $M$ we evaluate numerically the
evolution of SA for the optimal number of steps $T$ given by (24) and
determine $P_{m}(T)$ from the formula (20). To unravel the scaling of the
success probability we plot $1-P_{m}(T)$ on the log-log scale. Independent of
the value of $N$, the sets of data-points fit well onto the $1/M$ slope
indicated by the red line.

##  IV State transfer

We now turn to the analysis of the STA. There are two possible configurations
— the sender and the receiver are in the same partition or not. Numerical
simulations indicate that for the graph without loops the STA does not work
well. When the sender and the receiver are in the same partition the fidelity
does not surpass 0.25. For the second configuration the first maximum of
fidelity tends to 0.8. Hence, we turn to the graph with loops. Choosing the
initial state of the sender as the equal weight superposition (4), i.e.,
$\mathinner{|{s}\rangle}=\mathinner{|{\Omega_{s}}\rangle}$, the numerical
simulation reveals that the fidelity tends to 1 for the second configuration.
However, when the sender and the receiver are in the same partition the
fidelity is still limited. As we show in Figure 3 it does not surpass 0.35. A
careful analysis would reveal that the culprit are two orthogonal eigenvectors
of the evolution operator of the STA corresponding to the eigenvalue -1, one
having a large overlap with $\mathinner{|{\Omega_{s}}\rangle}$ and the other
one with $\mathinner{|{\Omega_{r}}\rangle}$. In the second configuration this
does not happen, as both $\mathinner{|{\Omega_{s}}\rangle}$ and
$\mathinner{|{\Omega_{r}}\rangle}$ have overlaps with the same eigenvectors of
the evolution operator of the STA. Hence, the absence of an edge between the
sender and the receiver vertex in the first configuration significantly limits
the achievable fidelity when we use the equal weight superposition state
$\mathinner{|{\Omega_{s}}\rangle}$ as the initial state of STA.

Figure 3: The evolution of the fidelity ${\cal F}$ of the state transfer
during $1000$ steps for $N=40$ and $M=100$. Sender and receiver are in the
same part. The initial state $\mathinner{|{s}\rangle}$ is the equal weight
superposition on the sender vertex $\mathinner{|{\Omega_{s}}\rangle}$. We see
that the fidelity does not grow over $0.35$.

We show that the fidelity of STA in the first configuration can be improved
considerably by choosing the initial state $\mathinner{|{s}\rangle}$ as the
loop on the sender vertex. Moreover, we prove that this initial state works
well also in the second configuration. In both configurations the walker will
be with high probability transferred to the loop at the receiver vertex. We
denote this receiver state as $\mathinner{|{r}\rangle}$.

###  IV.1 Sender and receiver in the same partition

Let us first consider the case when the sender and the receiver are in the
same partition of the graph , i.e., they are not connected directly by an
edge. Without loss of generality we consider that they are in the first one.

We begin by constructing the basis of the exact invariant subspace. The
procedure is similar to the one for the SA, but we have to consider two marked
vertices corresponding to the sender $s$ and the receiver $r$. Hence, the
basis states of the form (11), (12), (13) will appear twice - once for $m=s$
and once for $m=r$. In the end we find the following 11 basis vectors

$\displaystyle\mathinner{|{\nu_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{s_{1},s_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{2}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d}}\sum_{\alpha=2}^{M}\sum_{j=1}^{N}\mathinner{|{s_{1},j_{\alpha}}\rangle},$
$\displaystyle\mathinner{|{\nu_{3}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{r_{1},r_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{4}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d}}\sum_{\alpha=2}^{M}\sum_{j=1}^{N}\mathinner{|{r_{1},j_{\alpha}}\rangle},$
$\displaystyle\mathinner{|{\nu_{5}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{N-2}}\sum_{j\neq
s,r}^{N}\mathinner{|{j_{1},j_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{6}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d(N-2)}}\sum_{j\neq
s,r}^{N}\sum_{\alpha=2}^{M}\sum_{k=1}^{N}\mathinner{|{j_{1},k_{\alpha}}\rangle},$
$\displaystyle\mathinner{|{\nu_{7}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d}}\sum_{\alpha=2}^{M}\sum_{j=1}^{N}\mathinner{|{j_{\alpha},s_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{8}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d}}\sum_{\alpha=2}^{M}\sum_{j=1}^{N}\mathinner{|{j_{\alpha},r_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{9}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d(N-2)}}\sum_{j\neq
s,r}^{N}\sum_{\alpha=2}^{M}\sum_{k=1}^{N}\mathinner{|{k_{\alpha},j_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{10}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d(d-N)}}\sum_{\alpha=2}^{M}\sum_{\beta=2,\beta\neq\alpha}^{M}\sum_{j,k=1}^{N}\mathinner{|{j_{\alpha},k_{\beta}}\rangle},$
$\displaystyle\mathinner{|{\nu_{11}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d}}\sum_{\alpha=2}^{M}\sum_{j}^{N}\mathinner{|{j_{\alpha},j_{\alpha}}\rangle}$
(25)

Let us denote the subspace spanned by these vectors as $\cal I$. Clearly, it
contains the initial and the desired target state of the STA
($\mathinner{|{s}\rangle}=\mathinner{|{\nu_{1}}\rangle}$ and
$\mathinner{|{r}\rangle}=\mathinner{|{\nu_{3}}\rangle}$). It can be shown by
direct calculation that it is closed under the action of $\hat{U}_{s,r}$.
However, we will not provide the expression of $\hat{U}_{s,r}$ in this basis
because $\cal I$ can be divided further into two invariant subspaces. This
comes from a fact that the evolution of the STA is invariant with respect to
the exchange of the sender and the receiver vertex. Let us denote the operator
corresponding to this symmetry as $\hat{P}$. Clearly, it holds that

$\hat{P}^{2}=\hat{I},\quad[\hat{P},\hat{U}_{s,r}]=0.$

$\hat{P}$ acts on the basis states (25) as

$\displaystyle\hat{P}\mathinner{|{\nu_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{3}}\rangle},\quad\hat{P}\mathinner{|{\nu_{2}}\rangle}=\mathinner{|{\nu_{4}}\rangle},\quad\hat{P}\mathinner{|{\nu_{7}}\rangle}=\mathinner{|{\nu_{8}}\rangle},$
$\displaystyle\hat{P}\mathinner{|{\nu_{j}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{j}}\rangle},\quad j=5,6,9,10,11.$

Since $\hat{P}$ commutes with $\hat{U}_{s,r}$, they have common eigenvectors.
From $\hat{P}^{2}=\hat{I}$ we see that the spectrum of $\hat{P}$ consists of
two eigenvalues $1$ and $-1$. Hence, the invariant subspace ${\cal I}$ can be
split into two subspaces ${\cal I}_{+}$ and ${\cal I}_{-}$ which correspond to
eigenvalues $1$ and $-1$ of the operator $\hat{P}$. Basis of the invariant
subspace ${\cal I}_{+}$ is spanned by eigenstates denoted as
$\mathinner{|{\sigma_{i}}\rangle}$, $i=1,\ldots,8$ and it has the following
form

$\displaystyle\mathinner{|{\sigma_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{1}}\rangle}+\mathinner{|{\nu_{3}}\rangle}\right),$
$\displaystyle\mathinner{|{\sigma_{2}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{2}}\rangle}+\mathinner{|{\nu_{4}}\rangle}\right),$
$\displaystyle\mathinner{|{\sigma_{3}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{5}}\rangle},$
$\displaystyle\mathinner{|{\sigma_{4}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{6}}\rangle},$
$\displaystyle\mathinner{|{\sigma_{5}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{7}}\rangle}+\mathinner{|{\nu_{8}}\rangle}\right),$
$\displaystyle\mathinner{|{\sigma_{6}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{9}}\rangle},$
$\displaystyle\mathinner{|{\sigma_{7}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{10}}\rangle},$
$\displaystyle\mathinner{|{\sigma_{8}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{11}}\rangle}$

Note that if we perform SA for two marked vertices instead of STA, the
subspace ${\cal I}_{+}$ would be invariant with respect to the search. This is
due to the fact that the initial state of SA algorithm lies within this
subspace. Basis of the invariant subspace ${\cal I}_{-}$ is spanned by
eigenstates denoted as $\mathinner{|{\tau_{i}}\rangle}$, $i=1,\ldots,3$ and it
has the following form

$\displaystyle\mathinner{|{\tau_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{1}}\rangle}-\mathinner{|{\nu_{3}}\rangle}\right),$
$\displaystyle\mathinner{|{\tau_{2}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{2}}\rangle}-\mathinner{|{\nu_{4}}\rangle}\right),$
$\displaystyle\mathinner{|{\tau_{3}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{7}}\rangle}-\mathinner{|{\nu_{8}}\rangle}\right)$

This subspace is needed only in STA since the initial state of SA is
orthogonal to this subspace.

The sender and the receiver states in the new basis read

$\displaystyle\mathinner{|{s}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\sigma_{1}}\rangle}+\mathinner{|{\tau_{1}}\rangle}\right),$
$\displaystyle\mathinner{|{r}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\sigma_{1}}\rangle}-\mathinner{|{\tau_{1}}\rangle}\right).$
(26)

The evolution operator in the new basis is block diagonal, i.e., ${\cal
I}_{i}$ are the invariant subspaces of $\hat{U}_{s,r}$. We find the following
relations for the basis states of ${\cal I}_{+}$

$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left((d-1)\mathinner{|{\sigma_{1}}\rangle}-2\sqrt{d}\mathinner{|{\sigma_{5}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{2}}\rangle}$ $\displaystyle=$
$\displaystyle-\frac{1}{d+1}\left(2\sqrt{d}\mathinner{|{\sigma_{1}}\rangle}+(d-1)\mathinner{|{\sigma_{5}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{3}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left((1-d)\mathinner{|{\sigma_{3}}\rangle}+2\sqrt{d}\mathinner{|{\sigma_{6}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{4}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{d}\mathinner{|{\sigma_{3}}\rangle}+(d-1)\mathinner{|{\sigma_{6}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{5}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left((3-d)\mathinner{|{\sigma_{2}}\rangle}+2\sqrt{2(N-2)}\mathinner{|{\sigma_{4}}\rangle}+2\sqrt{2(d-N)}\mathinner{|{\sigma_{7}}\rangle}+2\sqrt{2}\mathinner{|{\sigma_{8}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{6}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{2(N-2)}\mathinner{|{\sigma_{2}}\rangle}-\left(d-2N+5\right)\mathinner{|{\sigma_{4}}\rangle}+2\sqrt{(d-N)(N-2)}\mathinner{|{\sigma_{7}}\rangle}+2\sqrt{N-2}\mathinner{|{\sigma_{8}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{7}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{2(d-N)}\mathinner{|{\sigma_{2}}\rangle}+2\sqrt{(d-N)(N-2)}\mathinner{|{\sigma_{4}}\rangle}+\left(d-2N-1\right)\mathinner{|{\sigma_{7}}\rangle}+2\sqrt{d-N}\mathinner{|{\sigma_{8}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{8}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{2}\mathinner{|{\sigma_{2}}\rangle}+2\sqrt{N-2}\mathinner{|{\sigma_{4}}\rangle}+2\sqrt{d-N}\mathinner{|{\sigma_{7}}\rangle}-\left(d-1\right)\mathinner{|{\sigma_{8}}\rangle}\right).$
(27)

In the second subspace ${\cal I}_{-}$ the evolution operator acts according to

$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(\left(d-1\right)\mathinner{|{\tau_{1}}\rangle}-2\sqrt{d}\mathinner{|{\tau_{3}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{2}}\rangle}$ $\displaystyle=$
$\displaystyle-\frac{1}{d+1}\left(2\sqrt{d}\mathinner{|{\tau_{1}}\rangle}+\left(d-1\right)\mathinner{|{\tau_{3}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{3}}\rangle}$ $\displaystyle=$
$\displaystyle-\mathinner{|{\tau_{2}}\rangle}.$ (28)

Let us now investigate the dynamics of the STA in the limit of a large graph.
We denote by $\hat{U}_{\pm}$ the restriction of $\hat{U}_{s,r}$ on ${\cal
I}_{\pm}$, and determine the spectrum and eigenvectors of these operators. For
$\hat{U}_{+}$ the results are similar to those for the SA. In the subspace
${\cal I}_{+}$ three relevant eigenvectors remain, as for the others the
overlap with $\mathinner{|{\sigma_{1}}\rangle}$ tends to zero at least as
$O(1/\sqrt{NM})$. The limit form of the relevant eigenvectors is given by

$\displaystyle\mathinner{|{\psi_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{2}{3}}\mathinner{|{\sigma_{1}}\rangle}-\frac{1}{\sqrt{3}}\mathinner{|{\sigma_{7}}\rangle},$
$\displaystyle\mathinner{|{\psi_{2}^{(\pm)}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{6}}\mathinner{|{\sigma_{1}}\rangle}+\frac{1}{\sqrt{3}}\mathinner{|{\sigma_{7}}\rangle}\pm\frac{i}{2}(\mathinner{|{\sigma_{5}}\rangle}-\mathinner{|{\sigma_{2}}\rangle}).$
(29)

The eigenvector $\mathinner{|{\psi_{1}}\rangle}$ corresponds to
$\lambda_{1}=1$. In the case of $\mathinner{|{\psi_{2}^{(\pm)}}\rangle}$ the
eigenvalues have the form

$\lambda_{2}^{(\pm)}=e^{\pm i\omega_{2}}.$

From the characteristic polynomial of $\hat{U}_{+}$ we find that
$\cos\omega_{2}$ is the largest root of the quadratic equation

$x^{2}-\left(1-\frac{N}{d+1}\right)x-\frac{{(d+1)}(N-3)+N-5}{{(d+1)}^{2}}=0,$

which leads us to

$\displaystyle\omega_{2}$ $\displaystyle=$
$\displaystyle\arccos\left(1-\frac{1+NM-\sqrt{N^{2}M^{2}-10NM+8N+9}}{2{(d+1)}}\right)$
(30) $\displaystyle\approx$ $\displaystyle\sqrt{\frac{6}{NM}}.$

In the subspace $\cal I_{-}$ there are two additional relevant eigenvectors in
the asymptotic limit

$\mathinner{|{\psi_{3}^{(\pm)}}\rangle}=\frac{1}{\sqrt{2}}\mathinner{|{\tau_{1}}\rangle}\pm\frac{i}{2}(\mathinner{|{\tau_{2}}\rangle}-\mathinner{|{\tau_{3}}\rangle}).$
(31)

For the last eigenvector of $\hat{U}_{-}$ the overlap with the state
$\mathinner{|{\tau_{1}}\rangle}$ behaves like $O(1/\sqrt{NM})$. The relevant
eigenvalues have the form

$\displaystyle\lambda_{3}^{(\pm)}$ $\displaystyle=$ $\displaystyle e^{\pm
i\omega_{3}},$

with

$\omega_{3}=\arccos\left(1-\frac{1}{{d+1}}\right)\approx\sqrt{\frac{2}{NM}}.$
(32)

Using the results (29), (31) we see that for a large graph the sender and the
receiver states (26) can be decomposed into the eigenvectors of the evolution
operator $\hat{U}_{s,r}$ according to

$\displaystyle\mathinner{|{s}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{3}}\mathinner{|{\psi_{1}}\rangle}+\frac{1}{\sqrt{12}}\left(\mathinner{|{\psi_{2}^{(+)}}\rangle}+\mathinner{|{\psi_{2}^{(-)}}\rangle}\right)+$
$\displaystyle+\frac{1}{2}\left(\mathinner{|{\psi_{3}^{(+)}}\rangle}+\mathinner{|{\psi_{3}^{(-)}}\rangle}\right),$
$\displaystyle\mathinner{|{r}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{3}}\mathinner{|{\psi_{1}}\rangle}+\frac{1}{\sqrt{12}}\left(\mathinner{|{\psi_{2}^{(+)}}\rangle}+\mathinner{|{\psi_{2}^{(-)}}\rangle}\right)-$
$\displaystyle-\frac{1}{2}\left(\mathinner{|{\psi_{3}^{(+)}}\rangle}+\mathinner{|{\psi_{3}^{(-)}}\rangle}\right).$

Hence, the evolution of STA takes place in a five dimensional subspace

$\displaystyle\mathinner{|{\phi(t)}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{3}}\mathinner{|{\psi_{1}}\rangle}+$ (33)
$\displaystyle+\frac{1}{\sqrt{12}}\left(e^{i\omega_{2}t}\mathinner{|{\psi_{2}^{(+)}}\rangle}+e^{-i\omega_{2}t}\mathinner{|{\psi_{2}^{(-)}}\rangle}\right)+$
$\displaystyle+\frac{1}{2}\left(e^{i\omega_{3}t}\mathinner{|{\psi_{3}^{(+)}}\rangle}+e^{-i\omega_{3}t}\mathinner{|{\psi_{3}^{(-)}}\rangle}\right).$

The fidelity of STA can be written as a sum

${\cal F}(t)=|\langle
r|\phi(t)\rangle|^{2}+|\langle\nu_{4}|\phi(t)\rangle|^{2},$ (34)

of probabilities that the walker is in the receiver state
$\mathinner{|{r}\rangle}=\mathinner{|{\nu_{3}}\rangle}$ corresponding to the
loop, or at the receiver vertex but not in the loop, i.e., the state
$\mathinner{|{\nu_{4}}\rangle}$. From the relations (29), (31) and (33) we
find that these probabilities are given by

$\displaystyle|\langle r|\phi(t)\rangle|^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{36}\left(2+\cos\left(\omega_{2}t\right)-3\cos\left(\omega_{3}t\right)\right)^{2},$
(35) $\displaystyle|\langle\nu_{4}|\phi(t)\rangle|^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{24}\left(\sin(\omega_{2}t)-\sqrt{3}\sin(\omega_{3}t)\right)^{2}.$
(36)

From the relations (30), (32) we see that the frequencies are not harmonic,
since for a large graph

$\omega_{2}=\sqrt{3}\omega_{3}.$

The overall fidelity of STA is then given by

$\displaystyle{\cal F}(t)$ $\displaystyle=$
$\displaystyle\frac{1}{36}\left(2+\cos\left(\sqrt{3}\omega_{3}t\right)-3\cos\left(\omega_{3}t\right)\right)^{2}+$
(37)
$\displaystyle+\frac{1}{24}\left(\sin(\sqrt{3}\omega_{3}t)-\sqrt{3}\sin(\omega_{3}t)\right)^{2}.$

The fidelity of STA will not reach one exactly. However, for a large graph the
first maximum of fidelity reaches the value

${\cal F}_{1}\approx 0.94.$ (38)

The number of steps required to reach the first maximum is approximately given
by

$T^{(st)}\approx 2.39\sqrt{NM}.$ (39)

At this time the walker is with high probability in the receiver state
$\mathinner{|{r}\rangle}$.

For illustration we show in Figure 4 the evolution of fidelity for a graph
with $N=40$ and $M=100$.

Figure 4: Fidelity of the state transfer as a function of the number of steps
$t$ for $N=40$ and $M=100$. The sender and the receiver vertices are in the
same partition. Black dots are obtained from the numerical simulation, the
full red curve corresponds to (37). Since the frequencies (30), (32) are not
integer multiples the fidelity behaves an-harmonically. At the time of the
first maximum (39) the walker is with high probability in the receiver state
$\mathinner{|{r}\rangle}$, which is depicted by the blue squares. The
probability to be in the receiver state follows the curve (35) represented by
the red dashed curve. The green diamonds correspond to the probability that
the walker is at the marked vertex but not in the loop, which follows the
curve (36).

The fidelity (38) in the first maximum is reached in the limit of large $N$
and $M$. We have performed numerical simulations to investigate how quickly
does the fidelity at the optimal time (39) approaches the asymptotic value
(38). Similarly to the results for the SA, the simulations indicate that the
fidelity is essentially independent of $N$ and with $M$ it scales according to

${\cal F}(T^{(st)})={\cal F}_{1}-O\left(\frac{1}{M}\right).$

The results are illustrated in Figure 5.

Figure 5:  Overall fidelity of STA as a function of the number of partitions
$M$ for $N=10$ (gray circles), $N=50$ (blue triangles) and $N=100$ (brown
diamonds). The sender and the receiver vertices are in the same partition. For
a given $N$ and $M$ we evaluate numerically the evolution of STA for the
number of steps $T^{(st)}$ needed to reach the first maximum (39) and
determine ${\cal F}(T^{(st)})$ according to (34). To unravel the scaling of
the fidelity we plot ${\cal F}_{1}-{\cal F}(T^{(st)})$ on the log-log scale.
The data-points follow the $1/M$ slope indicated by the red line, with almost
no dependence on $N$.

###  IV.2 Sender and receiver in different partitions

Let us now turn to the case when the sender and the receiver are in different
parts of the complete M-partite graph. Without loss of generality we label the
partition containing the sender as 1 and the partition with the receiver as 2.

The construction of the basis of the invariant subspace $\cal I$ is more
involved, since we have to consider the second partition with the receiver
vertex separately from the rest of the graph. We begin with the states
starting at the sender vertex

$\displaystyle\mathinner{|{\nu_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{s_{1},s_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{2}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{s_{1},r_{2}}\rangle},$
$\displaystyle\mathinner{|{\nu_{3}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{N-1}}\sum_{j\neq
r}^{N}\mathinner{|{s_{1},j_{2}}\rangle},$
$\displaystyle\mathinner{|{\nu_{4}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d-N}}\sum_{\alpha=3}^{M}\sum_{j=1}^{N}\mathinner{|{s_{1},j_{\alpha}}\rangle},$
(40)

which correspond to the loop, edge from the sender to the receiver, equal
weight superposition of all edges from the sender to the remaining vertices in
the second partition, and edges to all remaining vertices. We repeat the same
for the receiver vertex

$\displaystyle\mathinner{|{\nu_{5}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{r_{2},r_{2}}\rangle},$
$\displaystyle\mathinner{|{\nu_{6}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{r_{2},s_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{7}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{N-1}}\sum_{j\neq
s}^{N}\mathinner{|{r_{2},j_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{8}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d-N}}\sum_{\alpha=3}^{M}\sum_{j=1}^{N}\mathinner{|{r_{2},j_{\alpha}}\rangle}$
(41)

Next, we consider the same edges but starting at the non-marked vertices in
the first partition and prepare the following superpositions

$\displaystyle\mathinner{|{\nu_{9}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{N-1}}\sum_{j\neq
s}^{N}\mathinner{|{j_{1},j_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{10}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{N-1}}\sum_{j\neq
s}^{N}\mathinner{|{j_{1},r_{2}}\rangle},$
$\displaystyle\mathinner{|{\nu_{11}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{N-1}\sum_{j\neq s}^{N}\sum_{k\neq
r}^{N}\mathinner{|{j_{1},k_{2}}\rangle},$
$\displaystyle\mathinner{|{\nu_{12}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{(d-N)(N-1)}}\sum_{j\neq
s}^{N}\sum_{\alpha=3}^{M}\sum_{k=1}^{N}\mathinner{|{j_{1},k_{\alpha}}\rangle}.$
(42)

The same procedure is repeated in the second partition

$\displaystyle\mathinner{|{\nu_{13}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{N-1}}\sum_{j\neq
r}^{N}\mathinner{|{j_{2},j_{2}}\rangle},$
$\displaystyle\mathinner{|{\nu_{14}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{N-1}}\sum_{j\neq
r}^{N}\mathinner{|{j_{2},s_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{15}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{N-1}\sum_{j\neq r}^{N}\sum_{k\neq
s}^{N}\mathinner{|{j_{2},k_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{16}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{(d-N)(N-1)}}\sum_{j\neq
r}^{N}\sum_{\alpha=3}^{M}\sum_{k=1}^{N}\mathinner{|{j_{2},k_{\alpha}}\rangle}.$
(43)

Next, we consider the edges leading to the sender or the receiver vertex from
the outside of the first two partitions

$\displaystyle\mathinner{|{\nu_{17}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d-N}}\sum_{\alpha=3}^{M}\sum_{j=1}^{N}\mathinner{|{j_{\alpha},s_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{18}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d-N}}\sum_{\alpha=3}^{M}\sum_{j=1}^{N}\mathinner{|{j_{\alpha},r_{2}}\rangle}.$
(44)

Then we add states corresponding to edges leading to the non-marked vertices
in the first or the second partition from the outside

$\displaystyle\mathinner{|{\nu_{19}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{(d-N)(N-1)}}\sum_{j\neq
s}^{N}\sum_{\alpha=3}^{M}\sum_{k=1}^{N}\mathinner{|{k_{\alpha},j_{1}}\rangle},$
$\displaystyle\mathinner{|{\nu_{20}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{(d-N)(N-1)}}\sum_{j\neq
r}^{N}\sum_{\alpha=3}^{M}\sum_{k=1}^{N}\mathinner{|{k_{\alpha},j_{2}}\rangle}.$
(45)

Finally, we consider all edges between vertices in the rest of the graph, and
all remaining loops

$\displaystyle\mathinner{|{\nu_{21}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{N(d-N)(M-3)}}\sum_{\alpha=3}^{M}\sum_{\beta=3,\beta\neq\alpha}^{M}\sum_{j,k=1}^{N}\mathinner{|{j_{\alpha},k_{\beta}}\rangle},$
$\displaystyle\mathinner{|{\nu_{22}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d-N}}\sum_{\alpha=3}^{M}\sum_{j=1}^{N}\mathinner{|{j_{\alpha},j_{\alpha}}\rangle}$
(46)

It can be shown by direct calculation that the 22 vectors (40)-(46) constitute
an invariant subspace of the STA. To proceed further we employ the symmetry
$\hat{P}$ which switches the sender and the receiver partitions. Its action on
the basis states $\mathinner{|{\nu_{j}}\rangle}$ is given by

$\displaystyle\hat{P}\mathinner{|{\nu_{j}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{j+4}}\rangle},\quad j=1,2,3,4,9,10,11,12,$
$\displaystyle\hat{P}\mathinner{|{\nu_{i}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{i+1}}\rangle},\quad i=17,19,$
$\displaystyle\hat{P}\mathinner{|{\nu_{k}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{k}}\rangle},\quad k=21,22.$

Since $\hat{P}$ commutes with the evolution operator of the STA we can split
$\cal I$ into subspaces ${\cal I}_{\pm}$ corresponding to eigenvalues $\pm 1$.
Subspace ${\cal I}_{+}$ has dimension $12$ and it is spanned by the following
eigenvectors of $\hat{P}$

$\displaystyle\mathinner{|{\sigma_{i}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{i}}\rangle}+\mathinner{|{\nu_{i+4}}\rangle}\right),\quad
i=1,2,3,4$ $\displaystyle\mathinner{|{\sigma_{j}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{j+4}}\rangle}+\mathinner{|{\nu_{j+8}}\rangle}\right),\quad
j=5,6,7,8$ $\displaystyle\mathinner{|{\sigma_{9}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{17}}\rangle}+\mathinner{|{\nu_{18}}\rangle}\right),$
$\displaystyle\mathinner{|{\sigma_{10}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{19}}\rangle}+\mathinner{|{\nu_{20}}\rangle}\right),$
$\displaystyle\mathinner{|{\sigma_{11}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{21}}\rangle},$
$\displaystyle\mathinner{|{\sigma_{12}}\rangle}$ $\displaystyle=$
$\displaystyle\mathinner{|{\nu_{22}}\rangle}$

Subspace ${\cal I}_{-}$ has dimension $10$ and it is spanned by the following
eigenvectors of $\hat{P}$ corresponding to the eigenvalue $-1$

$\displaystyle\mathinner{|{\tau_{i}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{i}}\rangle}-\mathinner{|{\nu_{i+4}}\rangle}\right),\quad
i=1,2,3,4$ $\displaystyle\mathinner{|{\tau_{j}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{j+4}}\rangle}-\mathinner{|{\nu_{j+8}}\rangle}\right),\quad
j=5,6,7,8$ $\displaystyle\mathinner{|{\tau_{9}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{17}}\rangle}-\mathinner{|{\nu_{18}}\rangle}\right),$
$\displaystyle\mathinner{|{\tau_{10}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\nu_{19}}\rangle}-\mathinner{|{\nu_{20}}\rangle}\right)$

In the new basis the sender and the receiver states have the following form

$\displaystyle\mathinner{|{s}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\sigma_{1}}\rangle}+\mathinner{|{\tau_{1}}\rangle}\right),$
$\displaystyle\mathinner{|{r}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\mathinner{|{\sigma_{1}}\rangle}-\mathinner{|{\tau_{1}}\rangle}\right).$
(47)

The evolution operator $\hat{U}_{s,r}$ is block diagonal. We find the
following relations for the basis vectors of ${\cal I}_{+}$

$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(\left(d-1\right)\mathinner{|{\sigma_{1}}\rangle}-2\mathinner{|{\sigma_{2}}\rangle}-2\sqrt{N-1}\mathinner{|{\sigma_{6}}\rangle}-2\sqrt{d-N}\mathinner{|{\sigma_{9}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{2}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-2\mathinner{|{\sigma_{1}}\rangle}+\left(d-1\right)\mathinner{|{\sigma_{2}}\rangle}-2\sqrt{N-1}\mathinner{|{\sigma_{6}}\rangle}-2\sqrt{d-N}\mathinner{|{\sigma_{9}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{3}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-2\sqrt{N-1}\mathinner{|{\sigma_{1}}\rangle}-2\sqrt{N-1}\mathinner{|{\sigma_{2}}\rangle}+\left(d-2N+3\right)\mathinner{|{\sigma_{6}}\rangle}-2\sqrt{(d-N)(N-1)}\mathinner{|{\sigma_{9}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{4}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-2\sqrt{d-N}\mathinner{|{\sigma_{1}}\rangle}-2\sqrt{d-N}\mathinner{|{\sigma_{2}}\rangle}-2\sqrt{(d-N)(N-1)}\mathinner{|{\sigma_{6}}\rangle}-\left(d-2N-1\right)\mathinner{|{\sigma_{9}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{5}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\mathinner{|{\sigma_{3}}\rangle}-\left(d-1\right)\mathinner{|{\sigma_{5}}\rangle}+2\sqrt{N-1}\mathinner{|{\sigma_{7}}\rangle}+2\sqrt{d-N}\mathinner{|{\sigma_{10}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{6}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-\left(d-1\right)\mathinner{|{\sigma_{3}}\rangle}+2\mathinner{|{\sigma_{5}}\rangle}+2\sqrt{N-1}\mathinner{|{\sigma_{7}}\rangle}+2\sqrt{d-N}\mathinner{|{\sigma_{10}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{7}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{N-1}\mathinner{|{\sigma_{3}}\rangle}+2\sqrt{N-1}\mathinner{|{\sigma_{5}}\rangle}-\left(d-2N+3\right)\mathinner{|{\sigma_{7}}\rangle}+2\sqrt{(d-N)(N-1)}\mathinner{|{\sigma_{10}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{8}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{d-N}\mathinner{|{\sigma_{3}}\rangle}+2\sqrt{d-N}\mathinner{|{\sigma_{5}}\rangle}+2\sqrt{(d-N)(N-1)}\mathinner{|{\sigma_{7}}\rangle}+\left(d-2N-1\right)\mathinner{|{\sigma_{10}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{9}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-\left(d-3\right)\mathinner{|{\sigma_{4}}\rangle}+4\sqrt{N-1}\mathinner{|{\sigma_{8}}\rangle}+2\sqrt{2N(M-3)}\mathinner{|{\sigma_{11}}\rangle}+2\sqrt{2}\mathinner{|{\sigma_{12}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{10}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(4\sqrt{N-1}\mathinner{|{\sigma_{4}}\rangle}-\left(d-4N+5\right)\mathinner{|{\sigma_{8}}\rangle}+2\sqrt{2N(N-1)(M-3)}\mathinner{|{\sigma_{11}}\rangle}+2\sqrt{2(N-1)}\mathinner{|{\sigma_{12}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{11}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{2N(M-3)}\mathinner{|{\sigma_{4}}\rangle}+2\sqrt{2N(N-1)(M-3)}\mathinner{|{\sigma_{8}}\rangle}+\left(d-4N-1\right)\mathinner{|{\sigma_{11}}\rangle}+2\sqrt{N(M-3)}\mathinner{|{\sigma_{12}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\sigma_{12}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(2\sqrt{2}\mathinner{|{\sigma_{4}}\rangle}+2\sqrt{2(N-1)}\mathinner{|{\sigma_{8}}\rangle}+2\sqrt{N(M-3)}\mathinner{|{\sigma_{11}}\rangle}-\left(d-1\right)\mathinner{|{\sigma_{12}}\rangle}\right).$

The action of the evolution operator on the basis vectors of ${\cal I}_{-}$
reads

$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(\left(d-1\right)\mathinner{|{\tau_{1}}\rangle}+2\mathinner{|{\tau_{2}}\rangle}+2\sqrt{N-1}\mathinner{|{\tau_{6}}\rangle}-2\sqrt{d-N}\mathinner{|{\tau_{9}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{2}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-2\mathinner{|{\tau_{1}}\rangle}-\left(d-1\right)\mathinner{|{\tau_{2}}\rangle}+2\sqrt{N-1}\mathinner{|{\tau_{6}}\rangle}-2\sqrt{d-N}\mathinner{|{\tau_{9}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{3}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-2\sqrt{N-1}\mathinner{|{\tau_{1}}\rangle}+2\sqrt{N-1}\mathinner{|{\tau_{2}}\rangle}-\left(d-2N+3\right)\mathinner{|{\tau_{6}}\rangle}-2\sqrt{(d-N)(N-1)}\mathinner{|{\tau_{9}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{4}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-2\sqrt{d-N}\mathinner{|{\tau_{1}}\rangle}+2\sqrt{d-N}\mathinner{|{\tau_{2}}\rangle}+2\sqrt{(d-N)(N-1)}\mathinner{|{\tau_{6}}\rangle}-\left(d-2N-1\right)\mathinner{|{\tau_{9}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{5}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-2\mathinner{|{\tau_{3}}\rangle}-\left(d-1\right)\mathinner{|{\tau_{5}}\rangle}-2\sqrt{N-1}\mathinner{|{\tau_{7}}\rangle}+2\sqrt{d-N}\mathinner{|{\tau_{10}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{6}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(\left(d-1\right)\mathinner{|{\tau_{3}}\rangle}+2\mathinner{|{\tau_{5}}\rangle}-2\sqrt{N-1}\mathinner{|{\tau_{7}}\rangle}+2\sqrt{d-N}\mathinner{|{\tau_{10}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{7}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-2\sqrt{N-1}\mathinner{|{\tau_{3}}\rangle}+2\sqrt{N-1}\mathinner{|{\tau_{5}}\rangle}+\left(d-2N+3\right)\mathinner{|{\tau_{7}}\rangle}+2\sqrt{(d-N)(N-1)}\mathinner{|{\tau_{10}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{8}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1}\left(-2\sqrt{d-N}\mathinner{|{\tau_{3}}\rangle}+2\sqrt{d-N}\mathinner{|{\tau_{5}}\rangle}-2\sqrt{(d-N)(N-1)}\mathinner{|{\tau_{7}}\rangle}+\left(d-2N-1\right)\mathinner{|{\tau_{10}}\rangle}\right),$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{9}}\rangle}$ $\displaystyle=$
$\displaystyle-\mathinner{|{\tau_{4}}\rangle},$
$\displaystyle\hat{U}_{s,r}\mathinner{|{\tau_{10}}\rangle}$ $\displaystyle=$
$\displaystyle-\mathinner{|{\tau_{8}}\rangle}.$ (48)

To investigate the dynamics of STA in more detail we again turn to the limit
of a large graph. We denote by $\hat{U}_{\pm}$ the restriction of
$\hat{U}_{s,r}$ on ${\cal I}_{\pm}$. For $\hat{U}_{+}$ there are three
eigenstates which have non-vanishing overlap with the state
$\mathinner{|{\sigma_{1}}\rangle}$, namely

$\displaystyle\mathinner{|{\psi_{1}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{\sqrt{3}}{2}\mathinner{|{\sigma_{1}}\rangle}-\frac{1}{2\sqrt{3}}\mathinner{|{\sigma_{2}}\rangle}-\frac{1}{\sqrt{6}}\mathinner{|{\sigma_{11}}\rangle},$
(49) $\displaystyle\mathinner{|{\psi_{2}^{(\pm)}}\rangle}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{8}}(\mathinner{|{\sigma_{1}}\rangle}+\mathinner{|{\sigma_{2}}\rangle})\pm\frac{i}{2}(\mathinner{|{\sigma_{9}}\rangle}-\mathinner{|{\sigma_{4}}\rangle})+\frac{1}{2}\mathinner{|{\sigma_{11}}\rangle}.$

Note that for the other eigenstates the overlap with
$\mathinner{|{\sigma_{1}}\rangle}$ decreases at least as $O(1/\sqrt{NM})$.
Turning to the eigenvalues, we find that the eigenvector
$\mathinner{|{\psi_{1}}\rangle}$ has eigenvalue $\lambda_{1}=1$. From the
characteristic polynomial of $\hat{U}_{+}$ we find that the eigenvalues of
$\mathinner{|{\psi_{2}^{(\pm)}}\rangle}$ have the form
$\lambda_{2}^{(\pm)}=e^{\pm i\omega_{2}}$, where $\cos\omega_{2}$ is the
largest root of the cubic equation

$\displaystyle 0$ $\displaystyle=$ $\displaystyle
x^{3}-\left(1-\frac{N+2}{d+1}\right)x^{2}-\frac{{(d+1)}(N-1)-N+5}{{(d+1)}^{2}}x+$
$\displaystyle+\frac{NM-4}{{(d+1)}^{2}}.$

We find that it has the following asymptotic form

$\omega_{2}\approx\arccos\left(1-\frac{4}{NM}\right)\approx
2\sqrt{\frac{2}{NM}}.$ (50)

Considering the subspace ${\cal I}_{-}$, there are two eigenvectors which
remain relevant in the asymptotic limit (for the others the overlap with
$\mathinner{|{\tau_{1}}\rangle}$ vanishes at least as $O(1/\sqrt{NM})$),
namely

$\mathinner{|{\psi_{3}^{(\pm)}}\rangle}=\frac{1}{\sqrt{2}}\mathinner{|{\tau_{1}}\rangle}\pm\frac{i}{2}(\mathinner{|{\tau_{9}}\rangle}-\mathinner{|{\tau_{4}}\rangle}).$
(51)

The eigenvalues are $\lambda_{3}^{(\pm)}=e^{\pm i\omega_{3}}$, where
$\cos\omega_{3}$ is the largest root of the quartic equation

$\displaystyle 0$ $\displaystyle=$ $\displaystyle
x^{4}+\frac{N-2}{d+1}x^{3}-\left(1-\frac{NM}{{(d+1)}^{2}}\right)x^{2}-$
$\displaystyle-\frac{(N-2)(d-1)}{{(d+1)}^{2}}x+\frac{N(M-2)}{{(d+1)}^{2}}.$

Its asymptotic form is given by

$\omega_{3}\approx\arccos\left(1-\frac{1}{NM}\right)\approx\sqrt{\frac{2}{NM}}.$
(52)

From (49), (51) we see that for a large graph the sender and the receiver
states can be decomposed into the eigenvectors of the evolution operator
$\hat{U}_{s,r}$ according to

$\displaystyle\mathinner{|{s}\rangle}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{3}{8}}\mathinner{|{\psi_{1}}\rangle}+\frac{1}{4}\left(\mathinner{|{\psi_{2}^{(+)}}\rangle}+\mathinner{|{\psi_{2}^{(-)}}\rangle}\right)+$
$\displaystyle+\frac{1}{2}\left(\mathinner{|{\psi_{3}^{(+)}}\rangle}+\mathinner{|{\psi_{3}^{(-)}}\rangle}\right),$
$\displaystyle\mathinner{|{r}\rangle}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{3}{8}}\mathinner{|{\psi_{1}}\rangle}+\frac{1}{4}\left(\mathinner{|{\psi_{2}^{(+)}}\rangle}+\mathinner{|{\psi_{2}^{(-)}}\rangle}\right)-$
$\displaystyle-\frac{1}{2}\left(\mathinner{|{\psi_{3}^{(+)}}\rangle}+\mathinner{|{\psi_{3}^{(-)}}\rangle}\right).$

The evolution of STA takes place in a five dimensional subspace

$\displaystyle\mathinner{|{\phi(t)}\rangle}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{3}{8}}\mathinner{|{\psi_{1}}\rangle}+$ (53)
$\displaystyle+\frac{1}{4}\left(e^{i\omega_{2}t}\mathinner{|{\psi_{2}^{(+)}}\rangle}+e^{-i\omega_{2}t}\mathinner{|{\psi_{2}^{(-)}}\rangle}\right)+$
$\displaystyle+\frac{1}{2}\left(e^{i\omega_{3}t}\mathinner{|{\psi_{3}^{(+)}}\rangle}+e^{-i\omega_{3}t}\mathinner{|{\psi_{3}^{(-)}}\rangle}\right).$

The fidelity of STA after $t$ steps (9) can be expressed as a sum

${\cal F}(t)=\sum_{j=5}^{8}|\langle\nu_{j}|\phi(t)\rangle|^{2}.$ (54)

From (49), (51) and (53) we find that the transfer probabilities to individual
states $\mathinner{|{\nu_{j}}\rangle}$ are given by

$\displaystyle|\langle\nu_{5}|\phi(t)\rangle|^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{64}\left(3+\cos\left(\omega_{2}t\right)-4\cos\left(\omega_{3}t\right)\right)^{2},$
$\displaystyle|\langle\nu_{6}|\phi(t)\rangle|^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{16}\sin^{4}\left(\frac{\omega_{2}t}{2}\right),$
$\displaystyle|\langle\nu_{7}|\phi(t)\rangle|^{2}$ $\displaystyle=$
$\displaystyle 0,$ $\displaystyle|\langle\nu_{8}|\phi(t)\rangle|^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{32}\left(\sin(\omega_{2}t)-2\sin(\omega_{3}t)\right)^{2}.$
(55)

From the asymptotic expansions (50), (52) we see that for a large graph the
frequencies are harmonic

$\omega_{2}=2\omega_{3}.$

Hence, we find that with probability

$|\langle r|\phi(t)\rangle|^{2}=\sin^{8}{\left(\frac{\omega_{3}t}{2}\right)},$
(56)

the walker is in the receiver state
$\mathinner{|{r}\rangle}=\mathinner{|{\nu_{5}}\rangle}$, i.e., at the receiver
vertex in the loop, and with probability

$\displaystyle|\langle\nu_{6}|\phi(t)\rangle|^{2}+|\langle\nu_{8}|\phi(t)\rangle|^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sin^{2}\left(\omega_{3}t\right)\sin^{4}\left(\frac{\omega_{3}t}{2}\right)+$
(57) $\displaystyle+\frac{1}{16}\sin^{4}\left(\omega_{3}t\right),$

it is at the receiver vertex but not in the loop. Overall, the fidelity of STA
for a large graph is given by

${\cal F}(t)=\sin^{4}\left(\frac{\omega_{3}t}{2}\right).$ (58)

We conclude that the state transfer is achieved after $T^{(st)}$ steps, where

$T^{(st)}\approx\pi\sqrt{\frac{NM}{2}}.$ (59)

At this time the walker is with high probability in the receiver state
$\mathinner{|{r}\rangle}$.

For illustration we show in Figure 6 the evolution of fidelity for a graph
with $N=40$ and $M=100$.

Figure 6: Overall fidelity of the STA as a function of the number of steps $t$
for $N=40$ and $M=100$. The sender and the receiver vertices are in different
partitions. Black dots are obtained from the numerical simulation, the full
red curve corresponds to (58). The walker is transferred to the receiver
vertex with fidelity close to one after $T^{(st)}\approx 140$ steps, in
accordance with (59). At this time the walker is found with high probability
in the loop (blue squares), as follows from the analytical prediction (56)
depicted by the red dashed curve. Green diamonds represent the probability
that the walker is at the marked vertex but not in the loop, which follows the
curve (57).

The result (58) holds in the limit of large $N$ and $M$. To investigate how
quickly does the fidelity at the optimal time (59) approaches unity we
performed numerical simulations for various values of $N$ and $M$. The
simulations indicate that the fidelity can be again estimated by

${\cal F}(T^{(st)})=1-O\left(\frac{1}{M}\right),$

however, the dependence on $N$ is more complex than for search and STA with
the sender and the receiver in the same partition. The results are illustrated
in Figure 7.

Figure 7:  Overall fidelity of STA as a function of the number of partitions
$M$ for $N=10$ (gray circles), $N=50$ (blue triangles) and $N=100$ (brown
diamonds). The sender and the receiver vertices are in different partitions.
For a given $N$ and $M$ we evaluate numerically the evolution of STA for the
optimal number of steps $T^{(st)}$ given by (59) and determine ${\cal
F}(T^{(st)})$ from the formula (54). To unravel the scaling of the fidelity we
plot $1-{\cal F}(T^{(st)})$ on the log-log scale. The full red line has the
$1/M$ slope, while the dashed red line follows $1/M^{2}$. The plot indicates
that $O(1/M)>1-{\cal F}(T^{(st)})>O(1/M^{2})$, and that the fluctuations
decrease with increasing $N$.

##  V State transfer algorithm with an active switch

As we have shown in the previous section, the STA does not perform with unit
fidelity on the complete $M$-partite graph with loops when the sender and the
receiver are in the same partition. Note that if the receiver does not know
the position of the sender, the measurement should be made at the optimal time
(59) corresponding to the more likely configuration, i.e., when the sender and
the receiver are in different partition. This reduces the fidelity of STA
further to approximately 0.91.

To fix this issue we introduce an STA where the sender and the receiver will
actively switch the local coins at their vertices. We use that for
$M\to\infty$ and $N\to\infty$ the state of the SA (19) on the complete
$M$-partite graph with loops evolves periodically from the initial state
$\mathinner{|{\Omega}\rangle}$ to the target state
$\mathinner{|{\nu_{1}}\rangle}$ and back with a period of $2T$, where $T$ is
the run-time of the SA given by (24). Hence, we can perform the state transfer
in the following way. The sender initializes the walk on its vertex in the
target state of the search algorithm
$\mathinner{|{s}\rangle}=\mathinner{|{\nu_{1}}\rangle}$ which corresponds to
the loop at the sender vertex. For the first $T$ steps only the sender will
use the marked coin, i.e., the walk will evolve according to the operator
$\hat{U}_{s}$ of the SA with the marked vertex $s$. The sender state
$\mathinner{|{s}\rangle}$ will evolve close to the equal weight superposition
$\mathinner{|{\Omega}\rangle}$, i.e., the initial state of the SA (6).
Afterwards, the sender switches off the marked coin, and the receiver switches
it on, i.e., the walk evolves according to the operator $\hat{U}_{r}$ of the
SA with the marked vertex $r$. After another $T$ steps the walk will evolve
close to the state $\mathinner{|{r}\rangle}$ corresponding to the loop at the
receiver vertex, and the receiver will detect it with high probability. In
this way we can achieve state transfer with high fidelity on the complete
$M$-partite graph with loops irrespective of the relative position of the
sender and the receiver.

For illustration, we show in Figure 8 the comparison of the fidelities of
state transfer of the original STA and the STA with an active switch when the
sender and the receiver are in the same partition. We see that the STA with an
active switch takes more steps, however, the fidelity reaches one.

Figure 8: Comparison of fidelity of the original STA (37) (red diamonds) with
fidelity of the STA with an active switch (black dots) as a function of the
number of steps $t$ for $N=40$ and $M=100$. The sender and the receiver
vertices are in the same partition. The switch between $\hat{U}_{s}$ and
$\hat{U}_{r}$ is done after $T\approx 100$ steps, corresponding to the run-
time of the SA.

Let us now formalize the STA with an active switch on more general graphs.
Namely, we consider graphs where the optimal number of steps $T$ of the SA
does not depend on the position of the marked vertex $m$. The steps of the STA
with an active switch can be formulated as follows:

  1. 1.

Sender initializes the walk at its vertex in the state
$\mathinner{|{s}\rangle}$ corresponding to the target state of the SA with the
marked vertex $s$.

  2. 2.

Sender uses marked coin on his vertex for $T$ steps, i.e., the evolution
operator $\hat{U}_{s}$ is applied $T$-times.

  3. 3.

Receiver uses marked coin on his vertex for $T$ steps, i.e., the evolution
operator $\hat{U}_{r}$ is applied $T$-times.

  4. 4.

Receiver measures the walk at its vertex.

We show that the fidelity of the STA with an active switch can be lower
bounded using only the results from the SA with one marked vertex, which is
not true for the original STA. As we have seen in the case of the complete
$M$-partite graph with loops, the SA does not tell us anything about the
evolution of the STA in the subspace ${\cal I}_{-}$.

To derive the lower bound of fidelity of the STA with an active switch we
first introduce two conditions on the SA. The first condition is related to
target state of the SA. We suppose that after $T$ steps the state of the SA
can be expressed in the form

$\displaystyle\mathinner{|{\phi(T)}\rangle}=\hat{U}_{m}^{T}\mathinner{|{\Omega}\rangle}=\alpha_{m}\mathinner{|{m}\rangle}+\epsilon_{m}\mathinner{|{\eta_{m}}\rangle}$
(60)

for every marked vertex $m$ in the graph. Here
$\mathinner{|{m}\rangle}\in{\cal H}_{m}$ is the target state of the SA, i.e.,
if the walk is in this state the success probability of finding the marked
vertex $m$ is exactly $1$, and $\mathinner{|{\eta_{m}}\rangle}$ is a unit
vector orthogonal to $\mathinner{|{m}\rangle}$. Complex numbers $\alpha_{m}$
and $\epsilon_{m}$ are such that $|\alpha_{m}|$ is close to one and
$|\epsilon_{m}|\ll 1$. $|\alpha_{m}|^{2}$ is closely related to the success
probability of the SA, since

$\displaystyle P_{m}(T)$ $\displaystyle=$ $\displaystyle|\langle
m|\phi(T)\rangle|^{2}+\sum_{\begin{subarray}{c}\mathinner{|{j}\rangle}\in{\cal
H}_{m}\\\ \langle j|m\rangle=0\end{subarray}}|\langle j|\phi(T)\rangle|^{2}$
(61) $\displaystyle=$
$\displaystyle|\alpha_{m}|^{2}+|\epsilon_{m}|^{2}\sum_{\begin{subarray}{c}\mathinner{|{j}\rangle}\in{\cal
H}_{m}\\\ \langle j|m\rangle=0\end{subarray}}|\langle j|\eta_{m}\rangle|^{2}.$

Note that if the vector $\mathinner{|{\eta_{m}}\rangle}$ does not have a
support at the marked vertex then the success probability is exactly
$|\alpha_{m}|^{2}$. From the relation (60) for $m=s$ we express the initial
state of the STA with an active switch as

$\mathinner{|{s}\rangle}=\frac{1}{\alpha_{s}}\left(\hat{U}_{s}^{T}\mathinner{|{\Omega}\rangle}-\epsilon_{s}\mathinner{|{\eta_{s}}\rangle}\right).$
(62)

The second condition describes the periodicity of the SA. Namely, we suppose
that after $2T$ steps the state of the SA can be written in the form

$\displaystyle\hat{U}_{m}^{2T}\mathinner{|{\Omega}\rangle}=\beta_{m}\mathinner{|{\Omega}\rangle}+\delta_{m}\mathinner{|{\rho_{m}}\rangle},$
(63)

where $\mathinner{|{\rho_{m}}\rangle}$ is a unit vector orthogonal to the
initial state $\mathinner{|{\Omega}\rangle}$. $\beta_{m}$ and $\delta_{m}$ are
again complex numbers where $|\beta_{m}|^{2}$ is the return probability. We
assume that it is close to one and that $|\delta_{m}|\ll 1$. In other words,
this condition says that if we double the number of steps the SA returns close
to its initial state.

Assuming that the SA satisfies the conditions (60) and (63) we write the final
state of the STA with an active switch in the following manner

$\displaystyle\hat{U}_{r}^{T}\hat{U}_{s}^{T}|s\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\alpha_{s}}\hat{U}_{r}^{T}\hat{U}_{s}^{T}\left(\hat{U}_{s}^{T}|\Omega\rangle-\epsilon_{s}|\eta_{s}\rangle\right)$
(64) $\displaystyle=$
$\displaystyle\frac{1}{\alpha_{s}}\hat{U}_{r}^{T}\left(\hat{U}_{s}^{2T}|\Omega\rangle-\epsilon_{s}\hat{U}_{s}^{T}|\eta_{s}\rangle\right)$
$\displaystyle=$
$\displaystyle\frac{1}{\alpha_{s}}\hat{U}_{r}^{T}\left(\beta_{s}|\Omega\rangle+\delta_{s}|\rho_{s}\rangle-\epsilon_{s}\hat{U}_{s}^{T}|\eta_{s}\rangle\right)$
$\displaystyle=$
$\displaystyle\frac{\alpha_{r}}{\alpha_{s}}\beta_{s}|r\rangle+\frac{\beta_{s}}{\alpha_{s}}\epsilon_{r}|\eta_{r}\rangle+\frac{\delta_{s}}{\alpha_{s}}\hat{U}_{r}^{T}|\rho_{s}\rangle-$
$\displaystyle-\frac{\epsilon_{s}}{\alpha_{s}}\hat{U}_{r}^{T}\hat{U}_{s}^{T}|\eta_{s}\rangle$

where we have first used (62), then (63) and finally we again use (62) but for
the state $|r\rangle$. The fidelity of STA with an active switch can be
expressed as

${\cal F}=\left|\left\langle
r\left|\hat{U}_{r}^{T}\hat{U}_{s}^{T}\right|s\right\rangle\right|^{2}+\sum_{\begin{subarray}{c}\mathinner{|{j}\rangle}\in{\cal
H}_{r}\\\ \langle j|r\rangle=0\end{subarray}}\left|\left\langle
j\left|\hat{U}_{r}^{T}\hat{U}_{s}^{T}\right|s\right\rangle\right|^{2}.$

Hence, the square root of the fidelity can be bounded from below by

$\sqrt{\cal F}\geq\left|\left\langle
r\left|\hat{U}_{r}^{T}\hat{U}_{s}^{T}\right|s\right\rangle\right|.$

To approximate $\left|\left\langle
r\left|\hat{U}_{r}^{T}\hat{U}_{s}^{T}\right|s\right\rangle\right|$ we use the
following estimates

$\displaystyle\left|\left\langle
r\left|\hat{U}_{r}^{T}\right|\rho_{s}\right\rangle\right|$ $\displaystyle\leq$
$\displaystyle|||r\rangle||\left|\left|\hat{U}_{r}^{T}\left|\rho_{s}\right\rangle\right|\right|=|||r\rangle||\left|\left|\left|\rho_{s}\right\rangle\right|\right|=1,$
$\displaystyle\left|\left\langle
r\left|\hat{U}_{r}^{T}\hat{U}_{s}^{T}\right|\eta_{s}\right\rangle\right|$
$\displaystyle\leq$
$\displaystyle|||r\rangle||\left|\left|\hat{U}_{r}^{T}\hat{U}_{s}^{T}\left|\eta_{s}\right\rangle\right|\right|=1,$
(65)

which follow from the Cauchy–Schwarz inequality and the unitarity of evolution
operator $\hat{U}_{m}$. Combining (64) with (65) we find the lower bound for
the square root of the fidelity which reads

$\displaystyle\sqrt{\cal F}$ $\displaystyle\geq$
$\displaystyle\left|\frac{\alpha_{r}}{\alpha_{s}}\beta_{s}\langle
r|r\rangle+\frac{\beta_{s}}{\alpha_{s}}\epsilon_{r}\langle
r|\eta_{r}\rangle+\frac{\delta_{s}}{\alpha_{s}}\left\langle
r\left|\hat{U}_{r}^{T}\right|\rho_{s}\right\rangle-\frac{\epsilon_{s}}{\alpha_{s}}\left\langle
r\left|\hat{U}_{r}^{T}\hat{U}_{s}^{T}\right|\eta_{s}\right\rangle\right|$ (66)
$\displaystyle\geq$
$\displaystyle\frac{|\alpha_{r}|}{|\alpha_{s}|}|\beta_{s}|-\frac{|\delta_{s}|}{|\alpha_{s}|}\left|\left\langle
r\left|\hat{U}_{r}^{T}\right|\rho_{s}\right\rangle\right|-\frac{|\epsilon_{s}|}{|\alpha_{s}|}\left|\left\langle
r\left|\hat{U}_{r}^{T}\hat{U}_{s}^{T}\right|\eta_{s}\right\rangle\right|$
$\displaystyle\geq$
$\displaystyle\frac{|\alpha_{r}|}{|\alpha_{s}|}|\beta_{s}|-\frac{|\delta_{s}|}{|\alpha_{s}|}-\frac{|\epsilon_{s}|}{|\alpha_{s}|}.$

It is easy to see from (66) that if $|\alpha_{s}|$, $|\alpha_{r}|$ and
$|\beta_{s}|$ are close to one and if $|\epsilon_{s}|\ll 1$ and
$|\delta_{s}|\ll 1$ then the fidelity of the state transfer is close to one.

The result derived above guarantees that if the SA succeeds with unit
probability in the limit of a large graph, then the STA with an active switch
achieves perfect state transfer. Moreover, even for small graphs the STA with
an active switch can actually achieve very good fidelity. For illustration we
have investigated numerically the STA with an active switch on the complete
$M$-partite graph for various values of $N$ and $M$. The results are similar
to those presented in Figure 7.

Figure 9:  Overall fidelity of STA with an active switch as a function of the
number of partitions $M$ for $N=10$ (gray circles), $N=50$ (blue triangles)
and $N=100$ (brown diamonds). The walk is initialized at the sender vertex in
the loop. For a given $N$ and $M$ we evaluate numerically the evolution
operator $\hat{U}_{s}$ of SA with marked vertex $s$, apply it for the optimal
number of steps $T$ given by (24). Then we repeat the same with $\hat{U}_{r}$.
Finally, we make a measurement at the receiver vertex $r$ and determine the
fidelity ${\cal F}(2T)$. To unravel the scaling of the fidelity we plot
$1-{\cal F}(2T)$ on the log-log scale. The full red line has the $1/M$ slope,
while the dashed red line follows $1/M^{2}$. The plot indicates that
$O(1/M)>1-{\cal F}(2T)>O(1/M^{2})$.

##  VI Conclusion

We have investigated search and state transfer algorithms based on the coined
quantum walks, focusing on the complete $M$-partite graph. It was shown that
adding loops to all vertices increases the success probability of the SA close
to one for a large graph. This is by now a standard method [9, 10, 26, 27, 28,
29, 30] which has a potential to significantly improve the success probability
on a much broader class of graphs [31]. However, the analysis of the SA does
not provide the necessary insight for the investigation of the STA, as the
latter requires larger invariant subspace. As we have seen on the example of
the complete $M$-partite graph with loops, success probability of the SA close
to one does not guarantee STA with unit fidelity. The reason is that the
phases of the relevant eigenvalues of the evolution operator are not harmonic
when the sender and the receiver are in the same partition. Although the
modification of the initial state has improved the fidelity considerably, the
absence of an edge between the sender and the receiver vertex on the complete
$M$-partite graph does not allow for perfect state transfer. It would be
interesting to find out if this occurs for different graphs as well.

In the present paper we have limited our investigations to the case where all
partitions have the same number of vertices $N$. This enabled us to find exact
invariant subspaces for SA and STA which have dimensions independent of $N$
and $M$. Allowing the partitions with different number of vertices appears to
break this feature, and the dimension of the invariant subspace is likely to
depend on $M$. We plan to investigate this behaviour in the near future for
small values of $M$.

To improve the STA on the complete $M$-partite graph we have introduced the
STA with an active switch. This approach allows for perfect state transfer in
the limit of a large graph in both configurations of the sender and the
receiver vertex. The trade-off is that the STA with an active switch requires
more steps than the original STA. Indeed, when the sender and the receiver are
in different partitions, the number of steps for the original STA to reach
unit fidelity is twice the number of steps of the search for two vertices. On
the other hand, STA with an active switch takes twice the number of steps of
the SA for one vertex. Since the search for two vertices is $\sqrt{2}$ faster
than the search for one vertex, the STA with an active switch is slower by the
same factor.

The main advantages of the STA with an active switch are that it can be
applied to other graphs, and that its fidelity can be estimated based on the
analysis of the SA for one marked vertex alone. In this way we can achieve
state transfer with high fidelity on graphs, where the SA for one marked
vertex has success probability close to one and evolves almost periodically.
For many symmetric graphs these conditions are well satisfied, at least in the
limit of a large graph. Moreover, exact periodicity of the Grover walk (i.e.,
without the marked vertex) was recently investigated for various graphs [50,
51, 52]. It would be of interest to determine if SA works on these graphs as
well.

The STA with an active switch also has some disadvantages. As we have already
mentioned, it will have a longer run-time in comparison with the original STA.
Moreover, the sender and the receiver have to actively switch off or on their
marked coins. However, this is only a local operations, and since we consider
that the run-time of the SA is independent of the location of the marked
vertex, the time of the switching is determined solely by the global
properties of the graph, e.g., the number of vertices. Hence, the sender and
the receiver still do not need to know each other’s position. Finally, we have
to determine the target state of SA, which serves as the initial state for the
STA with an active switch. Nevertheless, for highly symmetric graphs this
target state is usually either the equal weight superposition of all direction
or the state corresponding to a loop.

###### Acknowledgements.

Both authors received support from the Czech Grant Agency (GAČR) under grant
No. 17-00844S and from MSMT RVO 14000. This publication was funded by the
project “Centre for Advanced Applied Sciences”, Registry No.
CZ.$02.1.01/0.0/0.0/16\\_019/0000778$, supported by the Operational Programme
Research, Development and Education, co-financed by the European Structural
and Investment Funds and the state budget of the Czech Republic.

## References

  * Aharonov  _et al._ [1993] Y. Aharonov, L. Davidovich, and N. Zagury, Phys. Rev. A 48, 1687 (1993).
  * Meyer [1996] D. A. Meyer, J. Stat. Phys. 85, 551 (1996).
  * Farhi and Gutmann [1998] E. Farhi and S. Gutmann, Phys. Rev. A 58, 915 (1998).
  * Aharonov  _et al._ [2001] D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, in Proceedings of the 33rd STOC (ACM Press, New York, 2001) , 50 (2001).
  * Grover [1997] L. K. Grover, Phys. Rev. Lett. 79, 325 (1997).
  * Childs and Goldstone [2004] A. M. Childs and J. Goldstone, Phy. Rev. A 70, 022314 (2004).
  * Ambainis  _et al._ [2001] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous, in  _STOC’01: Proc. of the 33rd annual ACM Symposium on Theory of Computing_ (2001) pp. 37–49.
  * Shenvi  _et al._ [2003] N. Shenvi, J. Kempe, and K. B. Whaley, Phys. Rev. A 67, 052307 (2003).
  * Ambainis  _et al._ [2005] A. Ambainis, J. Kempe, and A. Rivosh, in  _Proc. 16th ACM-SIAM symposium on Discrete algorithms_ (Society for Industrial and Applied Mathematics, 2005) pp. 1099–1108.
  * Potoček  _et al._ [2009] V. Potoček, A. Gábris, T. Kiss, and I. Jex, Phys. Rev. A 79, 012325 (2009).
  * Hein and Tanner [2009a] B. Hein and G. Tanner, J. Phys. A 42, 085303 (2009a).
  * Hillery  _et al._ [2003] M. Hillery, J. Bergou, and E. Feldman, Phys. Rev. A 68, 032314 (2003).
  * Feldman and Hillery [2004] E. Feldman and M. Hillery, Phys. Lett. A 324, 277 (2004).
  * Feldman and Hillery [2007] E. Feldman and M. Hillery, J. Phys. A: Math. Theor. 40, 11343 (2007).
  * Andrade and da Luz [2009] F. M. Andrade and M. G. E. da Luz, Phys. Rev. A 80, 052301 (2009).
  * Venancio  _et al._ [2013] B. F. Venancio, F. M. Andrade, and M. G. E. da Luz, J. Phys. A 46, 165302 (2013).
  * Reitzner  _et al._ [2009] D. Reitzner, M. Hillery, E. Feldman, and V. Bužek, Phys. Rev. A 79, 012323 (2009).
  * Janmark  _et al._ [2014] J. Janmark, D. A. Meyer, and T. G. Wong, Phys. Rev. Lett. 112, 210502 (2014).
  * Novo  _et al._ [2015] L. Novo, S. Chakraborty, M. Mohseni, H. Neven, and Y. Omar, Sci. Rep. 5, 13304 (2015).
  * Meyer and Wong [2015] D. A. Meyer and T. G. Wong, Phys. Rev. Lett. 114, 110503 (2015).
  * Chakraborty  _et al._ [2016] S. Chakraborty, L. Novo, A. Ambainis, and Y. Omar, Phys. Rev. Lett. 116, 100501 (2016).
  * Albert and Barabási [2002] R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
  * Osada  _et al._ [2020] T. Osada, B. Coutinho, Y. Omar, K. Sanaka, W. J. Munro, and K. Nemoto, Phys. Rev. A 101, 022310 (2020).
  * Chakraborty  _et al._ [2020] S. Chakraborty, L. Novo, and J. Roland, Phys. Rev. A 102, 032214 (2020).
  * Brassard  _et al._ [2002] G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Contemp. Math. 350, 53 (2002).
  * Wong [2015] T. G. Wong, J. Phys. A 48, 435304 (2015).
  * Wong [2018] T. G. Wong, Quantum Inf. Process. 17, 68 (2018).
  * Rhodes and Wong [2019] M. L. Rhodes and T. G. Wong, Phys. Rev. A 100, 042303 (2019).
  * Rhodes and Wong [2020] M. L. Rhodes and T. G. Wong, Quantum Inf. Process. 19, 334 (2020).
  * Chiang [2020] C. Chiang, Quantum Inf. Process. 19, 364 (2020).
  * Høyer and Zhan [2020] P. Høyer and Y. Zhan, arXiv:2002.11234 (2020).
  * Bose [2003] S. Bose, Phys. Rev. Lett. 91, 207901 (2003).
  * Kurzynski and Wojcik [2011] P. Kurzynski and A. Wojcik, Phys. Rev. A 83, 062315 (2011).
  * Yalcinkaya and Gedik [2015] I. Yalcinkaya and Z. Gedik, J. Phys. A 48, 225302 (2015).
  * Zhan  _et al._ [2014] X. Zhan, H. Qin, Z. H. Bian, J. Li, and P. Xue, Phys. Rev. A 90, 012331 (2014).
  * Shang  _et al._ [2018] Y. Shang, Y. Wang, M. Li, and R. Q. Lu, EPL 124, 60009 (2018).
  * Chen  _et al._ [2019] X. B. Chen, Y. L. Wang, G. Xu, and Y. X. Yang, IEEE ACCESS 7, 13634 (2019).
  * Hein and Tanner [2009b] B. Hein and G. Tanner, Phys. Rev. Lett. 103, 260501 (2009b).
  * Kendon and Tamon [2011] V. M. Kendon and C. Tamon, J. Comput. Theor. Nanosci. 8, 422 (2011).
  * Barr  _et al._ [2014] K. Barr, T. Proctor, D. Allen, and V. M. Kendon, Quantum Inf. Comput. 14, 417 (2014).
  * Štefaňák and Skoupý [2016] M. Štefaňák and S. Skoupý, Phys. Rev. A 94, 022301 (2016).
  * Štefaňák and Skoupý [2017] M. Štefaňák and S. Skoupý, Quantum Inf. Process. 16, 72 (2017).
  * Zhan [2019] H. Zhan, Quantum Inf. Process. 18, 369 (2019).
  * Cao  _et al._ [2019] W. F. Cao, Y. G. Yang, D. Li, J. R. Dong, Y. H. Zhou, and W. M. Shi, Mod. Phys. Lett. A 34, 1950317 (2019).
  * Reitzner  _et al._ [2017] D. Reitzner, M. Hillery, and D. Koch, Phys. Rev. A 96, 032323 (2017).
  * Koch and Hillery [2018] D. Koch and M. Hillery, Phys. Rev. A 97, 012308 (2018).
  * Krovi and Brun [2007] H. Krovi and T. A. Brun, Phys. Rev. A 75, 062332 (2007).
  * Feldman  _et al._ [2010] E. Feldman, M. Hillery, H.-W. Lee, D. Reitzner, H. Zheng, and V. Bužek, Phys. Rev. A 82, 040301 (2010).
  * Hillery  _et al._ [2012] M. Hillery, H. Zheng, E. Feldman, D. Reitzner, and V. Bužek, Phys. Rev. A 85, 062325 (2012).
  * Kubota  _et al._ [2018] S. Kubota, E. Segawa, T. Taniguchi, and Y. Yoshie, Linear Algebra Appl. 554, 371 (2018).
  * Kubota  _et al._ [2019] S. Kubota, E. Segawa, T. Taniguchi, and Y. Yoshie, Linear Algebra Appl. 579, 217 (2019).
  * Yoshie [2019] Y. Yoshie, Graphs Combin. 35, 1305 (2019).