# Non-uniform Mixing of Quantum Walks on the Symmetric Group

Avah Banerjee  Avah Banerjee<EMAIL_ADDRESS>Missouri S&T AB is supported
by NSF award no. CCF-2246144.

###### Abstract

It is well-known that classical random walks on regular graphs converge to the
uniform distribution. Quantum walks, in their various forms, are quantizations
of their corresponding classical random walk processes. Gerhardt and Watrous
(2003) demonstrated that continuous-time quantum walks do not converge to the
uniform distribution on certain Cayley graphs of the Symmetric group, which by
definition are all regular. In this paper, we demonstrate that discrete-time
quantum walks, in the sense of quantized Markov chains as introduced by
Szegedy (2004), also do not converge to the uniform distribution. We analyze
the spectra of the Szegedy walk operators using the representation theory of
the symmetric group. In the discrete setting, the analysis is complicated by
the fact that we work within a Hilbert space of a higher dimension than the
continuous case, spanned by pairs of vertices. Our techniques are general, and
we believe they can be applied to derive similar analytical results for other
non-commutative groups using the characters of their irreducible
representation.

Keywords: Quantum Walks, Symmetric Group, Non-commutative Fourier analysis

Mathematics Subject Classification: 81P68, 20C30.

##  1 Introduction

The phenomenon of random walks on graphs has been widely studied and holds
significant applications across a myriad of problems in computational
sciences. They have been instrumental in developing randomized and
approximation algorithms [25]. Random walks can be characterized by Markov
chains and they can be fully characterized using methods from spectral graph
theory.

We look at the problem of sampling from the symmetric group via a quantization
of random walk. The study of sampling from groups has a rich history [15, 16,
7]. Particularly, sampling an element from the symmetric group has been well-
studied in the classical setting [16], especially with respect to functions
over elements of groups. Sampling from group elements ties with certain random
walks; in some cases, even if the original sampling problem does not involve
sampling from a group element (for example, the famous Ehrenfest process).
These random walks take place on the Cayley graphs of the groups, which are
constructed using some generating set. Since Cayley graphs are regular, a
uniform random walk on them converges to the uniform distribution. However,
this does not seem to be the case in the quantum setting. We extend the
analysis of Gerhardt and Watrous (2003) [20] to demonstrate the uniformity of
the distribution, both instantaneous and average, arising from the
quantization of a uniform Markov chain on the symmetric group.

Unlike _classical_ random walks a _quantum walk_ propagates using the
principle of quantum mechanics. Few difference of note include - 1) Instead of
real probabilities the state of the walk is specified by complex probability
amplitudes111However, in some case if the amplitudes are constrained to be in
$\mathbb{R}$, working with them becomes slightly simpler.. 2) The random
(walk) coin is now replaced by a unitary transformation. The unitary evolution
ensures the walk is reversible222For open systems the walk operator need not
be unitary. Interspersing walking with measurements also leads to non-unitary
dynamics[22]. 2) Propagation of the walk generates a superposition state overs
all possible positions available to the walker. 3) Finally, we can sample the
positions by applying suitable measurements on the state of the walker.

There are various (somewhat equivalent) models of quantum walks. Study of
quantum walks has a long history, going back to the early works of Feynman,
Meyer, Aharonov, Gutmann and others [3, 18, 27]. The hope is that quantum walk
can emulate the success of random walk in the development of classical
algorithms in developing quantum algorithms. Quantum or classical
walk333Henceforth we will refer to classical random walk simply as classical
walk. has been primarily used as a generative models for probability
distributions. Hence, two of the most important properties to study are the
kind of distributions they can generate and their converging behavior. In
general, quantum walks do not converge to a stationary distribution. However,
their time-averaged distribution (introduced later) does converge. Quantum
walk has been shown to generalize Grover’s diffusion based search on graphs.
It has been used to obtain currently best known quantum algorithms for certain
problems. Most notable among them are element distinctness, triangle finding,
faster simulation of Markov chains, expansion testing etc. [26, 5, 6].

###  1.1 Overview of our techniques and Results.

In this paper, we focus on a discrete-time model of quantum walk. The model we
examine has its origins in the seminal paper by Aharonov et al.[2]. Since its
introduction, numerous variants of discrete-time quantum walks (DTQW) have
emerged. When it comes to accelerating randomized algorithms by harnessing the
faster mixing properties of quantum walks, the most extensively studied
framework involves the quantization of a classical Markov chain. This
framework was first introduced by Szegedy [35], and has since been expanded
upon and applied to a multitude of graph search algorithms within the black-
box query model. In this paper, we employ the Szegedy quantum walk framework
to analyze the distribution properties of a specific type of Cayley graph of
the symmetric group. Our primary concern is not the mixing time or other
measures of convergence, but rather illustrating how the probability
distribution deviates from that of the corresponding classical Markov chain.
This research implies that the probability of observing a group element is
intricately tied to the “weight” of its various irreducible representations.
In the case of abelian groups, given that their representations are
1-dimensional, they play a consistent role for all group elements, and, as
demonstrated previously, such walks converge to the uniform distribution. This
distinctive difference renders the study of such walks for symmetric and other
simple non-abelian groups considerably more intricate. Further discussions on
previous results can be found in Section 3.

Given a Markov chain with its transition matrix $P$, we begin by constructing
a bipartite walk on the combined state space $X\times X$. The transition
matrix of this bipartite walk forms the basis for deriving a unitary operator
in the quantum context. Informally, for each state $x\in X$, one constructs a
vector $\vec{\phi}_{x}$ that represents a superposition of the edges linking
$x$ to its neighbors, with weights corresponding to the transition amplitudes.
These vectors are utilized to define a reflection operator as well as a shift
operator (which will be introduced later). The reflection operator allows the
quantum walk to “propagate in superposition” along the edges adjacent to a
vertex. The shift operator alternates the propagation direction from left-to-
right and vice versa. The composition of these operators results in a unitary
$\operatorname{\mathcal{W}}$, which characterizes a step of the quantum walk.
This construction facilitates a relatively straightforward determination of
the spectral decomposition of $\operatorname{\mathcal{W}}$ in relation to the
spectra of $P$. The elements of $X$ can be interpreted as vertices of an edge-
weighted directed graph, where the weights correspond to the transition
probabilities. In our context, this graph is associated with a specific Cayley
graph of the symmetric group. The quantization of the bipartite Markov chain
gives rise to a quantum walk, which fundamentally occurs on the edges of the
original graph. Due to the inverse closure of the generating set we utilized,
this graph is undirected.

In the case of continuous-time quantum walks, which evolve based on the
Hamiltonian $e^{itL}$ where $L$ is the graph Laplacian, Gerhart and Watrous
studied the walk on several Cayley graphs of the symmetric group. They
utilized the spectral decomposition of the random walk operator in terms of
the irreducible representations (irreps) of the symmetric group, initially
derived by Diaconis [15], to determine the probability of observing an
$n$-cycle for the quantum walk. They demonstrated that this probability,
$O(2^{-2n}/(n+1)!)$, is exponentially smaller than in the case of the uniform
distribution (which is $1/n$). We extend their technique in the setting of the
Szegedy walk. We apply the spectral decomposition of $P$ in terms of the
irreps of the group to construct a similar, albeit more technical, spectral
decomposition of $\operatorname{\mathcal{W}}$. This enables us to similarly
upper bound the probability of observing an $n$-cycle, in our case determined
by all edges incident to $n$-cycles. However, due to the difference in the
Hilbert space of the quantized Markov chain compared to the continuous-time
version, our analysis presents a considerably greater challenge.

The analysis highly depends on the tractability of working directly with
irreps. Unfortunately, the irreps are matrices with no simple formulaic
description. This restricts us to focusing our analysis on cases where we can
use the characters of the group elements instead of the irreps. In light of
this, we limit our study to generating sets that are conjugacy closed.
Specifically, in this paper, we focus on the generating sets which consist of
transpositions. Even with this limitation, the analysis is still influenced by
the choice of the initial state and the form of the final state. Particularly,
the support of the probabilities in the final state should also be over a
conjugacy-invariant set. However, this isn’t an issue for us as, when testing
the probability of observing an $n$-cycle, we can choose the uniform
distribution over all $n$-cycles (more technically, all edges incident to
$n$-cycles) and determine its overlap with the final state. Much of the
technical calculations in this paper are focused on determining this overlap
using the characters of the group. This lead to our main theorem.

######  Theorem 1.

For any constant $\beta>\frac{81}{16}$,

$\displaystyle\norm{\bra{\phi_{[n]}}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}}=O\left(\frac{n^{20}\beta^{2n}}{n!}\right),$

where $\ket{\psi_{[n]}}=\frac{1}{\sqrt{(n-1)!d}}\sum_{g\in[n],s\in
S}\ket{g,gs}$ is the uniform superposition of all edges incident to
$n$-cycles, and $\ket{\psi_{\mathbb{e}}}=\frac{1}{\sqrt{d}}\sum_{s\in
S}\ket{\mathbb{e},s}$ is the uniform superposition of all edges incident to
the identity permutation.

Ignoring the polynomial factor, which arises due to the technical limitations
of our approach, we observe that the walk operator behaves roughly similarly
to that of the continuous version.

###  1.2 Discussion

####  1.2.1 Classical Complexity of Generating Quantum Walk Distribution,
Localization

Consider a unitary operator $U$ drawn from the unitary group $\mathbb{U}(n)$
according to the Haar measure. When $U$ acts on the state $\ket{0^{n}}$, it
results in the state $\ket{\psi}$. It’s worth noting that $\ket{0^{n}}$ can be
replaced with any fixed initial state, not necessarily the all-zero state. Let
$p(x)$ represent the probability of observing the state $\ket{x}$ when the
system is in state $\ket{\psi}$, with $x$ being a computational basis state.

It is a well-established fact that when $p(x)\in[0,1]$ is viewed as a
continuous random variable (determined by the Haar measure on
$\mathbb{U}(n)$), the distribution of probability values, $p$, conforms to the
Porter-Thomas distribution as given by: $\mathbb{P}[p]=2^{n}e^{-2^{n}p}$. An
intrinsic property of this distribution is that the probability amplitude
distribution of $\ket{\psi}$ is anti-concentrated; this means that no specific
basis state is noticeably more or less probable than the uniformly distributed
probability value of $2^{-n}$. Nevertheless, there isn’t a classical process
available to effectively approximate such outputs, even though it’s feasible
to devise a classical stochastic process that can mimic the Porter-Thomas
distribution for these probabilities [9, 10]. Our result, which is consistent
with those from continuous-time cases, reveals that the unitary operator of
the Discrete-Time Quantum Walk (DTQW) on the symmetric group is considerably
different from a Haar-random unitary. Additionally, its probability
distribution deviates markedly from uniformity. We observe that the quantum
walker has certain blind spots, which may hint at some localization phenomenon
and consequently a lack of anti-concentration. It is not a priori evident that
such distributions can be generated efficiently in the classical setting.

####  1.2.2 Beyond Class Functions

While the techniques presented here are farely general, their capacity to
derive analytical results largely hinges on the ability to use characters of
certain irreducible representations of the symmetric group. Generally, the
spectrum of the DQTW operator will depend directly on the irreps, unless the
discriminant matrix, derived from the Markov chain, possesses some special
structure. As outlined in [15], the eigenvalue expression utilizing class
functions is valid for any matrix whose $[g,h]^{th}$ entry can be expressed by
a class function $f(g^{-1}h)$. More comprehensively, for any transition matrix
$P$, one can form a block-diagonal decomposition:

$\displaystyle P=\varphi M\varphi^{\dagger}$

