Non-uniform Mixing of Quantum Walks on the Symmetric Group

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.

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.

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.

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.

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})$ ⁴⁴4A 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$.

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.

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.

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 outgoing⁵⁵5Even 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.