Here, the columns of the $|G|\times|G|$ matrix $\varphi$ form an orthonormal
set of vectors spanning the vector space defined by elements of $G$. Moreover,
$M$ is a block-diagonal matrix, with blocks corresponding to components of the
Fourier transformation of $P$ (defined as a function from $G$ to $[0,1]$ where
$P(g,h)=f(g^{-1}h)$ for a certain probability distribution $f$ on $G$, not
necessarily a class function) in terms of the irreps of $G$. In scenarios
where $f$ is a class function, $M$ is strictly a diagonal matrix, and the
column vectors of $\varphi$ are the vectors $\rho_{\mu,i,j}(g)$, with
$\rho_{\mu}$ denoting an irrep of $G$. Nonetheless, within this broader
framework, the spectral decomposition of the Szegedy walk operator is directly
influenced by the matrix entries of the irreps, not solely the trace (commonly
known as the characters of the irreps). Currently, there is no apparent method
to broaden our analysis beyond class functions.

####  1.2.3 Discrete Heisenberg Group

The discrete Heisenberg group has found applications in physics [19, 4] as
well in complexity theory [24]. It is one of the simplest non-abelian
extension of the regular 2d lattice, for which random walks have been
thoroughly studied. Furthermore, it has an elegant description with respect to
its _center_. The 3-dimensional discrete Heisenberg group $H_{3}(n)$ over
$\mathbb{Z}/n\mathbb{Z}$ is defined by the following multiplication rule :
$(x,y,z)(x^{\prime},y^{\prime}z^{\prime})\to(x+x^{\prime},y+y^{\prime},z+z^{\prime}+xy^{\prime})$
(modulo $n$). Dynamics of random walks over them are well understood, and
known to converge to the uniform distribution in $O(n^{2})$ steps [11, 39].
Here, we are especially interested in the case where $n=p$, a prime. This
group is _extra-special_ , in particular, $H_{3}(p)/Z$ is abelian and $Z$ is
cyclic where $Z$ is the center of $H_{3}(p)$. For this case we can to consider
the _Schreier coset graph_ of $H_{3}(p)$ with respect to the cosets of $Z$. As
far as we are aware, quantum walks have not been studied on coset graphs in
the discrete setting (for an example in the continuous case see [30]). The
techniques presented here could be applied to this group, possibly taking
advantage of its “nested” structure and more manageable representations.

##  2 Preliminaries

###  2.1 Symmetric Group, Cayley Graphs and Representation Theory

####  2.1.1 Cayley Graphs

Let $(G,\circ)$ be any finite group, and let $S$ be a generator of $G$. We
define $|G|=N$ and $|S|=d$. The Cayley graph of the pair, denoted as
$\Gamma(G,S)$, is a directed graph $\Gamma$, defined as follows: The vertex
set is $V(\Gamma)=G$, and the edge set is defined as

$\displaystyle E(\Gamma)$ $\displaystyle=\\{(g,h)\mid g,h\in G,\exists s\in
S\text{ such that }g^{-1}\circ h\in S\\}.$

Henceforth, we omit the “$\circ$” and simply write $g\circ h$ as $gh$ for all
$g,h\in G$. If $S$ is closed under taking inverses, i.e., $s\in S\implies
s^{-1}\in S$, then $\Gamma$ is undirected. In this paper, we set
$G=\mathcal{S}_{n}$, the symmetric group of permutations of $n$ elements. We
use $\mathbb{e}$ to denote the identity permutation, where
$\mathbb{e}=(1)(2)\cdots(n)$. We will exclusively work with the generating set
composed of all transpositions in $\mathcal{S}_{n}$, i.e., $S=\\{(i,j)\mid
i\neq j,i,j\in[n]\\}$. Thus, $S$ is closed under conjugation, and
$\Gamma_{n}=(\mathcal{S}_{n},S)$ is a ${n\choose 2}$-regular undirected graph.
Throughout this paper, we use $g$, $h$, $x$, $y$, etc. to denote generic group
elements. Occasionally, we use $\pi$ and $\sigma$ to emphasize elements of the
symmetric group.

The quantum walk studied in this paper does not take place directly on
$\Gamma_{n}$ but on a bipartite extension, denoted as
$\Gamma^{\musDoubleFlat}_{n}$, of $\Gamma_{n}$. Where

$\displaystyle\Gamma^{\musDoubleFlat}_{n}=(\mathcal{S}_{n}\times\mathcal{S}_{n},\\{{\pi,\sigma}\mid\pi,\sigma\in\mathcal{S}_{n}\text{
and }\exists\tau\in S\text{ such that }\pi=\sigma\tau\\})$

We further elaborate on this when introducing Szegedy walks in Section 2.2.

####  2.1.2 Representation of the Symmetric Group

Representation theory provides a framework to study abstract algebraic
structures by representing their elements as linear transformations of vector
spaces. In particular, the representation theory of the symmetric group, the
group of all permutations of a set, holds profound mathematical importance and
has ties to diverse areas. Here, we briefly introduce only the relevant
definitions needed to present our analysis. A comprehensive introduction to
representation theory in the context of symmetric groups, non-commutative
Fourier analysis, and random walks can be found in the books and monographs by
Sagan [32], A. Terras [36], and Diaconis [15], respectively, as well as in the
references therein. Much of the following material has been taken from those
sources.

A _representation_ of a group $G$ on a vector space $V$ over a field $F$ is a
homomorphism $\rho:G\to GL(V)$, where $GL(V)$ is the group of invertible
linear transformations of $V$. Specifically, for each element $g\in G$,
there’s an associated matrix $\rho(g)$ that respects the group operation:
$\rho(gh)=\rho(g)\rho(h)$ for all $g,h\in G$. In our setting we take
$F=\mathbb{C}$, the field of complex numbers. The _dimension_ of a
representation $\rho$ corresponds to the dimension of its associated vector
space $V$, denoted as $\dim\rho$. The representative matrices are
$(\dim\rho)\times(\dim\rho)$ matrices, which can be made to be unitary. A
representation $\rho$ is termed _irreducible_ if no non-trivial invariant
subspaces exist within it. This means the only subspaces of $V$ invariant
under every transformation $(\rho(g),g\in G)$, are $V$ itself and the zero
subspace. Henceforth we shall refer to irreducible representations as simply
_irreps_ for brevity. For a given representation $\rho$ , the character of
this representation, $\chi_{\rho}$, is a function from $G$ to the field
$\mathbb{C}$ defined by the trace of the representation’s matrix:
$\chi_{\rho}(g)=\text{Tr}(\rho(g))$. Following properties of $\chi_{\rho}$
will be useful:

  1. 1.

$\chi_{\rho}(\mathbb{e})=d_{\rho}$

  2. 2.

$\forall g,h\in G:\ \chi_{\rho}(gh)=\chi_{\rho}(hg)$ (cyclic property)

  3. 3.

$\forall g,h\in G:\ \chi_{\rho}(hgh^{-1})=\chi_{\rho}(g)$ ($\chi_{\rho}$ is
constant over the conjugacy classes)

Elements $g_{1}$ and $g_{2}$ in $G$ are termed _conjugate_ if there’s an $h\in
G$ such that $g_{2}=hg_{1}h^{-1}$. All elements conjugate to $g_{1}$ form its
_conjugacy class_. In symmetric groups, conjugacy classes are characterized by
a permutation’s cycle type. A _class function_ on group $G$ is a function
$f:G\to F$ (for some field $F$) that remains constant on conjugacy classes.
Characters of representations are classic instances of class functions.

A _Young diagram_ associated with a partition
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{k})$ of the number $n$ (that
is $\lambda_{1}+\cdots+\lambda_{k}=n$, denoted as $\lambda\vdash n$) consists
of $\lambda_{1}$ left-justified boxes in the top row, $\lambda_{2}$ in the
second, and so on. We will construct Young diagrams using the English
convention, with row lengths decreasing or remaining constant from top to
bottom. A _Young tableau_ fills this diagram with numbers from $1$ to $n$ such
that entries in each row and column are increasing. A _rim hook_ is a set of
boxes that can be removed from a Young diagram, leaving another Young diagram
behind.

The following text about _Young normal form_ is taken from [20] and has been
modified to match the language of the present paper. A more comprehensive
description can be found in [38, 32]. The symmetric group containing $n$
elements provides a unique method to link partitions of $n$ (which have a
bijection to the conjugacy classes of $\mathcal{S}_{n}$) to a full set of
distinct, irreps of $\mathcal{S}_{n}$. These distinct irreps are identified as
the Young normal forms. A notable feature of these irreps is that each matrix
entry within them is an integer. For each such representation, we may
associate another irrep up to an isomorphism, with all its matrices being
unitary. The irreducible, unitary representation corresponding to a specific
partition $\lambda$ is denoted as $\rho_{\lambda}$, and its corresponding
character is expressed as $\chi_{\lambda}$.

Finally, we briefly discuss the _Murnaghan-Nakayama Rule_ , which is useful
for computing the characters of certain irreps and conjugacy classes we used
in this paper. This is a combinatorial method used to compute character values
for symmetric group representations indexed by Young tableaux. The character
of a permutation with cycle type $\mu$ in the representation corresponding to
a Young tableau of shape $\lambda$ is determined by iteratively removing rim-
hooks and summing the associated contributions. We need to define a few more
terms before we can proceed. Given a Young diagram of shape (partition)
$\lambda$ and a composition of $\mu=(\mu_{1},\ldots,\mu_{k})$ 444A composition
of $n$ is a partition where the order of the parts matters. For a given
partition, the collection of compositions having the same parts corresponds to
different permutations with the same cycle structure; hence, their characters
are the same., a _filling_ of $\lambda$ using the _content_ from $\mu$ is a
labeling of the cells of $\lambda$ such that $\mu_{1}$ cells are labeled with
$1$, $\mu_{2}$ cells are labeled with $2$, and so on. Additionally, the
labeling must satisfy the following two conditions: (1) the cells
corresponding to the same label have the shape of a rim-hook, and (2) labels
are non-decreasing along rows and columns. Such a filling of the shape is
called a _rim-hook tableau_. The _leg-length_ (denoted as $ll()$) of a rim-
hook $\zeta$ is defined as $(\text{number of rows spanned by }\zeta)-1$. The
_sign_ of a rim-hook tableau $T$ is given by:

$\displaystyle\operatorname{sgn}(T)=(-1)^{\sum_{\zeta\in T}{ll(\zeta)}}$

Then, the Murnaghan-Nakayama Rule provides a way to compute
$\chi_{\lambda}(\mu)$:

$\displaystyle\chi_{\lambda}(\mu)=\sum_{T}\operatorname{sgn}(T)$

where the sum is over all valid rim-hook tableaux for the pair $\lambda,\mu$.

####  2.1.3 Fourier Transform Over Non-Commutative Groups

The Fourier transform is a powerful tool in signal processing and applied
mathematics, enabling the analysis of a signal’s frequency content. In the
case of groups ($G$), the Fourier transform of a function $f:G\to\mathbb{C}$
performs a basis change from $\\{\delta_{g}\mid g\in G\\}$ to
$\\{\rho[i,j]\mid 1\leq i,j\leq\dim\rho\\}$. Here, $\rho[i,j]$ is the
$(i,j)^{\text{th}}$ entry of the matrix presentation of $\rho$ for different
group elements, thus constituting a function of the form $G\to\mathbb{C}$. As
observed, in the case of non-commutative groups, the Fourier transform takes a
more complex form than in the commutative case, owing to the fact that the
irreps are themselves linear operators. More formally, the Fourier transform
over finite groups is defined as:

$\displaystyle\hat{f}(\rho)=\sum_{g\in G}f(g)\rho(g)$

In the case where $f$ is a class function, this simplifies to:

$\displaystyle\hat{f}(\rho)=\frac{1}{\dim\rho}\left(\sum_{[g]}f([g])\chi_{\rho}(g)|[g]|\right)I_{\dim\rho\times\dim\rho}$

where the sum is over all conjugacy classes in $G$, and $|[g]|$ denotes the
size of $[g]$. We shall use the latter expression when computing certain
projections with respect to the Szegedy walk operator.

###  2.2 Quantizing Markov Chains: Szegedy Walk

Szegedy developed the framework of quantizing a Markov chain [35], which was
then used to derive a quantum speedup of random-walk-based search algorithms
on graphs. Here, we borrow Szegedy’s terminology. Let $X$ and $Y$ be two parts
of a bipartite graph, and let $P$ and $Q$ be probabilistic maps from $X$ to
$Y$ and from $Y$ to $X$, respectively. For any $x\in X$ and $y\in Y$ let

$\displaystyle\ket{\phi_{x}}=\sum_{y\in Y}\sqrt{P_{xy}}\ket{x,y}$ and
$\displaystyle\ket{\psi_{y}}=\sum_{x\in X}\sqrt{Q_{yx}}\ket{x,y}$

Further, let $A$ (resp. $B$) be matrix composed of the column vectors
$\\{\ket{\phi_{x}}\\}$ (resp. $\\{\ket{\psi_{x}}\\}$). Define two reflection
operators - $R_{A}=2AA^{\dagger}-I$ and $R_{A}=2BB^{\dagger}-I$. Finally the
quantum walk unitary is defined as

$\displaystyle\operatorname{\mathcal{W}}=R_{B}R_{A}.$

The formulation above generalizes coined quantum walks on regular graphs in
the following sense. To provide some intuition about this definition, we
briefly introduce coined quantum walks. A classical random walk on vertices
cannot be directly quantized into a unitary operator on the Hilbert space
spanned by the vertices. To create a unitary, one has to lift the space on
which the quantum walk takes place to a product of two Hilbert spaces: 1) a
“coin space,” which is used to propagate amplitudes from a vertex to its
neighbors in superposition, and 2) a shift or move operator that transfers the
walker from the current vertex to its neighbors. More formally, the state of
such a particle at any moment is described by a vector in the Hilbert space
${\cal H}$, with a basis set $\\{\ket{c,x}\mid c\in C\text{ and }x\in X\\}$
(standard basis), for some $|C|$-regular graph with vertex set $X$. Thus, we
can express ${\cal H}$ as ${\cal H}={\cal H}_{X}\otimes{\cal H}_{C}$. The
space ${\cal H}_{X}$ describes the position of the particle over the vertices.
${\cal H}_{C}$ is the coin space, which describes the state of the particle’s
internal degrees of freedom (sometimes referred to as the particle’s
_chirality_). One step of the walk consists of successively applying the two
unitaries $U_{C}\otimes I_{X}$ and $\Lambda$, where $\Lambda=\sum_{c\in C,x\in
X}\outerproduct{c,c(x)}{x,c}$. Here, $c(x)$ denotes the $c^{th}$ neighbor of
$x$. The shift operator $\Lambda$ moves the walker to its neighboring vertex
in superposition. The coin operator $U_{C}$ determines how the amplitudes
spread to neighboring vertices, acting like a quantum analogue of a classical
$|C|$-sided die. For graphs with arbitrary vertex degree, $U_{C}$ is replaced
by the reflection operator $R_{A}$. It is easy to see that if we take $C=Y$,
then $\Lambda R_{A}\Lambda=R_{B}$, where shift operator is generalized as
$\Lambda=\sum_{x\in X,y\in Y}\outerproduct{y,x}{x,y}$. The spectral properties
of the walk operator $\operatorname{\mathcal{W}}$ are closely related to the
discriminant matrix $D$, whose entries are defined as
$D_{xy}=\sqrt{P_{xy}Q_{yx}}$. In the setting of quantized random walks, we
shall take $X=Y=\mathcal{S}_{n}$. Furthermore, the transition probabilities
are assumed to be uniform, and as such, $P$ is symmetric. Thus, $D=P$.
Specifically,

$\displaystyle D_{\pi\sigma}=\begin{cases}\frac{1}{d}\hskip 28.45274pt\mbox{if
$\pi^{-1}\sigma\in S$}\\\ 0\hskip 28.45274pt\mbox{otherwise}\end{cases}$ (1)

####  2.2.1 Instantaneous and Limiting Distribution

Given the initial state $\ket{\psi_{0}}$, the state after $t$ steps of the
walk is represented as:

$\displaystyle\ket{\psi_{t}}=\operatorname{\mathcal{W}}^{t}\ket{\psi_{0}}.$

As previously discussed, the basis of the Hilbert space in which the walk
takes place consists of pairs of permutations from $\mathcal{S}_{n}$, and we
refer to this as the standard basis. From this point onward, we assume that
all measurements are performed in this basis. The probability of sampling a
permutation $\pi$—more specifically, observing it in the first register—of
$\mathcal{S}_{n}$ after $t$ steps of the walk is given by:

$\displaystyle
P_{t}[\pi\mid\psi_{0}]=\sum_{\sigma\in\mathcal{S}_{n}}\norm{\bra{\pi,\sigma}\operatorname{\mathcal{W}}^{t}\ket{\psi_{0}}}_{2}^{2}$

Since $\operatorname{\mathcal{W}}$ is unitary, $\ket{\psi_{t}}$ exhibits
periodicity [2], provided that $\ket{\psi_{0}}$ is not an eigenvector of
$\operatorname{\mathcal{W}}$. Generally, $P_{t}$ does not converge. However,
the time-averaged distribution, defined below, does converge as $T\to\infty$:

$\displaystyle\overline{P}_{T}[\pi\mid\psi_{0}]=\frac{1}{T}\sum_{t=0}^{T-1}P_{t}[\pi\mid\psi_{0}]$

$\overline{P}_{T}$ can be interpreted as the expected value of the
distribution $P_{t}$ when $t$ is selected uniformly at random from the set
$\\{0,\ldots,T-1\\}$.

In this paper, we are interested in upper-bounding
$\overline{P}_{T}[\psi_{[n]}\mid\psi_{0}]$, where $\psi_{[n]}$ is the state
representing the uniform superposition of pairs $(\pi,\sigma)$ in which the
first register is an $n$-cycle. For the case of classical random walk this is
analogous to determining the probability of sampling an $n$-cycle.
$\overline{P}_{T}[\ \mid\psi_{0}]$ defines a distribution
$\overline{\mathcal{D}}_{n,\psi_{0},S}$ on $\mathcal{S}_{n}$, which depends on
the initial state $\ket{\psi_{0}}$ and the choice of the generating set $S$.
Since in our analysis both $S$ and $\ket{\psi_{0}}$ are fixed we simply use
$\overline{\mathcal{D}}_{n}$ to denote this time averaged distribution.

####  2.2.2 Continuous Time Quantum Walks and Average Mixing Matrix

Here we briefly introduce some notion related to continuous time walks that
will be useful to compare this work with some previous and recent results in
the domain of continuous time quantum walks. A comprehensive introduction to
concepts presented here can be found in [13] and the references therein. Let
$A$ be the adjacency matrix of a undirected regular graph with vertex set $X$.
$A$ is hermitian and as such $e^{itA}$ defines a Hamiltonian evolution on the
Hilbert space spanned by the vertices of the graph. Let $U(t)=e^{itA}$. $U(t)$
is known as the continuous time quantum walk operator. It is important to note
here that $U(t)$ acts directly on the vertices, which is not possible in the
discrete setting. In the setting of continuous time quantum walk a there is
another notion of time average distribution - the _average mixing matrix_
[21]. Let $(A\circ B)_{x,y}=A_{x,y}B_{x,y}$ denote the _Schur product_ of $A$
and $B$. Then $M(t)=U(t)\circ U(-t)$, which is a doubly stochastic matrix. On
the standard basis spanned by the vertices, the collection $\\{\bra{x}M(t)\\}$
gives rise family of probability densities - which can be interpreted as the
resulting distribution after evolving for time $t$ starting from the vertex
$x\in X$. To define the time average distribution , we can work with the time
average version of $M(t)$, denoted as $\overline{M}(t)$, called the average
mixing matrix. :

$\displaystyle\overline{M}(t)=\frac{1}{T}\int_{0}^{T}M(t)dt.$

Recently, average mixing matrix has been extended in the discrete setting
[34]. In the language of this paper, we can define an average mixing matrix
for the Szegedy walk operator as follows:

$\displaystyle\overline{M}_{xy}=\frac{1}{T}\sum_{t=0}^{T-1}\sum_{\sigma\in
S}P_{t}\left[\ket{x,x\sigma}\mid\ A\ket{y}\right]$

Here, the matrix $A$ is the matrix we defined earlier when introducing the
Szegedy walk. We can interpret $\overline{M}_{xy}$ as the average probability
of observing $x$ in the first register, starting from the state $A\ket{y}$. In
this context, the initial state is a superposition over the outgoing555Even
though the walk takes place on an undirected graph, we may assign an
orientation to an edge with respect to the vertex where the walker is
situated, treating it as the tail of the edge. Since we are only considering
bipartite walks, the walker can be present at most at one of the endpoints.
edges from $y$, according to the amplitude distribution $\ket{\phi}_{y}$. The
average mixing matrix can be useful for studying the average limiting behavior
of the quantized Markov chain. In particular, if the Markov chain $P$ mixes to
a uniform distribution, then an analogous notion can be considered in the
quantum case, where we are interested in how close $\overline{M}$ is to the
matrix $\frac{1}{n}J$, with $J$ being the matrix whose all entries are 1. If
$\overline{M}$ equals $\frac{1}{n}J$ in the limit, then we say the chain
exhibits average uniform mixing.

##  3 Previous and Related Work

##### Discrete Time Quantum Walk on Groups.

In their seminal paper [2], Aharonov et al. presented several results on
DTQWs. They characterized the convergence behavior of walks on abelian groups,
showing that the time-averaged distribution converges to the uniform
distribution whenever the eigenvalues of $U$ are all distinct. They also
provided an $O\left(\frac{n\log n}{\epsilon^{3}}\right)$ upper bound on the
mixing time for $\mathbb{Z}_{n}$ (the cycle graph), and proved some lower
bounds in terms of the graph’s conductance. Following their introduction,
DTQWs have been studied for several graph families. Nayak and Vishwanath [29]
conducted a detailed analysis for the line using Fourier analysis,
demonstrating that the Hadamard walk mixes almost uniformly in only $O(t)$
steps, achieving a quadratic speedup over its classical counterpart. Moore and
Russell [28] analyzed the Grover walk on the Cayley graph of
$\mathbb{Z}^{n}_{2}$ (also known as the hypercube), showing an instantaneous
mixing time of $O(n)$, which beats the classical $\Omega(n\log n)$ bound.
Acevedo and Gobron [1] studied quantum walks for certain Cayley graphs,
providing several results for graphs generated by free groups in particular.
D’Ariano et al. [17] investigated the case where the group is virtually
abelian, a condition that allowed them to reduce the problem to an equivalent
one on an abelian group with a larger chiral space dimension, employing the
Fourier method introduced in [29]. More recently, DTQWs on the Dihedral group
$D_{n}$ have been studied by Dai et al. [14] and Sarkar and Adhikari [33].
Since $D_{n}$ is isomorphic to the semi-direct product
$\mathbb{Z}_{n}\rtimes\mathbb{Z}_{2}$, the Fourier approach introduced in [29]
is applicable once again. Using this method, the authors in [14] provided a
spectral decomposition of $U$ for the Grover walk. In [33], the authors study
the periodicity and localization properties of the walk using generalized
Grover coins. A detailed survey of various types of quantum walks, including
DTQW, can be found in [37], with additional references therein. A survey
specifically addressing DTQWs on Cayley graphs is available in [23].

##### Quantum Walk on the Symmetric Group.

In a previous work by the author [8], DTQW on the symmetric group was studied
using the coin-based model. Utilizing the Fourier transform (see Section
2.1.3), a recurrence relation was derived for the amplitudes of
$\ket{\phi_{t}}$, from which a “sum-over-paths” type expression was determined
for the amplitudes. It was also determined under which conditions the
amplitudes are class functions. Prior to this, as indicated earlier, Gerhardt
and Watrous [20] studied the continuous time quantum walk model on the
symmetric group. They showed that when $S$ is the set of transpositions, the
time-averaged distribution is far from the uniform distribution. They
explicitly calculated the probability of reaching an $n$-cycle starting from
$\mathbb{e}$ by expressing the eigenstates of $\operatorname{\mathcal{W}}$
using the characters of ${\cal S}_{n}$. They also considered the generating
set (for $\mathcal{A}_{n}$) consisting of all $p$-cycles (where $p$ is odd)
and derived similar results as in the transposition case.

##### Average limiting behavior.

Considerable research has been conducted on studying the limiting behavior of
quantized Markov chains, as mentioned earlier. More recently, the properties
of the average mixing matrix have been explored, especially for continuous-
time chains. For example, in [34, 12], the entries of the average mixing
matrix in the limit as $t\to\infty$ were expressed using the projectors in the
spectral decomposition of the walk operator. One of the interesting questions
with respect to limiting behavior is whether a quantized Markov chain exhibits
average uniform mixing. To this end, the authors in [34] have constructed a
family of Markov chains whose quantized versions do exhibit such average
mixing behavior, and have shown that average uniform mixing of the continuous-
time quantum walk implies the same for its discretized version.

##  4 Eigendecomposition of $\operatorname{\mathcal{W}}$ over the irreps of
$\mathcal{S}_{n}$

Gerhardt and Watrous used representation theory to express the eigenstates
using the irreps of ${\cal S}_{n}$. This method is effective due to the fact
that the walker’s Hamiltonian is completely specified by the adjacency matrix
of $\Gamma_{n}$. In the discrete case, as $\operatorname{\mathcal{W}}$ acts on
a larger space, this decomposition becomes more complex for an arbitrary
generating set. However, there is at least one special case where we can
directly apply their Fourier method.

This special case occurs when the generating set $S$ forms a group itself. For
the amplitudes to be uniform over the conjugacy class, which is a necessity
for using Fourier analysis over the characters of the irreps., the generating
set $S$ must be conjugate invariant. However, the only non-trivial subgroup of
${\cal S}_{n}$ that is also conjugate invariant is the _alternating group_
${\cal A}_{n}$, which is the subgroup of all even permutations in ${\cal
S}_{n}$. In this scenario, it becomes possible to factorize the space of
irreps. for the walk on $\Gamma=({\cal S}_{n},{\cal A}_{n})$, and determine
the spectral decomposition of $\operatorname{\mathcal{W}}$ using the
characters of both ${\cal S}_{n}$ and ${\cal A}_{n}$. To overcome this issue
we use the Szegedy walk formalism, which considers an even larger coin-space,
as introduced earlier.

As Szegedy showed, the dynamics of the walk operator
$\operatorname{\mathcal{W}}$ can be determined from the discriminant matrix
$D$. Since $D$ is Hermitian (in fact, symmetric), the singular values of $D$
lie in the interval $[0,1]$. We index the singular values $\lambda_{\mu}$ of
$D$ using the conjugacy classes $\mu$ of $G$, which are the partitions of $n$.
For each $\lambda_{\mu}$, if the corresponding eigenvalue is also
$\lambda_{\mu}$, then the left and right singular vectors are equal (and are
equal to the corresponding eigenvector); otherwise, they differ by a minus
sign. For the former case, we use $\ket{\lambda_{\mu}}$ to denote both the
left and the right singular vectors. For the latter case, without loss of
generality, we use $-\ket{\lambda_{\mu}}$ to denote the left singular vector
by appropriately choosing the sign of the corresponding eigenvector. Let
$\Pi_{\operatorname{col}(A)}$ (resp., $\Pi_{\operatorname{col}(B)}$) denote
the projector onto the column space of $A$ (resp., $B$), and let
$\Pi_{\ker(A)}$ (resp., $\Pi_{\ker(B)}$) denote the projector onto the
orthogonal complement of the column space of $A$ (resp., $B$). We can restate
the _spectral lemma_ from [35] in the language of this paper, which will be
used in our subsequent analysis.

######  Lemma 2 (modified Lemma-1 from [35]).

Let $\lambda_{1},\ldots\lambda_{l}$ (with multiplicity) are the sequence of
singular values of $D$ in the interval $(0,1)$ and $\tilde{\lambda_{\mu}}$ be
the eigenvalue corresponding to $\lambda_{\mu}$. Then the eigenvalues and
eigenvectors of the walk operator $\operatorname{\mathcal{W}}$ is $e^{\pm
2i\cos^{-1}\lambda_{1}}\ldots e^{\pm 2i\cos^{-1}\lambda_{l}}$ and
$(A-(\operatorname{sgn}\tilde{\lambda_{1}})e^{\pm
i\cos^{-1}\lambda_{1}}B)\ket{\lambda_{1}}\ldots(A-(\operatorname{sgn}\tilde{\lambda_{l}})e^{\pm
i\cos^{-1}\lambda_{l}}B)\ket{\lambda_{l}}$ respectively (up to a
normalization). Additionally, corresponding to the singular value $1$,
$\operatorname{\mathcal{W}}$ acts as the identity ($I$) on the space
$\operatorname{col}(A)\cap\operatorname{col}(B)\oplus\ker(A)\cap\ker(B)$ and
corresponding to the singular value $0$, $\operatorname{\mathcal{W}}$ acts as
$-I$ on the space
$\operatorname{col}(A)\cap\ker(B)\oplus\ker(A)\cap\operatorname{col}(B)$.

From the definition of $D$, as presented in [20], we may define a class
function $f$ on $G$ such that $D_{\pi\sigma}=f(\pi^{-1}\sigma)$, provided that
$S$ is conjugate invariant (which holds true in our case). We will employ the
spectral decomposition of $D$ in terms of the characters of $\mathcal{S}_{n}$,
as given in [20], which takes advantage of the fact that the entries of $D$
behave as a class function. This is a special case of a more general result by
Diaconis [15] presented earlier. It has also been shown that the basis of the
irreps are the eigenvectors of $D$. This can, in turn, be utilized to derive
the spectra of the walker’s Hamiltonian by exponentiating the corresponding
eigenvalues of $D$. In the discrete case, the relationship between $D$ and the
walk operator $\operatorname{\mathcal{W}}$ is somewhat more subtle, and the
remainder of this section is devoted to elucidating it.

Recall that the conjugacy classes in $G$ have a one-to-one correspondence with
the collection of non-isomorphic irreps of $G$. These irreps can be expressed
using the so-called _Young normal form_ , whose matrix entries are all
integers. Let $\rho_{\mu}$ denote the irrep corresponding to the conjugacy
class $\mu$ (with size given by $\absolutevalue{\mu}$), which is a partition
of $n$ ($\mu\vdash n$). Define $\rho_{\mu,i,j}(g)=\rho_{\mu}(g)[i,j]$. The
vectors $\ket{\rho_{\mu,i,j}}$ (in the $G$-module $\mathbb{C}[G]$ over the
field of complex numbers) form an orthonormal basis corresponding to the irrep
$\rho_{\mu}$. For reference, we restate Lemma 6 from [20], which gives the
expressions for the eigenvalues of $D$ in terms of the characters of $G$.

######  Lemma 3 (modified lemma-6 from [20]).

Given $D,f$ as above, then $\ket{\rho_{\mu,i,j}}$ are the eigenvectors of $D$
with the eigenvalues,

$\displaystyle\tilde{\lambda_{\mu}}=\frac{1}{\dim\rho_{\mu}}\sum_{\sigma\vdash
n}|[\sigma]|f(\sigma)\chi_{\mu}(\sigma)$ (2)

Recall that $\lambda_{\mu}=\absolutevalue{\tilde{\lambda_{\mu}}}$ are the
singular values of $D$. Let $\kappa_{\mu}=e^{2i\cos^{-1}\lambda_{\mu}}$.
Associated with each non-extremal singular value $\lambda_{\mu}$
($\not\in\\{0,1\\}$) of $D$, there is a collection of eigenvectors
$\\{\ket{\rho_{\mu,i,j}}\\}$, where $1\leq i,j\leq\dim\rho_{\mu}$. The
$g^{th}$ component of $\ket{\rho_{\mu,i,j}}$ is given by $\rho_{\mu}(g)[i,j]$.
The projectors onto the space spanned by $\ket{\rho_{\mu,i,j}}$ are given by

$\displaystyle\Pi_{\mu,i,j}=\frac{(\dim\rho_{\mu})\ket{\rho_{\mu,i,j}}\bra{\rho_{\mu,i,j}}}{n!},$

where $\frac{\dim\rho_{\mu}}{n!}$ is a normalization factor, since we have
$\norm{\innerproduct{\rho_{\mu,i,j}}{\rho_{\mu,i,j}}}=\frac{n!}{\dim\rho_{\mu}}$.
Let $\Pi_{\mu}=\sum_{i,j}\Pi_{\mu,i,j}$ be the projector onto the column space
of $\tilde{\lambda_{\mu}}$. Let the projectors corresponding to the subspaces
$(\operatorname{col}(A)\cap\operatorname{col}(B))\oplus(\ker(A)\cap\ker(B))$
and
$(\operatorname{col}(A)\cap\ker(B))\oplus(\ker(A)\cap\operatorname{col}(B))$
be $\Pi_{+1}$ and $\Pi_{-1}$, respectively. Further, let
$\operatorname{\mathcal{W}}_{A,B}=\Pi_{+1}-\Pi_{-1}$. We can completely
determine the spectral decomposition of $\operatorname{\mathcal{W}}$ using
that of $D$, as given by the following lemma. Let
$s_{\mu}=\operatorname{sgn}\tilde{\lambda_{\mu}}$, and let
$\theta_{\mu}=\cos^{-1}\lambda_{\mu}$.

######  Lemma 4.

Spectral decomposition of $\operatorname{\mathcal{W}}$ is given by,

$\displaystyle\operatorname{\mathcal{W}}$ $\displaystyle=\sum_{\mu\vdash
n}\frac{1}{2\sin^{2}\theta_{\mu}}\kappa_{\mu}(A-s_{\mu}\sqrt{\kappa}_{\mu}B)\Pi_{\mu}(A^{\dagger}-s_{\mu}\sqrt{\kappa}_{\mu}^{*}B^{\dagger})+$
$\displaystyle\sum_{\mu\vdash
n}\frac{1}{2\sin^{2}\theta_{\mu}}\kappa_{\mu}^{*}(A-s_{\mu}\sqrt{\kappa}_{\mu}^{*}B)\Pi_{\mu}(A^{\dagger}-s_{\mu}\sqrt{\kappa}_{\mu}B^{\dagger})+\operatorname{\mathcal{W}}_{A,B}$

###### Proof.

The proof directly follows from the preceding discussions and Lemma 2. The
factor $\frac{1}{2\sin^{2}\theta_{\mu}}$ comes from normalizing the
eigenvectors. ∎

The decomposition of $\operatorname{\mathcal{W}}$ can then be divided into two
parts: one corresponding to the non-trivial eigenvalues, and the other
corresponding to the two trivial ones, $\\{-1,1\\}$. Let
$\operatorname{\mathcal{W}}_{\mu}$ be the term corresponding to $\mu$. Then,

$\displaystyle\operatorname{\mathcal{W}}^{t}=\sum_{\mu\vdash
n}\operatorname{\mathcal{W}}_{\mu}^{t}+\operatorname{\mathcal{W}}_{A,B}^{t}$
(3)

where, by a slight abuse of notation, we assume the sum above is over all
partitions except those corresponding to the trivial eigenvalues. It follows
that $\operatorname{\mathcal{W}}_{A,B}^{t}=\Pi_{+1}+(-1)^{t}\Pi_{-1}$, since
the projectors are mutually orthogonal. Expanding
$\operatorname{\mathcal{W}}_{\mu}^{t}$ we get,

$\displaystyle\operatorname{\mathcal{W}}_{\mu}^{t}=$
$\displaystyle\frac{1}{2\sin^{2}\theta_{\mu}}\left(\vphantom{\frac{1}{2}}(\kappa_{\mu}^{t}+\kappa_{\mu}^{*t})A\Pi_{\mu}A^{\dagger}-s_{\mu}(\kappa_{\mu}^{t}\sqrt{\kappa}_{\mu}^{*}+\kappa_{\mu}^{*t}\sqrt{\kappa}_{\mu})A\Pi_{\mu}B^{\dagger}\right.$
$\displaystyle\left.-s_{\mu}(\kappa_{\mu}^{t}\sqrt{\kappa}_{\mu}+\kappa_{\mu}^{*t}\sqrt{\kappa}_{\mu}^{*})B\Pi_{\mu}A^{\dagger}+(\kappa_{\mu}^{t+1/2}\sqrt{\kappa}_{\mu}^{*}+\kappa_{\mu}^{*t+1/2}\sqrt{\kappa}_{\mu})B\Pi_{\mu}B^{\dagger})\vphantom{\frac{1}{2}}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2\sin^{2}\theta_{\mu}}\left(\vphantom{\frac{1}{2}}\cos{2\theta_{\mu}t}(A\Pi_{\mu}A^{\dagger}+B\Pi_{\mu}B^{\dagger})-s_{\mu}\cos{2\theta_{\mu}(t-1/2)}A\Pi_{\mu}B^{\dagger}\right.$
$\displaystyle\left.-s_{\mu}\cos{2\theta_{\mu}(t+1/2)}B\Pi_{\mu}A^{\dagger}\vphantom{\frac{1}{2}}\right)$
(4)

From the above, we see that for any pair of initial and final states
$\ket{\psi_{0}}$ and $\ket{\psi_{t}}$, respectively, an upper bound on the
inner product $\bra{\psi_{t}}\operatorname{\mathcal{W}}\ket{\psi_{0}}$ depends
on the projectors respective to the irreps. In particular, if the overlap is
sufficiently low, then we can ignore the effect of the cosine terms (replacing
them with 1 or -1, as appropriate) and still obtain a non-trivial upper bound.
In the following, we use this approach to compute
$\norm{\bra{\phi_{[n]}}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}}$.

##  5 Divergence of $\operatorname{\mathcal{W}}$ from uniform mixing

In [20], the divergence of the instantaneous distribution from the uniform
distribution was confirmed by upper bounding the probability of being at an
$n$-cycle of $\mathcal{S}_{n}$. This probability was shown to be exponentially
smaller than in the classical case. Specifically, they showed that the
probability of being at some $n$-cycle is $O(2^{-2n}/(n+1)!)$, as compared to
$\frac{1}{n}$ in the classical case (uniform distribution). In the discrete
case that we study here, the walk takes place on the edges of the graph. We
show that the instantaneous probability of observing an $n$-cycle in the first
register is upper bounded away from $\frac{1}{n}$ by a function which is
$\tilde{O}\left(\frac{c^{n}}{n!}\right)$. Here, $\tilde{O}$ represents the
soft-O notation, but in our case, we ignore any functions up to polynomial in
$n$ (which are most likely due to artifacts from our techniques). Since the
bound we provide is on the instantaneous probability, it also implies that the
average mixing probabilities (entries of the average mixing matrix) are
exponentially far from uniform.

In the following, we use “$g,h$” to denote generic permutations from
$\mathcal{S}_{n}$, aiming to avoid confusion arising from our slight
notational abuse. Specifically, we use $\mu$ to denote a generic conjugacy
class that contains the permutation $\mu$. Recall,

$\displaystyle\ket{\psi_{[n]}}$
$\displaystyle=\frac{1}{\sqrt{(n-1)!d}}\sum_{g\in[(n)],s\in S}\ket{g,gs}$
$\displaystyle\ket{\psi_{\mathbb{e}}}$
$\displaystyle=\frac{1}{\sqrt{d}}\sum_{s\in S}\ket{\mathbb{e},s}$

Also, $d=|S|={n\choose 2}$ is the degree of $\Gamma^{\musDoubleFlat}_{n}$. We
will provide an upper bound for
$\norm{\bra{\phi_{[n]}}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}}$.
The state $\phi_{[n]}$ is the uniform superposition over all outgoing edges of
$n$-cycles, analogous to the state in classical walks and continuous time
quantum walks, which is the uniform superposition of all $n$-cycles. In the
discrete case, another possibility is to compute
$\norm{\bra{g,gs}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}}$ for
some arbitrary $n$-cycle $g$. By then summing over $S$, we find that
$\sum_{s}\norm{\bra{g,gs}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}}$
gives the instantaneous probability of observing $g$ in the first register
after $t$ steps. In both cases, we start from the state
$\ket{\phi_{\mathbb{e}}}$, which is the uniform superposition over all
outgoing edges from the identity permutation. This choice of initial state is
consistent with our definition of the average mixing matrix and is symmetric
with respect to the generating set $S$. Unfortunately, to compute the
aforementioned quantity, we need to have direct access to the entries of the
irreps, as the final state does not span all the basis vectors of a conjugacy
class. Thus, we make do with computing the former expression. We discuss this
issue briefly at the end of this section.

This section is organized as follows. First, in Section 5.1, we derive
expressions for the $\tilde{\lambda}_{\mu}$’s using the character theory of
$\mathcal{S}_{n}$. In Section 5.2, we prove Theorem 1. Finally, we discuss the
issue related to computing
$\sum_{s}\norm{\bra{g,gs}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}}$
in Section 5.3.

###  5.1 Computing $\tilde{\lambda_{\mu}}$

Here, we derive expressions for $\tilde{\lambda}_{\mu}$, which will be used
later for bounding the probabilities. Recall that our walk takes place on
$\Gamma^{\musDoubleFlat}_{n}$, derived from $\Gamma_{n}=(\mathcal{S}_{n},S)$,
where $S$ is the class of all transpositions. Furthermore, the entries of the
discriminant matrix $D_{gh}=f(g^{-1}h)$ form a class function over
$\mathcal{S}_{n}$ (equation 1). Specifically we define:

$\displaystyle f(g)=\begin{cases}\mbox{$\frac{1}{d}$ if $g\in S$}\\\ \mbox{$0$
otherwise}\end{cases}$

In the expression for characters, we will use $[\sigma]$ instead of $S$ to
denote the class of transpositions going forward. The above definition of $f$
simplifies the expression for the eigenvalues $\tilde{\lambda}_{\mu}$ given in
equation 2 as follows:

$\displaystyle\tilde{\lambda}_{\mu}=\frac{\chi_{\mu}([\sigma])}{\dim\rho_{\mu}}$
(5)

Next, we set out to compute the values of $\chi_{\mu}([\sigma])$ and the
dimension of $\rho_{\mu}$. Let $\mu=(\mu_{1},\ldots,\mu_{l})$, where
$\mu_{1}+\cdots+\mu_{l}=n$. It is known that [31]:

$\displaystyle\chi_{\mu}([\sigma])=\frac{\dim\rho_{\mu}}{n(n-1)}\left(\sum_{j=1}^{l}(\mu_{j}-j+1)(\mu_{j}-j)-j(j-1)\right)$
(6)

Fortunately, we only need to compute these quantities for a subset of
partitions ($\mu$’s) of $n$, which will greatly simplify our analysis.
Specifically, we assume $\mu\in\Xi_{n}$, where $\Xi_{n}$ is the collection of
partitions of $n$ having the following property: There exist four non-negative
integers $\mu_{1}\geq\mu_{2}\geq 1$, and $r,l\geq 2$ such that
$\mu=(\mu_{1},\mu_{2},2^{r-2},1^{l-r})$. Here, we allow $\mu_{2}=1$, but in
that case, $\mu$ can simply be written as $\mu=(k,1^{n-k})$ (that is,
$\mu_{1}=k,\mu_{2}=1,r=2,l=n-k+1$), and we say $\mu\in\Xi_{n,k}$. The
following fact is a simple application of the Murnaghan-Nakayama rule (see for
example Chapter 4 in [32]).

######  Fact 1.

Let $[n]$ set of all $n$-cycles of $\mathcal{S}_{n}$. Then

$\displaystyle\chi_{\mu}([n])=\begin{cases}\mbox{$(-1)^{n-k}$ \qquad if
$\mu\in\Xi_{n,k}$ and}\\\ \mbox{$0$ \qquad\qquad\qquad otherwise}\end{cases}$

Let $[\tau_{l}]$ (where $1\leq l\leq\lfloor n/2\rfloor$) be the conjugacy
class of all permutations with one cycle of length $l$ and another of length
$n-l$. Then, the following two facts are immediately apparent:

######  Fact 2.

If $\sigma\in[\sigma]$ and $\tau\sigma\in[n]$ then $\tau\in[\tau_{l}]$.

######  Fact 3.

If $\tau\in[\tau_{l}]$ for some $l$ and $\chi_{\mu}([\tau_{l}])\neq 0$ then
$\mu\in\Xi_{n}$.

######  Fact 4.

Size of the set $\Xi_{n}$ is $O(n^{3})$.

Again using the Murnaghan-Nakayama rule we get:

######  Fact 5.

$\displaystyle\chi_{\mu}([\tau_{l}])=\begin{cases}\mbox{$(-1)^{n-k-1}$ \qquad
if $\mu\in\Xi_{n,k}$ and $l\geq k$ }\\\ \mbox{$0$ \qquad\qquad\qquad
otherwise}\end{cases}$

Although we do not need to know $\dim\rho_{\mu}$ in order to compute
$\tilde{\lambda}_{\mu}$ we will need this for our analysis in later sections.

######  Lemma 5.

Let $\mu\in\Xi_{n}$ then

$\displaystyle\dim{\rho_{\mu}}=\begin{cases}{n-1\choose
k-1}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\mbox{if
$\mu\in\Xi_{n,k}$}\\\
\frac{n!(\mu_{1}-\mu_{2}+1)(l-r+1)((\mu_{1}+l-1)(\mu_{1}+r-2)(\mu_{2}+l-2)(\mu_{2}+r-3))^{-1}}{(\mu_{1}-1)!(\mu_{2}-2)!(l-1)!(r-2)!}\quad\quad\mbox{otherwise}\end{cases}$

###### Proof.

The proof of the lemma follows directly from the application of the _hook-
length_ formula, given by:

$\displaystyle\dim{\rho_{\mu}}=\frac{n!}{\prod_{i,j}h_{\mu}(i,j)}$

where $h_{\mu}(i,j)$ represents the hook-length of the cell $(i,j)$ in the
Young diagram of the partition $\mu$. The case $\mu\in\Xi_{n,k}$ is
straightforward, and we will focus on deriving the latter case. Since
$\mu\in\Xi_{n}\setminus\Xi_{n,k}$, we can express $\mu$ as
$(\mu_{1},\mu_{2},2^{r-2},1^{l-r})$, where $\mu_{1}\geq\mu_{2}\geq 2$. Below,
we provide the explicit hook lengths for a cell $(i,j)$, from which the lemma
immediately follows.

$\displaystyle h_{\mu}(i,j)=\begin{cases}(\mu_{1}+l-1)\qquad\mbox{if
$i=j=1$}\\\ (\mu_{1}+r-2)\qquad\mbox{if $i=1,j=2$}\\\
(\mu_{1}-j+2)\qquad\mbox{if $i=1,2<j\leq\mu_{2}$}\\\
(\mu_{1}-j+1)\qquad\mbox{if $i=1,\mu_{2}<j\leq\mu_{1}$}\\\
(\mu_{2}+l-2)\qquad\mbox{if $i=2,j=1$}\\\ (\mu_{2}+r-3)\qquad\mbox{if
$i=2,j=2$}\\\ (\mu_{2}-j+1)\qquad\mbox{if $i=2,2<j\leq\mu_{2}$}\\\
(l-i+2)\qquad\mbox{if $2<i\leq r,j=1$}\\\ (r-i+1)\qquad\mbox{if $2<i\leq
r,j=2$}\\\ (l-i+1)\qquad\mbox{if $r<i\leq l,j=1$}\end{cases}$

∎

######  Lemma 6.

If $\mu\in\Xi_{n}$ and $\tau\in[\tau_{l}]$ then
$\chi_{\mu}([\tau_{l}])\in\\{-1,0,1\\}$.

###### Proof.

Given $\tau\in[\tau_{l}]$, it is necessary for the partition $\mu$ to be in
$\Xi_{n}$ in order for $\chi_{\mu}([\tau])$ to be non-zero, as any valid rim-
hook tableaux filled using the labels from $\\{1,2\\}$ (according to the
composition $\tau$) must take the form of partitions in $\Xi_{n}$. As it turns
out, for any such shape $\mu$, there is at most one way to create a rim-hook
tableau $T_{\mu,\tau}$. In other words,
$\chi_{\mu}([\tau_{k}])=\operatorname{sgn}(T_{\mu,\tau})$ if $T_{\mu,\tau}$
exists, and $0$ otherwise.

∎

Next, we provide an upper bound on $\chi_{\mu}([\sigma])$, which is divided
into Lemmas 7 and 8.

######  Lemma 7.

If $\mu\in\Xi_{n,k}$ then $\chi_{\mu}([\sigma])=-\frac{n-2k+1}{n-1}{n-1\choose
k-1}$

###### Proof.

The stated bound follows immediately from the expression for
$\chi_{\mu}([\sigma])$ given in Equation 6, combined with Lemma 5, when we
substitute the components of $\mu=(k,1^{n-k})$. Specifically,

$\displaystyle\chi_{\mu}([\sigma])=\frac{\dim\rho_{\mu}}{n(n-1)}\sum_{j=1}^{n-k+1}(\mu_{j}-j+1)(\mu_{j}-j)-j(j-1)=-\frac{n-2k+1}{n-1}{n-1\choose
k-1}$

∎

######  Lemma 8.

If $\mu\in\Xi_{n}\setminus\Xi_{n,k}$ then for any constant
$\beta\geq\frac{81}{16}$ we have
$\absolutevalue{\chi_{\mu}([\sigma])}=O\left(n^{6.5}\beta^{n}\right)$

###### Proof.

Substituting $\mu=(\mu_{1},\mu_{2},2^{r-2},1^{l-r})$ in Equation 6 we get:

$\displaystyle\frac{n(n-1)}{\dim\rho_{\mu}}\chi_{\mu}([\sigma])$
$\displaystyle=\sum_{j=1}^{l}(\mu_{j}-j+1)(\mu_{j}-j)-j(j-1)=\mu_{1}(\mu_{1}-1)+(\mu_{2}-1)(\mu_{2}-2)-2$
$\displaystyle+\sum_{j=3}^{r}(3-j)(2-j)-\sum_{j=3}^{l}j(j-1)+\sum_{j=r+1}^{l}(2-j)(1-j)$
$\displaystyle=\mu_{1}^{2}+\mu_{2}^{2}-\mu_{1}-3\mu_{2}+l-l^{2}-(r-3)r$

Hence,

$\displaystyle\chi_{\mu}([\sigma])$
$\displaystyle=\frac{(\mu_{1}^{2}+\mu_{2}^{2}-\mu_{1}-3\mu_{2}+l-l^{2}-(r-3)r)(\mu_{1}-\mu_{2}+1)(l-r+1)}{n(n-1)(\mu_{1}+l-1)(\mu_{1}+r-2)(\mu_{2}+l-2)(\mu_{2}+r-3)}\times
T_{\mu}$ (7)

where $T_{\mu}=n!((\mu_{1}-1)!(\mu_{2}-2)!(l-1)!(r-2)!)^{-1}$. Suppose that
$\mu_{i}=\beta_{i}n$ for $i\in\\{1,2\\}$, and let $l=\beta_{3}n$,
$r=\beta_{4}n$, with $\beta_{1}\geq\beta_{2}$ and $\beta_{3}\geq\beta_{4}$,
where $\beta_{i}\geq 0$. Note that $\sum_{i}\beta_{i}=1+\frac{4}{n}$. Here, we
ignore the fact that the terms $\beta_{i}n$ may not be integers, as it does
not affect our analysis. Finally, by substituting Stirling’s approximation
formula for factorials ($n!=\Theta(n^{n+0.5}e^{-n})$), we obtain the claimed
bound, as shown below.

$\displaystyle T_{\mu}$
$\displaystyle\lesssim\frac{n^{0.5+n}e^{-n+\left(n\sum_{i}{\beta_{i}}\right)}}{\prod_{i}(\beta^{\prime}_{i}n)^{\left(\beta^{\prime}_{i}n-1+(-1)^{i}\frac{1}{2}\right)}(\beta_{i}^{\prime}n)^{\frac{3+(-1)^{i}}{2n}}}$
$\displaystyle\lesssim\frac{n^{0.5+n}}{\prod_{i}(\beta^{\prime}_{i}n)^{\left(\beta^{\prime}_{i}n-1+(-1)^{i}\frac{1}{2}\right)}}$
$\displaystyle\lesssim\frac{n^{0.5+n-n\sum_{i}\beta^{\prime}_{i}+4}}{\left(\prod_{i}{\beta_{i}^{{}^{\prime}\beta^{\prime}_{i}n}}\right)}=\frac{n^{6.5}}{\left(\prod_{i}{\beta_{i}^{{}^{\prime}\beta^{\prime}_{i}}}\right)^{n}}\lesssim
n^{6.5}\beta^{n}$

In the above derivation, $\lesssim$ denotes that the quantity on the left-hand
side is less than or approximately equal to the quantity on the right-hand
side up to a multiplicative constant. We set
$\beta_{i}^{\prime}=\beta_{i}-\frac{3+(-1)^{i}}{2n}$. To justify the last
inequality, consider the fact that $0<\beta^{\prime}_{i}<1$, which implies
$\beta_{i}^{{}^{\prime}\beta^{\prime}_{i}}\geq 2/3$. Hence, taking
$\beta\geq\frac{81}{16}$ completes the derivation. Now, for the fraction on
the right-hand side of Equation 7, we observe that the absolute value of the
denominator is

$\displaystyle\absolutevalue{n(n-1)(\mu_{1}+l-1)(\mu_{1}+r-2)(\mu_{2}+l-2)(\mu_{2}+r-3)}\gtrsim
n^{4},$

and the numerator is

$\displaystyle\absolutevalue{(\mu_{1}^{2}+\mu_{2}^{2}-\mu_{1}-3\mu_{2}+l-l^{2}-(r-3)r)(\mu_{1}-\mu_{2}+1)(l-r+1)}\lesssim
n^{4}.$

Hence, we conclude that $\absolutevalue{\chi_{\mu}([\sigma])}\lesssim
T_{\mu}$, which proves the lemma. ∎

######  Lemma 9.

If $\mu\in\Xi_{n}$ and $\chi_{\mu}([\sigma])\neq 0$, then for any non-trivial
singular value, we have $\lambda_{\mu}\leq 1-\frac{2}{n-1}$.

###### Proof.

Combining Equations 5 and 6, we obtain

$\displaystyle\tilde{\lambda_{\mu}}$
$\displaystyle=\frac{\chi_{\mu}([\sigma])}{\dim\rho_{\mu}}=\frac{1}{n(n-1)}\left(\sum_{j=1}^{l}(\mu_{j}-j+1)(\mu_{j}-j)-j(j-1)\right)$
$\displaystyle=\frac{\mu_{1}^{2}+\mu_{2}^{2}-\mu_{1}-3\mu_{2}+l-l^{2}-(r-3)r}{n(n-1)},$
(8)

where the last equality follows from the proof of Lemma 8. If
$\mu\in\Xi_{n,k}$, then from Lemma 7, we see that
$\absolutevalue{\tilde{\lambda_{\mu}}}\leq\frac{n-3}{n-1}$. For any
$\mu^{\prime}\in\Xi_{n}\setminus\Xi_{n,k}$, it can be easily verified from
Equation 5.1 that
$\absolutevalue{\tilde{\lambda_{\mu^{\prime}}}}\leq\absolutevalue{\tilde{\lambda_{\mu}}}$.
∎

###  5.2 Computing the divergence from the uniform distribution

Let $\vec{u}_{[n]}$ be the normalized vector (in the $\ell_{2}$ norm)
corresponding to the distribution over $\mathcal{S}_{n}$, which is uniformly
supported over the $n$-cycles. Let $\vec{u}$ represent the uniform
distribution over elements of $\mathcal{S}_{n}$. Their inner product is given
by $\innerproduct{\vec{u}_{[n]}}{\vec{u}}=\frac{1}{\sqrt{n}}$. For some
normalized distribution vector $\vec{u^{\prime}}$, the quantity
$\absolutevalue{\frac{1}{\sqrt{n}}-\innerproduct{\vec{u}_{[n]}}{\vec{u^{\prime}}}}$
serves as a measure of the distance between $\vec{u}$ and $\vec{u^{\prime}}$.
In the quantum walk setting, we can use the state $\ket{\psi_{[n]}}$ in place
of $\vec{u}_{[n]}$. We aim to determine the norm of the projection of
$\ket{\psi_{(n)}}$ onto
$\operatorname{\mathcal{W}}^{t}\ket{\psi_{\mathbb{e}}}$, as discussed earlier.
In this section, we set out to explicitly determine this projection.

######  Lemma 10 (projection lemma).

Given $\ket{\rho_{\mu,i,j}},A,B,S,f,\ket{\psi_{\mathbb{e}}}$ and
$\ket{\psi_{[n]}}$ as defined earlier the following holds for the operator
$\operatorname{\mathcal{W}}$:

  1. 1.

$\bra{\rho_{\mu,i,j}}A^{\dagger}\ket{\psi_{\mathbb{e}}}=\delta_{ij}$

  2. 2.

$\bra{\rho_{\mu,i,j}}B^{\dagger}\ket{\psi_{\mathbb{e}}}=\frac{\delta_{ij}\chi_{\mu}([\sigma])}{\dim\rho_{\mu}}$

  3. 3.

$\bra{\psi_{[n]}}A\ket{\rho_{\mu,i,j}}=\frac{\sqrt{(n-1)!}\delta_{ij}\chi_{\mu}([n])}{\dim\rho_{\mu}}$

  4. 4.

$\bra{\psi_{[n]}}B\ket{\rho_{\mu,i,j}}=\frac{\delta_{ij}}{d\sqrt{(n-1)!}\dim\rho_{\mu}}\left(\sum_{[\tau]}\absolutevalue{[\tau]}\Upsilon([\tau])\chi_{\mu}([\tau])\right)$
where $\Upsilon(g)=\sum_{h\in[n]}f(g^{-1}h)$.

where the last sum is over the conjugacy classes of $\mathcal{S}_{n}$.

###### Proof.

We only prove the relations $2-4$ as the first one is easy to check. In what
follows we denote $d=\absolutevalue{S}={n\choose 2}$. Recall,
$B=\sum_{g\in\mathcal{S}_{n}}\ket{\phi^{\prime}_{g}}\bra{g}$, where
$\ket{\phi^{\prime}_{g}}=\frac{1}{\sqrt{d}}\sum_{s\in S}\ket{gs^{-1},g}$.
Then,

$\displaystyle B^{\dagger}\ket{\psi_{\mathbb{e}}}=\sum_{g\in
G}\innerproduct{\phi^{\prime}_{g}}{\psi_{\mathbb{e}}}\ket{g}=\frac{1}{d}\sum_{s\in
S}\ket{s}$

Hence,

$\displaystyle\bra{\rho_{\mu,i,j}}B^{\dagger}\ket{\psi_{\mathbb{e}}}$
$\displaystyle=\frac{1}{d}\sum_{s\in
S}\rho_{\mu}(s)[i,j]^{*}=\frac{1}{d}\sum_{s\in
S}\rho_{\mu}(s)[i,j]=\frac{1}{d}\sum_{g\in G}X_{S}(g)\rho_{\mu}(g)[i,j]$
$\displaystyle=\frac{\hat{X}_{S}(\rho_{\mu})[i,j]}{d}=\frac{\delta_{ij}\chi_{\mu}([\sigma])}{\dim\rho_{\mu}}$

Similarly,

$\displaystyle\bra{\psi_{[n]}}A$
$\displaystyle=\frac{1}{\sqrt{(n-1)!}}\sum_{g\in[n]}\innerproduct{\phi_{g}}{\phi_{g}}\bra{g}=\frac{1}{\sqrt{(n-1)!}}\sum_{g\in[n]}\bra{g}$
$\displaystyle\bra{\psi_{[n]}}A\ket{\rho_{\mu,i,j}}$
$\displaystyle=\frac{1}{\sqrt{(n-1)!}}\sum_{g\in[n]}\bra{g}\ket{\rho_{\mu,i,j}}=\frac{1}{\sqrt{(n-1)!}}\sum_{g\in[n]}\rho_{\mu}(g)[i,j]$
$\displaystyle=\frac{1}{\sqrt{(n-1)!}}\sum_{g\in
G}X_{[n]}(g)\rho_{\mu}(g)[i,j]=\frac{\sqrt{(n-1)!}\delta_{ij}\chi_{\mu}([n])}{\dim\rho_{\mu}}$

and

$\displaystyle\bra{\psi_{[n]}}B$
$\displaystyle=\frac{1}{\sqrt{(n-1)!}}\sum_{h\in[n]}\sum_{g\in
G}\innerproduct{\phi_{h}}{\phi^{\prime}_{g}}\bra{g}=\frac{1}{d\sqrt{(n-1)!}}\sum_{g\in
G}\sum_{h\in[n]}f(g^{-1}h)\bra{g}$
$\displaystyle\bra{\psi_{[n]}}B\ket{\rho_{\mu,i,j}}$
$\displaystyle=\frac{1}{d\sqrt{(n-1)!}}\sum_{g\in
G}\rho_{\mu}(g)[i,j]\sum_{h\in[n]}f(g^{-1}h)$

Let, $\Upsilon(g)=\sum_{h\in[n]}f(g^{-1}h)$. Since $f$ is a class function,
$\Upsilon(tgt^{-1})=\sum_{h\in[n]}f(tg^{-1}t^{-1}h)=\sum_{h\in[n]}f(g^{-1}t^{-1}ht)=\Upsilon(g)$.
Hence, $\Upsilon$ is a class function. Thus,

$\displaystyle\bra{\psi_{[n]}}B\ket{\rho_{\mu,i,j}}$
$\displaystyle=\frac{1}{d\sqrt{(n-1)!}}\hat{\Upsilon}(\rho_{\mu})[i,j]=\frac{\delta_{ij}}{d\sqrt{(n-1)!}\dim\rho_{\mu}}\left(\sum_{[\tau]}\absolutevalue{[\tau]}\Upsilon([\tau])\chi_{\mu}([\tau])\right)$

where the last sum is taken over the conjugacy classes of $\mathcal{S}_{n}$,
and $\hat{\Upsilon}$ denotes the Fourier transform of $\Upsilon$ (as defined
in Section 2.1.3). ∎

Let,

$\displaystyle\gamma_{\mu}=\frac{1}{\dim\rho_{\mu}}\left(\sum_{[\tau]}\absolutevalue{[\tau]}\Upsilon([\tau])\chi_{\mu}([\tau])\right)=\frac{\tilde{\gamma}_{\mu}}{\dim\rho_{\mu}}$
(9)

Deriving the exact expression for $\gamma_{\mu}$ is quite challenging.
Instead, we will attempt to find asymptotic bounds for them, which will serve
our intended purpose.

######  Lemma 11.

If $S$ is the class of transpositions and $\Upsilon$ is as defined in Lemma
10,

$\displaystyle\Upsilon(g)=\begin{cases}\mbox{$l(n-l)$ if $g\in[(l,n-l)]$
and}\\\ \mbox{$0$ otherwise}\end{cases}$

###### Proof.

The proof follows directly from an application of Fact 2 and a straightforward
counting argument. ∎

Let $\mathcal{H}=\\{[(l,n-l)]\mid 1\leq l\leq n\\}$, and we identify the
elements of $\mathcal{H}$ with $\tau_{l}$. In equation 9, we only need to
consider the sum over $\mathcal{H}$. The following lemma is a consequence of
Lemma 11.

######  Lemma 12.

For any $\mu$, we have $\tilde{\gamma}_{\mu}=n!\iota_{\mu}$, where

$\displaystyle\iota_{\mu}=\begin{cases}\mbox{$\sum_{l=1}^{\lfloor
n/2\rfloor}\chi_{\mu}([\tau_{l}])$ if $n$ is odd}\\\
\mbox{$\sum_{l=1}^{\lfloor
n/2\rfloor-1}\chi_{\mu}([\tau_{l}])+\frac{n!}{2}\chi_{\mu}([\tau_{n/2}])$
otherwise}\end{cases}$

###### Proof.

Note that $\absolutevalue{[\tau_{l}]}={n\choose
l}(l-1)!(n-l-1)!=\frac{n!}{l(n-l)}$ except when $n$ is even and $l=n/2$, in
that case, $\absolutevalue{[\tau_{n/2}]}=\frac{2(n-1)!}{n}$. ∎

If $\mu\in\Xi_{n,k}$ we can be more specific.

######  Corollary 13.

If $\mu\in\Xi_{n,k}$ and $\tau_{l}\in\mathcal{H}$ then

$\displaystyle\tilde{\gamma}_{\mu}=\begin{cases}\mbox{$\frac{1}{2}(-1)^{n-k-1}(n-2k+1)n!$\
\ \ if $n$ is odd}\\\ \mbox{$\frac{1}{2}(-1)^{n-k-1}(n-2k+\frac{4}{n^{2}})n!$
\ \ \ otherwise}\end{cases}$

###### Proof.

Using Fact 5 and Lemma 12 we have,

$\displaystyle\tilde{\gamma}_{\mu}$ $\displaystyle=\sum_{l\geq k}^{\lfloor
n/2\rfloor}{\absolutevalue{[\tau_{l}]}l(n-l)(-1)^{n-k-1}}=\begin{cases}\mbox{$\frac{1}{2}(-1)^{n-k-1}(n-2k+1)n!$\
\ \ if $n$ is odd}\\\ \mbox{$\frac{1}{2}(-1)^{n-k-1}(n-2k+\frac{4}{n^{2}})n!$
\ \ \ otherwise}\end{cases}$

∎

In the next lemma, we show that the component
$\operatorname{\mathcal{W}}_{A,B}$ can be ignored in the spectral
decomposition of the walk operator. This greatly simplifies the analysis and
allows us to focus on the action of $\operatorname{\mathcal{W}}$ on the space
orthogonal to the trivial singular values of $D$.

######  Lemma 14.

Given
$\operatorname{\mathcal{W}}_{A,B}^{t},\ket{\psi_{[n]}},\ket{\psi_{\mathbb{e}}}$
as defined earlier
$\bra{\psi_{[n]}}\operatorname{\mathcal{W}}_{A,B}^{t}\ket{\psi_{\mathbb{e}}}=0$.

###### Proof.

We have
$\operatorname{\mathcal{W}}_{A,B}^{t}=\Pi_{+1}+(-1)^{t}\Pi_{-1}=\Pi_{\operatorname{col}(A)\cap\operatorname{col}(B)}+\Pi_{\ker(A)\cap\ker(B)}+(-1)^{t}\Pi_{\operatorname{col}(A)\cap\ker(B)}+(-1)^{t}\Pi_{\ker(A)\cap\operatorname{col}(B)}$.
Since $\ket{\phi_{\mathbb{e}}}\in\operatorname{col}(A)$,

$\displaystyle\operatorname{\mathcal{W}}_{A,B}^{t}\ket{\phi_{\mathbb{e}}}=(\Pi_{\operatorname{col}(A)\cap\operatorname{col}(B)}+(-1)^{t}\Pi_{\operatorname{col}(A)\cap\ker(B)})\ket{\phi_{\mathbb{e}}}=\begin{cases}\mbox{$\ket{\phi_{\mathbb{e}}}$
if $t$ is even}\\\ \mbox{$(2\Pi_{B}-I)\ket{\phi_{\mathbb{e}}}$
otherwise}\end{cases}$

In either case, we have
$\bra{\phi_{[n]}}\operatorname{\mathcal{W}}_{A,B}^{t}\ket{\phi_{\mathbb{e}}}=0$.
Intuitively, this is because $\ket{\phi_{[n]}}$ has positive support only on
the conjugacy class $[n]$, while
$\operatorname{\mathcal{W}}_{A,B}^{t}\ket{\phi_{\mathbb{e}}}$ has support
solely on $[\sigma]\cup\\{\mathbb{e}\\}$ in their first register,
respectively. ∎

From the above lemma, it follows that
$\bra{\phi_{[n]}}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}=\sum_{\mu\vdash
n}\bra{\phi_{[n]}}\operatorname{\mathcal{W}}_{\mu}^{t}\ket{\phi_{\mathbb{e}}}$.
Finally, we are ready to prove our main theorem.

See 1

###### Proof.

Using the spectral idempotents in the decomposition of
$\operatorname{\mathcal{W}}_{\mu}^{t}$ from Equation 4, we derive the
following intermediate terms.

$\displaystyle\alpha_{1}(\mu)=\bra{\phi_{[n]}}$
$\displaystyle(A\Pi_{\mu}A^{\dagger}+B\Pi_{\mu}B^{\dagger})\ket{\phi_{\mathbb{e}}}$
$\displaystyle=\frac{\dim\rho_{\mu}}{n!}\sum_{1\leq
i,j\leq\dim\rho_{\mu}}\left(\bra{\phi_{[n]}}A\ket{\rho_{\mu,i,j}}\bra{\rho_{\mu,i,j}}A^{\dagger}\ket{\phi_{\mathbb{e}}}+\bra{\phi_{[n]}}B\ket{\rho_{\mu,i,j}}\bra{\rho_{\mu,i,j}}B^{\dagger}\ket{\phi_{\mathbb{e}}}\right)$
$\displaystyle=\frac{\dim\rho_{\mu}}{n!}\sum_{1\leq
i,j\leq\dim\rho_{\mu}}\delta_{ij}\left(\frac{\sqrt{(n-1)!}\chi_{\mu}([n])}{\dim\rho_{\mu}}+\frac{\chi_{\mu}([\sigma])\tilde{\gamma}_{\mu}}{d\sqrt{(n-1)!}\dim^{2}\rho_{\mu}}\right)$
$\displaystyle=\frac{\dim\rho_{\mu}}{n!}\left(\sqrt{(n-1)!}\chi_{\mu}([n])+\frac{\chi_{\mu}([\sigma])\tilde{\gamma}_{\mu}}{d\sqrt{(n-1)!}\dim\rho_{\mu}}\right)$

Similarly, we have

$\displaystyle\alpha_{2}(\mu)=\bra{\phi_{[n]}}A\Pi_{\mu}B^{\dagger}\ket{\phi_{\mathbb{e}}}=\frac{\chi_{\mu}([n])\chi_{\mu}([\sigma])}{n\sqrt{(n-1)!}}$

and

$\displaystyle\alpha_{3}(\mu)=\bra{\phi_{[n]}}B\Pi_{\mu}A^{\dagger}\ket{\phi_{\mathbb{e}}}=\frac{\tilde{\gamma}_{\mu}}{dn!\sqrt{(n-1)!}}$

We can rewrite $\alpha_{1}(\mu)$ as:

$\displaystyle\alpha_{1}(\mu)=\frac{\dim\rho_{\mu}}{\chi_{\mu}([\sigma])}\alpha_{2}(\mu)+\chi_{\mu}([\sigma])\alpha_{3}(\mu)$

If $\mu\in\Xi_{n,k}$ where $\mu=(k,1,\ldots,1)$ then,

$\displaystyle\alpha_{2}(\mu)$ $\displaystyle=\frac{(-1)^{n-k}{n-1\choose
k-1}(n-2k+1)}{m}$ and $\displaystyle\alpha_{3}(\mu)$
$\displaystyle\approxeq\frac{b_{n,k}}{m}$ thus $\displaystyle\alpha_{1}(\mu)$
$\displaystyle=\frac{(n-1)(-1)^{n-k+1}}{m}{n-1\choose
k-1}\left(1+\frac{(-1)^{n-k}b_{n,k}(n-2k+1)}{(n-1)^{2}}\right)$

where $m=n(n-1)\sqrt{(n-1)!}$ and

$\displaystyle b_{n,k}=\begin{cases}\mbox{$(-1)^{k}(n-2k)$\ \ \ if $n$ is
odd}\\\ \mbox{$(-1)^{k-1}(n-2k)$ \ \ \ otherwise}\end{cases}$

Else if $\mu\in\Xi_{n}\setminus\Xi_{n,k}$ then:

$\displaystyle\alpha_{2}(\mu)$ $\displaystyle=0\ \mbox{\ , since
$\chi_{\mu}([n])=0$}$ and $\displaystyle\alpha_{3}(\mu)$
$\displaystyle=\frac{2\iota_{\mu}}{m}$

Now,

$\displaystyle\bra{\phi_{[n]}}\operatorname{\mathcal{W}}_{\mu}^{t}\ket{\phi_{\mathbb{e}}}$
$\displaystyle=\frac{1}{2(1-\lambda^{2}_{\mu})}\left(\alpha_{1}(\mu)\cos(2\theta_{\mu}t)-s_{\mu}\alpha_{2}(\mu)\cos(2\theta_{\mu}(t-1/2))-s_{\mu}\alpha_{3}(\mu)\cos(2\theta_{\mu}(t+1/2))\right)$

Let $c_{1}=\cos(2\theta_{\mu}t),c_{2}=\cos(2\theta_{\mu}(t-1/2))$ and
$c_{3}=\cos(2\theta_{\mu}(t+1/2))$. To compute
$\bra{\phi_{[n]}}\operatorname{\mathcal{W}}_{\mu}^{t}\ket{\phi_{\mathbb{e}}}$
we only need to sum over $\mu\in\Xi_{n}$. Thus,

$\displaystyle\sum_{\mu\in\Xi_{n}}\bra{\phi_{[n]}}\operatorname{\mathcal{W}}_{\mu}^{t}\ket{\phi_{\mathbb{e}}}$
$\displaystyle\leq\frac{1}{2m}\sum_{\mu\in\Xi_{n}}\frac{1}{1-\lambda_{\mu}^{2}}\left(\alpha_{1}(\mu)-s_{\mu}\alpha_{2}(\mu)c_{2}-s_{\mu}\alpha_{3}(\mu)c_{3}\right)$
$\displaystyle=\frac{1}{2m}\sum_{\mu\in\Xi_{n}\setminus\Xi_{n,k}}\frac{1}{1-\lambda_{\mu}^{2}}\left(2(\chi_{\mu}([\sigma])-s_{\mu}c_{3})\iota_{\mu}\right)$
$\displaystyle+\frac{1}{2m}\sum_{\mu\in\Xi_{n,k}}\frac{1}{1-\lambda_{\mu}^{2}}P(n,k,\mu)$
(10)

where,

$\displaystyle P(n,k,\mu)$
$\displaystyle=\frac{(n-1)(-1)^{n-k+1}}{m}{n-1\choose
k-1}\left(1+\frac{(-1)^{n-k}b_{n,k}(n-2k+1)}{(n-1)^{2}}\right)$
$\displaystyle-s_{\mu}{n-1\choose
k-1}(-1)^{n-k}(n-2k+1)c_{2}-s_{\mu}b_{n,k}c_{3}$

Next, we use Lemmas 6 through 9:

  1. 1.

Since each $\chi_{\mu}([\tau_{l}])\in\\{-1,0,1\\}$ (by Lemma 6), we have
$\absolutevalue{\iota_{\mu}}\leq n/2$.

  2. 2.

From Lemma 8, we have $\chi_{\mu}([\sigma])=O(n^{6.5}\beta^{n})$ (for any
$\beta>81/16$).

  3. 3.

Additionally, Lemma 9 yields $\frac{1}{1-\lambda_{\mu}^{2}}\leq\frac{n}{2}$
for $n\geq 2$ and for any $\mu\in\Xi_{n}$.

Thus for any $\mu\in\Xi_{n}\setminus\Xi_{n,k}$,

$\displaystyle\frac{1}{1-\lambda_{\mu}^{2}}\left(2(\chi_{\mu}([\sigma])-s_{\mu}c_{3})\iota_{\mu}\right)=O(n^{8.5}\beta^{n})$
(11)

We also have,

$\displaystyle P(n,k,\mu)=O\left(n^{2}{n-1\choose k-1}\right)$

for $\mu\in\Xi_{n,k}$. Hence,

$\displaystyle\frac{1}{1-\lambda_{\mu}^{2}}P(n,k,\mu)=O(n^{3}2^{n})$ (12)

Using Fact 4 and substituting the expression for the left-hand side of
Equations 11 and 12 into equation 5.2, we obtain:

$\displaystyle\sum_{\mu\in\Xi_{n}}\bra{\phi_{[n]}}\operatorname{\mathcal{W}}_{\mu}^{t}\ket{\phi_{\mathbb{e}}}=O\left(\frac{n^{10}\beta^{n}}{\sqrt{n!}}\right)$

Thus,

$\displaystyle\norm{\bra{\phi_{[n]}}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}}=O\left(\frac{n^{20}{\beta}^{2n}}{n!}\right)$

∎

###  5.3 Computing the probability of observing $\ket{g,gs}$ for some
$g\in[n]$

Here, we provide a brief discussion on why the above analysis fails (at least
when applied directly) if we consider determining the probability of detecting
a basis state $\ket{g,gs}$, where $g$ is an $n$-cycle. The key to our analysis
was the projection lemma (Lemma 10). However, in this case, we are not dealing
solely with class functions, which implies explicit computation of the irreps
that lack straightforward analytical expressions. More specifically, we wish
to compute $\sum_{s\in
S}\norm{\bra{g,gs}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}}$.
Additionally, due to our choice of the starting state, the individual
probabilities
$\norm{\bra{g,gs}\operatorname{\mathcal{W}}^{t}\ket{\phi_{\mathbb{e}}}}$ do
not depend on $s$. Now,

$\displaystyle\bra{g,gs}B\ket{\rho_{\mu,i,j}}=\frac{1}{\sqrt{d}}\sum_{h\in
G}f_{S}(g^{-1}h)\rho_{\mu}(h)[i,j]$

However, the function $f_{g}(h)=f(g^{-1}h)$ is not a class function, as can be
easily seen. Thus, we cannot use the projection lemma in the manner we did
earlier without knowing the irreps explicitly.

## References

  * [1] Acevedo, O.L., Gobron, T.: Quantum walks on cayley graphs. Journal of Physics A: Mathematical and General 39(3), 585 (2005)
  * [2] Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing. pp. 50–59 (2001)
  * [3] Aharonov, Y., Davidovich, L., Zagury, N.: Quantum random walks. Physical Review A 48(2), 1687 (1993)
  * [4] Aliferis, G., Leontaris, G., Vlachos, N.: Sl (2, 7) representations and their relevance to neutrino physics. The European Physical Journal C 77(6), 1–11 (2017)
  * [5] Ambainis, A.: Quantum random walks–new method for designing quantum algorithms. In: International Conference on Current Trends in Theory and Practice of Computer Science. pp. 1–4. Springer (2008)
  * [6] Apers, S.: Expansion testing using quantum fast-forwarding and seed sets. Quantum 4, 323 (2020)
  * [7] Babai, L.: Local expansion of vertex-transitive graphs and random generation in finite groups. In: Proceedings of the twenty-third annual ACM symposium on Theory of computing. pp. 164–174 (1991)
  * [8] Banerjee, A.: Discrete quantum walks on the symmetric group. arXiv preprint arXiv:2203.15148 (2022)
  * [9] Barak, B., Chou, C.N., Gao, X.: Spoofing linear cross-entropy benchmarking in shallow quantum circuits. arXiv preprint arXiv:2005.02421 (2020)
  * [10] Bouland, A., Fefferman, B., Nirkhe, C., Vazirani, U.: Quantum supremacy and the complexity of random circuit sampling. arXiv preprint arXiv:1803.04402 (2018)
  * [11] Bump, D., Diaconis, P., Hicks, A., Miclo, L., Widom, H.: An exercise (?) in fourier analysis on the heisenberg group. In: Annales de la Faculté des sciences de Toulouse: Mathématiques. vol. 26, pp. 263–288 (2017)
  * [12] Chan, A., Zhan, H.: Pretty good state transfer in discrete-time quantum walks. Journal of Physics A: Mathematical and Theoretical 56(16), 165305 (2023)
  * [13] Coutinho, G., Godsil, C.: Graph spectra and continuous quantum walks. Unpublished notes (2021)
  * [14] Dai, W., Yuan, J., Li, D.: Discrete-time quantum walk on the cayley graph of the dihedral group. Quantum Information Processing 17(12), 1–21 (2018)
  * [15] Diaconis, P.: Group representations in probability and statistics. Lecture notes-monograph series 11, i–192 (1988)
  * [16] Diaconis, P., Shahshahani, M.: Generating a random permutation with random transpositions. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 57(2), 159–179 (1981)
  * [17] D’Ariano, G.M., Erba, M., Perinotti, P., Tosini, A.: Virtually abelian quantum walks. Journal of Physics A: Mathematical and Theoretical 50(3), 035301 (2016)
  * [18] Farhi, E., Gutmann, S.: Quantum computation and decision trees. Physical Review A 58(2), 915 (1998)
  * [19] Floratos, E., Leontaris, G.: Discrete flavour symmetries from the heisenberg group. Physics Letters B 755, 155–161 (2016)
  * [20] Gerhardt, H., Watrous, J.: Continuous-time quantum walks on the symmetric group. In: Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques, pp. 290–301 (2003)
  * [21] Godsil, C.: Average mixing of continuous quantum walks. Journal of Combinatorial Theory, Series A 120(7), 1649–1662 (2013)
  * [22] Kendon, V.: Decoherence in quantum walks–a review. Mathematical Structures in Computer Science 17(6), 1169–1220 (2007)
  * [23] Knittel, M., Bassirian, R.: Quantum random walks on cayley graphs
  * [24] Lee, J.R., Naor, A.: Lp metrics on the heisenberg group and the goemans-linial conjecture. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). pp. 99–108. IEEE (2006)
  * [25] Lovász, L.: Random walks on graphs. Combinatorics, Paul erdos is eighty 2(1-46), 4 (1993)
  * [26] Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. SIAM journal on computing 40(1), 142–164 (2011)
  * [27] Meyer, D.A.: From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics 85(5), 551–574 (1996)
  * [28] Moore, C., Russell, A.: Quantum walks on the hypercube. In: International Workshop on Randomization and Approximation Techniques in Computer Science. pp. 164–178 (2002)
  * [29] Nayak, A., Vishwanath, A.: Quantum walk on the line. arXiv preprint quant-ph/0010117 (2000)
  * [30] Osborne, T.J., Severini, S.: Quantum algorithms and covering spaces. arXiv preprint quant-ph/0403127 (2004)
  * [31] RE Ingram, S.: Some characters of the symmetric group. Proceedings of the American Mathematical Society pp. 358–369 (1950)
  * [32] Sagan, B.E.: The symmetric group: representations, combinatorial algorithms, and symmetric functions, vol. 203. Springer Science & Business Media (2013)
  * [33] Sarkar, R.S., Adhikari, B.: Discrete-time quantum walks on cayley graphs of dihedral groups using generalized grover coins. arXiv preprint arXiv:2309.15194 (2023)
  * [34] Sorci, J.: Average mixing in quantum walks of reversible markov chains. arXiv preprint arXiv:2211.02037 (2022)
  * [35] Szegedy, M.: Quantum speed-up of markov chain based algorithms. In: 45th Annual IEEE symposium on foundations of computer science. pp. 32–41. IEEE (2004)
  * [36] Terras, A.: Fourier analysis on finite groups and applications. No. 43, Cambridge University Press, Cambridge (1999)
  * [37] Venegas-Andraca, S.E.: Quantum walks: a comprehensive review. Quantum Information Processing 11(5), 1015–1106 (2012)
  * [38] Wallace, D.: G. james and a. kerber, the representation theory of the symmetric group (encyclopedia of mathematics and its applications, vol. 16, addison-wesley, reading, mass., 1981), pp. 510,£ 37.80. Proceedings of the Edinburgh Mathematical Society 27(1), 103–104 (1984)
  * [39] Zack, M.: Measuring randomness and evaluating random number generators using the finite heisenberg group. Limit theorems in probability and statistics (Pécs, 1989) 57, 537–544 (1990)