1. General introduction
Background. Quantum computing promises algorithmic speedup compared to its classical counterpart [1–5]. Most of the quantum advantage campaigns are based on digital circuits [6–8], such as Grover's amplitude amplification [5], Shor's quantum Fourier transform [4], etc. However, analog or hybrid algorithms associated with sampling problems are attracting more and more interest in the NISQ era because of the efforts to push forward the application of quantum computing, such as QAOA, Metropolisá-Hashing, and Hybrid Monte Carlo [8–11]. Among these algorithms, quantum walk emerges as a promising option for NISQ devices by showcasing exponential speedups of the hitting process on some graph structures for searching problems [12]. The study of quantum walks has further extended to investigate mixing time on various graphs such as Erdos Renyi networks [13]. This could help solve problems from a class of #P complete problems—the approximate sampling problems [14]. Notably, two specific problems, namely sampling a uniform permutation through card shuffling and reaching the Gibbs state using Glauber dynamics, are equivalent, e.g. for [15,16]. It shows how probability theory and statistical mechanics are interlinked. The card shuffling problem can be viewed as a random walk on symmetric group Sn. Both discrete and continuous time quantum walks have been performed on the Sn group to determine the mixing time [17,18].
Issues. Extensive research has shown that quantum walks have exponential advantages compared to classical random walks on certain graphs [3,14,19–22]. A few families of Cayley graphs have also been explored, such as Cayley graphs of Extraspecial groups [23]. There is recent work on well-known graphs like the Johnson, Kneser, Grassman, and Rook graphs to sample (exact) uniformly using quantum walk [24]. However, the quantum walk mixing time on Cayley graphs of the non-Abelian group is still not settled. Cayley graphs are an essential class of graphs for quantum walks because they are generated from groups and can be used to design quantum algorithms that exploit the symmetries and properties of the underlying group structure. Previously, properties like perfect state transfer, hitting time, and instantaneous uniform mixing have been verified on Cayley graphs of non-abelian groups [25–28]. Also, they can be used to study the quantum dynamics and transport phenomena on discrete structures, such as quantum coherence, entanglement, mixing, localization, and phase transitions [29]. Mathematically, a group is a set of elements equipped with an operation that satisfies closure, associativity, identity, and inverse properties [30]. Cayley graphs visually represent the symmetries of the group. The vertices of the Cayley graph are elements of the groups, and edges show how these elements relate to each other through the groups' operations.
Methodology. Proving the mixing time involves two main components: determining how long it takes for the mixing process to reach the limiting distribution (which may not be uniform) and exploring the possibility of uniform sampling from this distribution. Previously, it has been proved that continuous-time quantum walks with repeated measurements on certain Cayley graphs of a symmetric group Sn do not converge to the uniform distribution [17]. A remedy is given in reference [14], where Richter gave a double loop quantum walk algorithm for uniform sampling using quantum walks. He demonstrated that performing approximately $O(\mathrm{log}(1/\epsilon ))$ iterations of the quantum walk e−iPt, where P is a classical Markov chain on the underlying graph Γ, and selecting t uniformly at random from the interval [0, T], is sufficient to sample uniformly. This study focuses on the Cayley graphs of the dihedral group (D2n). This group symmetries of a regular polygon; reflection and rotation are the elements with composition operation. We use the same algorithms as Richter's to show the quadratic speedup on D2n. We numerically depict the quantum walk speedup in figure 1. By utilizing lower bounds on mixing time for regular graphs, we establish that classical random walks on Cayley graphs of D2n require at least ${\rm{\Omega }}({n}^{2}\mathrm{log}(1/2\epsilon ))$ time to achieve uniform mixing [31]. To estimate the mixing time of quantum walks, we employ the upper bound on mixing time provided in the reference [13], which relies on eigenvalue gaps. We retrieve the adjacency matrix using the [32] method for the Cayley graph of dihedral groups to find the eigenvalues. The graph Γ is generated by a symmetric inverse closed subset S ∈ D2n and is isomorphic to the semi-Cayley graph of an n-cycle, i.e. ${\rm{\Gamma }}({D}_{2n},S)\cong {{\mathbb{Z}}}_{n}\rtimes {{\mathbb{Z}}}_{2}$. Our main result is that $O{(n(\mathrm{log}(n))}^{5})$ time is sufficient to mix the continuous-time quantum walk with repeated measurements on the dihedral group towards a uniform distribution with $O(\mathrm{log}(1/\epsilon ))$ iterations. To prove the main theorem, we propose a conjecture on the sum of the inverse of the difference in eigenvalue gaps for a subset of eigenvalues. We support the conjecture with simulations.
The work is organized as follows: The first section is dedicated to the preliminaries. Then, we discuss how to get the adjacency matrix for the Cayley graph Γ(D2n, S = {a, a−1, b}) from the semi-Cayley graphs. We give the general formulation to calculate the quantum walk amplitude. Subsequently, we calculate the limiting probability distribution on Cayley graphs of D2n. Later, we analyze the mixing time on the Cayley graphs of dihedral groups and show that it is linear in the number of vertices on the graph. We conclude the sections with the results and future directions. The supplementary material includes the quantum walk algorithm, analysis of bounds from the main theorem, conjecture, and derivation of limiting distribution, respectively.
2. Preliminaries
This section introduces key definitions and propositions related to the Cayley graph, groups, Markov chains, and mixing time [31] since the random walk is a special case of a Markov chain. The mixing time of a random or quantum walk refers to the duration it takes for the distribution of the walker to become ε distance close to its stationary distribution.
Cayley Graph: consider a finite G group and let $S\subseteq G$ be a symmetric subset of G, i.e. if $g\in S$, then ${g}^{-1}\in S$ for all $g\in G$. The Cayley graph is defined as ${\rm{\Gamma }}(G,S)$, where elements of G are the vertices of the graph Γ and an edge $(g,h)\in {\rm{\Gamma }}$ if and only if ${{gh}}^{-1}\in S$.
Suppose the size of S is d, then for every vertex in Γ has degree d. So, the Cayley graphs are d-regular graphs.
Conjugate: consider a group G, let $g,h\in G$ be conjugate if there exists $r\in G$ such that ${{rgr}}^{-1}=h$, then g is called a conjugate of h.
Semi-direct product: consider a group G, N as the normal subgroup, and H as a proper subgroup of G. If $G={NH}$ such that $N\cap H=\{e\}$, where e is the group's identity G, then G is called a semi-direct product of N and H. It can be written as $G=N\rtimes H$.
Semi-Cayley graphs: let G be a group and R, M, T be its subsets such that R and M are inverse closed and $e\notin R\cup M$. The semi-Cayley graph $\mathrm{SC}(G;R,M,T)$ with the vertex set $G\times \{0,1\}$. To have an edge between vertices (h, i) and (g, j), one of the following holds:
$i=j=0$ and ${{gh}}^{-1}\in R;$
$i=j=1$ and ${{gh}}^{-1}\in M;$
$i=0,j=1$ and ${{gh}}^{-1}\in T$.
A Markov chain is a stochastic process X0, X1, X2, ... with a countable set of states S, where the probability of transitioning from one state to another depends only on the current state. Mathematically, for any states i, j ∈ S and any time steps t ≥ 0, the Markov property can be expressed as:
P(Xt+1 = j∣Xt = i, Xt−1 = xt−1, ..., X1 = x1, X0 = x0) = P(Xt+1 = j∣Xt = i), where P(Xt+1 = j∣Xt = i) represents the probability of transitioning from state i to state j in a one-time step.
Markov chain P has a stationary distribution π implies that $P\pi =\pi $.
Consider an irreducible (strongly connected) and aperiodic (non-bipartite) Markov Chain P with a stationary distribution π. The mixing time(also known as threshold mixing) can be defined as follows:
$\begin{eqnarray}{\tau }_{\mathrm{mix}}=\min \left\{T:\displaystyle \frac{1}{2}\parallel {P}^{t}-\pi {1}^{\dagger }{\parallel }_{1}\leqslant \displaystyle \frac{1}{2e}\hspace{1mm}\forall \hspace{1mm}t\geqslant T\right\},\end{eqnarray}$
where $\parallel .{\parallel }_{1}$ is a matrix 1-norm and ${1}^{\dagger }$ is all one row vector.Given a Markov chain P
$\begin{eqnarray*}d(P)={\max }_{{jj}^{\prime} }\displaystyle \frac{1}{2}\parallel P(.,j)-P(.,j^{\prime} ){\parallel }_{1},\end{eqnarray*}$
is called the maximum pairwise column distance. The following inequality holds for d(P) $\begin{eqnarray}\displaystyle \frac{1}{2}\parallel P-\pi {1}^{\dagger }{\parallel }_{1}\leqslant d(P)\leqslant \parallel P-\pi {1}^{\dagger }{\parallel }_{1}.\end{eqnarray}$
The distance d(P) is submultiplicative, i.e.
$\begin{eqnarray}d({P}_{t+t^{\prime} })\leqslant d({P}_{t})d({P}_{t^{\prime} })\end{eqnarray}$
for any time t and $t^{\prime} $. This implies that $d{({P}_{t})\leqslant d(P)}^{t}$ and $d{({({P}_{t})}^{t^{\prime} })\leqslant d({P}_{t})}^{t^{\prime} }$.[33] If $d({P}_{T})\leqslant 1/2e$, then $\parallel {P}_{T}^{T^{\prime} }-\pi {1}^{\dagger }{\parallel }_{1}\leqslant \epsilon $ for some time $T^{\prime} =O(\mathrm{log}(1/\epsilon ))$.
3. Dihedral group
In this section, we discuss the dihedral group D2n, represented by symmetries of an n-regular polygon. We use the isomorphism given in the [32] between Γ(D2n, S) and semi-Cayley graph of ${{\mathbb{Z}}}_{n}$, allowing us to determine the adjacency matrix of Γ. The graph exhibits a unique structure, and the walks on D2n are equivalent to those on a specific semi-Cayley graph of ${{\mathbb{Z}}}_{n}$. The obtained adjacency matrix enables further analysis.
The dihedral group D2n is a finite group representing the symmetries of an n-regular polygon. It includes elements rotations and reflections and can be described abstractly as ⟨a, b∣an = 1, b2 = 1, bab = a−1⟩. With 2n elements, D2n explicitly includes {1, a, b, ba, ba2, ..., ban−1, a2, a3, ..., an−1}. To study quantum walks on D2n, we construct the Cayley graph Γ(D2n, S) using the symmetric subset S = {a, a−1, b} as the generating set. The adjacency matrix A(g, h) of Γ(D2n, S) is defined such that
$\begin{eqnarray}A(g,h)=\left\{\begin{array}{ll}1 & \ \mathrm{if}\ {{gh}}^{-1}\in S,\\ 0 & \ \mathrm{otherwise}\ .\end{array}\right.\end{eqnarray}$
This representation provides the foundation for analyzing quantum walks on Cayley graphs associated with the dihedral group D2n.To analyze continuous-time quantum walks on Γ(D2n, S), we can use an isomorphic counterpart, semi-Cayley graph on ${{\mathbb{Z}}}_{n}$ denoted as $\mathrm{SC}({{\mathbb{Z}}}_{n};R,M,T)$, where R = M = {1, n − 1}, T = {0}. This choice is advantageous because it simplifies the analysis. Here, ${{\mathbb{Z}}}_{n}$ represents a cyclic group of order n. Based on the findings in [32], we can determine the spectral properties of the adjacency matrix of Γ(D2n, S). According to lemma 4.2 in [32] and the definition of semi-Cayley graphs, there exists an isomorphism φ between Γ(D2n, S) and $\mathrm{SC}({{\mathbb{Z}}}_{n};R,M,T)$. The isomorphism is defined as φ(ar) = (r, 0) and φ(bar) = (n − r, 1) for r ∈ [0, n − 1]. Consequently, performing continuous-time quantum walks on the graph $\mathrm{SC}({{\mathbb{Z}}}_{n};R,M,T)$ is equivalent to conducting the same walks on Γ(D2n, S). The adjacency matrix is of $\mathrm{SC}({{\mathbb{Z}}}_{n};R,M,T)$ is given as follows:
$\begin{eqnarray}A=\left[\begin{array}{cc}{W}_{n}+{W}_{n}^{n-1} & I\\ I & {W}_{n}+{W}_{n}^{n-1}\end{array}\right].\end{eqnarray}$
Here, Wn is n × n a circulant matrix given below. $\begin{eqnarray*}{W}_{n}=\left[\begin{array}{ccccc}0 & 1 & 0 & ... & 0\\ 0 & 0 & 1 & ... & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & 0 & 0 & ... & 0\end{array}\right],\end{eqnarray*}$
with eigenvalues wj and eigenvectors ${v}_{j}^{{\rm{T}}}=(1/\sqrt{n}){[1,{w}^{j},{w}^{2j},\,...,\,{w}^{(n-1)j}]}^{{\rm{T}}}$ for 0 ≤ j ≤ n − 1, where w = e(2πi/n) and T is transpose. In the next section, we will discuss how to define a unitary evolution operator to do a quantum walk on Γ(D2n, S).4. Quantum walk on D2n
In this section, we state the eigenspectrum of the adjacency matrix A given in equation (5 ). Next, we provide the lower bound for the classical mixing time of a random walk on Γ(D2n, S). Afterwards, we discuss the time-averaged quantum walk probability and the limiting distribution of quantum walks on Γ.
The simple random walk matrix for regular graphs is simply the normalized adjacency matrix of the graph, i.e. $\bar{A}=\tfrac{A}{3}$. We use normalized adjacency matrix $\bar{A}$, which gives us the following normalized 2n eigenvalues and eigenvectors, respectively.
$\begin{eqnarray}{\lambda }_{j}=\left(1+2\cos (2\pi j/n)\right)/3,\end{eqnarray}$
$\begin{eqnarray}\left|{x}_{j}\right\rangle =\displaystyle \frac{1}{\sqrt{2n}}{\left[\begin{array}{cc}{v}_{j} & {v}_{j}\end{array}\right]}^{\dagger },\end{eqnarray}$
for 0 ≤ j ≤ (n − 1), and $\begin{eqnarray}{\lambda }_{j}=\left(2\cos \left(2\pi (j-n)/n\right)-1\right)/3,\end{eqnarray}$
$\begin{eqnarray}\left|{y}_{j}\right\rangle =\displaystyle \frac{1}{\sqrt{2n}}{\left[\begin{array}{cc}{v}_{j} & -{v}_{j}\end{array}\right]}^{\dagger },\end{eqnarray}$
for n ≤ j ≤ (2n − 1).To prove the classical mixing time lower bound on Γ(D2n, S), we use the theorem 12.5 given in [31] which states that for transition matrix P of a reversible, irreducible Markov chain then ${\tau }_{\mathrm{mix}}(\epsilon )\geqslant (1/(1-{\lambda }_{2})-1)\mathrm{log}\left(1/2\epsilon \right),$ where λ2 is the second largest eigenvalue.
Upon examining equation (5 ), it becomes evident that the simple random walk $\bar{A}$ on Γ(D2n, S) possesses key properties, namely symmetry (reversibility) and strong connectivity (irreducibility). Additionally, the Cayley graph Γ is regular, resulting in a uniform stationary distribution π, [31]. We can determine the second largest eigenvalue of $\bar{A}$ as ${\lambda }_{2}=\left(1+2\cos (2\pi /n)\right)/3$ using equation (6 ). By employing the inequality $1-\cos (x)\leqslant {x}^{2}/2,$ we find that
$\begin{eqnarray*}{\tau }_{\mathrm{mix}}(\epsilon )\geqslant (3{n}^{2}/4{\pi }^{2}-1)\mathrm{log}\left(1/2\epsilon \right).\end{eqnarray*}$
Consequently, the classical mixing time on Γ(D2n, S) is at least ${\rm{\Omega }}\left({n}^{2}\mathrm{log}\left(1/2\epsilon \right)\right)$.Now, we define the unitary operator. Based on the eigen-spectrum of $\bar{A}$, the continuous-time quantum walk operator $U(t)={{\rm{e}}}^{{\rm{i}}\bar{A}t}$ can be written as
$\begin{eqnarray}U(t)=\displaystyle \sum _{j=0}^{n-1}{{\rm{e}}}^{{\rm{i}}{\lambda }_{j}t}\left|{x}_{j}\rangle \langle {x}_{j}\right|+\displaystyle \sum _{j=n}^{2n-1}{{\rm{e}}}^{{\rm{i}}{\lambda }_{j}t}\left|{y}_{j}\rangle \langle {y}_{j}\right|.\end{eqnarray}$
Let us define ${X}_{j}:= \left|{x}_{j}\rangle \langle {x}_{j}\right|$ and ${Y}_{j}:= \left|{y}_{j}\rangle \langle {y}_{j}\right|$ for 0 ≤ j ≤ (2n − 1) respectively. Then the probability to go from some vertex $\left|p\right\rangle $ to another vertex $\left|q\right\rangle $ on the graph Γ(D2n, S) in time t is given by $\begin{eqnarray}\begin{array}{rcl}{P}_{t}(p,q) & = & \left|\displaystyle \frac{1}{2n}\,\left\langle q\right|\displaystyle \sum _{j=0}^{n-1}{{\rm{e}}}^{{\rm{i}}t(2\cos (2\pi j/n)+1)/3}{X}_{j}\right.\\ & & {\left.+\displaystyle \sum _{j=n}^{2n-1}{{\rm{e}}}^{{\rm{i}}t(2\cos (2\pi (j-n)/n)-1)/3}{Y}_{j}\left|p\right\rangle \right|}^{2}.\end{array}\end{eqnarray}$
For each 1 ≤ p, q ≤ 2n, we get Pt(p, q), and that gives us Pt matrix, a quantum-generated stochastic matrix. Since the evolution U(t) is unitary, we know that for large times, it will not converge to any specific distribution. Hence, we do probability averaging over an interval of time. It results in the time-averaged probability matrix ${\bar{P}}_{T}$, where each (p, q) entry is given by
$\begin{eqnarray}{\bar{P}}_{T}(p,q)=\displaystyle \frac{1}{T}{\int }_{0}^{T}{P}_{t}(p,q){\rm{d}}t.\end{eqnarray}$
The long-term behavior of this quantum walks ${\bar{P}}_{T}$ always fluctuates around its limiting distribution, which is stationary. We denote the limiting distribution by Π. Calculating the entries Π(p, q) of limiting distribution of a quantum walk on Γ is straightforward (refer to supplementary material D). When we take the limit of T → ∞ in equation (12 ), we find that PT→∞(p, q) is equal to
$\begin{eqnarray}{\rm{\Pi }}(p,q)=\left\{\begin{array}{ll}\displaystyle \frac{1}{2n}+\displaystyle \frac{n-1}{2{n}^{2}} & p=q\ \mathrm{or}\ q-p=n,\\ \displaystyle \frac{1}{2n}-\displaystyle \frac{1}{2{n}^{2}} & p\ne q\ \mathrm{and}\ q-p\ne n.\end{array}\right.\end{eqnarray}$
It is worth noting that the distribution Π described in equation (13 ) is non-uniform. To sample uniformly from Pt(subsequently ${\bar{P}}_{T}$ and Π), has to have uniform distribution. We show that the following theorem 1 holds for the Markov chain $P=\bar{A}$ and Π.
[14] If P is a symmetric irreducible Markov chain on N states, then each entry of Π bounded below by $1/{N}^{2};$ in particular, Π is ergodic. Moreover, each Pt is symmetric and, hence, has a uniform stationary distribution.
By inspection, it is clear that each entry of Π given in equation (13 ) is bounded below by 1/(2n)2 and Pt in equation (11 ) is symmetric since Pt(p, q) = Pt(q, p) (and so is ${\bar{P}}_{T}$). Hence, Pt has a uniform stationary distribution. We utilize the double-loop quantum algorithm to achieve uniform sampling, as outlined in supplementary material A. This algorithm was originally introduced by Richter in their work [14], and it exhibits a logarithmic dependence on 1/ε, where ε represents the desired accuracy or precision. This algorithm essentially runs a classical random walk for a duration of $T^{\prime} =O(\mathrm{log}(1/\epsilon ))$ using the quantum-generated stochastic matrix ${\bar{P}}_{T}$, (given in equation (12 )). We are interested in the minimum time τmix = T such that1 , $T^{\prime} =O(\mathrm{log}(1/\epsilon ))$, repetitions of this walk are adequate for achieving uniform sampling. The following section discusses the quantum mixing time bound based on the inverse sum of eigenvalue gaps to achieve equation (14 ). To do that, we state a conjecture for the subset of eigenvalues of $\bar{A}$.
$\begin{eqnarray}\parallel {\bar{P}}_{T}-{\rm{\Pi }}{\parallel }_{1}\leqslant \displaystyle \frac{1}{2e}.\end{eqnarray}$
Then, using proposition 5. Mixing time bound and conjecture
This section focuses on the quantum mixing time bound, utilizing the eigenvalue gaps of $\bar{A}$. We present the general quantum mixing time bound based on these eigenvalues. Subsequently, we provide specific bounds for our case and propose a conjecture for certain eigenvalue gaps. Finally, we establish the main result.
Given ${\bar{P}}_{T}$, the quantum mixing bound based on eigenvalues of $\bar{A}$ ([13]) on the LHS of equation (14 ) is given as follows:7 ) and (9 ), for 1 ≤ p ≤ 2n we have
$\begin{eqnarray}\parallel {\bar{P}}_{T}-{\rm{\Pi }}{\parallel }_{1}\leqslant \displaystyle \sum _{{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{2| \left\langle {x}_{j}\ \mathrm{or}\ {y}_{j}| p\right\rangle | .| \left\langle p| {x}_{k}\ \mathrm{or}\ {y}_{k}\right\rangle | }{T| {\lambda }_{j}-{\lambda }_{k}| },\end{eqnarray}$
where without loss of generality $\left|p\right\rangle $ is initial state, and $\{{\lambda }_{j},\left|{x}_{j}\right\rangle ,\left|{y}_{j}\right\rangle \}$ is the eigen spectrum of $\bar{A}$. From equations ( $\begin{eqnarray}| \left\langle {x}_{j}\ \mathrm{or}\ {y}_{j}| p\right\rangle | .| \left\langle p| {x}_{k}\ \mathrm{or}\ {y}_{k}\right\rangle | =\displaystyle \frac{1}{2n}.\end{eqnarray}$
Using equation (15 ) and the above calculations, the quantity we need to bound is the following:
$\begin{eqnarray}\displaystyle \frac{1}{{nT}}\displaystyle \sum _{{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }.\end{eqnarray}$
We initially partitioned the set of 2n eigenvalues into two subsets based on their indices: the first subset consists of eigenvalues given by equation (7 ) for 0 ≤ j ≤ n − 1, and the second subset comprises eigenvalues given by equation (9 ) for n ≤ j ≤ 2n − 1.
To further identify distinct eigenvalues within these subsets, we introduce index subsets C1 and C2 as follows: For $j\in {C}_{1}=[0,\tfrac{n-1}{2}]$, the eigenvalues satisfy $1\geqslant {\lambda }_{j}\gt -\tfrac{1}{3}$. For $j\in {C}_{2}=[n,\tfrac{3n-1}{2}]$, the eigenvalues satisfy $\tfrac{1}{3}\geqslant {\lambda }_{j}\gt -1$.
Additionally, we define index subsets ${C}_{1^{\prime} }=[\tfrac{n+1}{2},n-1]$ and ${C}_{2^{\prime} }=[\tfrac{3n+1}{2},2n-1]$. In ${C}_{1^{\prime} }$, the eigenvalues fall within the range $(1,-\tfrac{1}{3})$, while in ${C}_{2^{\prime} }$, the eigenvalues fall within the range $(\tfrac{1}{3},-1)$. Notably, ${C}_{1^{\prime} }$ and ${C}_{2^{\prime} }$ each contain n − 2 repeated eigenvalues from the C1 and C2 subsets, respectively, resulting in distinct sets of eigenvalues
$\begin{eqnarray}\begin{array}{rcl}\displaystyle \sum _{{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| } & = & 2\displaystyle \sum _{j\in {C}_{1}}\left(\displaystyle \sum _{k\in {C}_{2}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }+\displaystyle \sum _{k\in {C}_{1^{\prime} }}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }\right.\\ & & \left.+\displaystyle \sum _{k\in {C}_{2^{\prime} }}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }+\displaystyle \sum _{k\in {C}_{1},{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }\right)\\ & & +2\displaystyle \sum _{j\in {C}_{2}}\left(\displaystyle \sum _{k\in {C}_{1}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }+\displaystyle \sum _{k\in {C}_{1^{\prime} }}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }\right.\\ & & \left.+\displaystyle \sum _{k\in {C}_{2^{\prime} }}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }+\displaystyle \sum _{k\in {C}_{2},{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }\right).\end{array}\end{eqnarray}$
We simplify equation (18 ) by redefining the ranges of indices k and j to only involve the index sets C1 and C2 (by changing the variable k → k + n and j → n − j). We get the following equation.19 ). Let us tackle the first sum by simplifying it as follows:
$\begin{eqnarray}\begin{array}{rcl}\displaystyle \sum _{{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| } & = & 8\displaystyle \sum _{j\in {C}_{1}}\displaystyle \sum _{k\in {C}_{2}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }\\ & & +4\displaystyle \sum _{j\in {C}_{1}}\displaystyle \sum _{k\in {C}_{1},{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }\\ & & +4\displaystyle \sum _{j\in {C}_{2}}\displaystyle \sum _{k\in {C}_{2},{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }.\end{array}\end{eqnarray}$
Now, we calculate the bound on each sum from equation ( $\begin{eqnarray}\begin{array}{l}\displaystyle \sum _{j\in {C}_{1}}\displaystyle \sum _{k\in {C}_{2}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }\\ =\,3\displaystyle \sum _{j\in {C}_{1}}\displaystyle \sum _{k\in {C}_{2}}\displaystyle \frac{1}{| 2\cos (2\pi j/n)-2\cos (2\pi (k-n)/n)+2| }\\ =\,3\displaystyle \sum _{j\in {C}_{1}}\displaystyle \sum _{k\in {C}_{1}}\displaystyle \frac{1}{| 2\cos (2\pi j/n)-2\cos (2\pi k/n)+2| }\\ =\,\displaystyle \frac{3}{2}\displaystyle \sum _{j\in {C}_{1}}\displaystyle \sum _{k\in {C}_{1}}\displaystyle \frac{1}{| \cos (2\pi j/n)-\cos (2\pi k/n)+1| }.\end{array}\end{eqnarray}$
We divide equation (20 ) into four sums based on the range of j and k as follows:
$\begin{eqnarray}\begin{array}{l}\displaystyle \frac{3}{2}\displaystyle \sum _{j\in {C}_{1}}\displaystyle \sum _{k\in {C}_{1}}\displaystyle \frac{1}{| \cos (2\pi j/n)-\cos (2\pi k/n)+1| }\\ =\,{{Su}}_{1}+{{Su}}_{2}+{{Su}}_{3}+{{Su}}_{4},\end{array}\end{eqnarray}$
where $\begin{eqnarray}\begin{array}{rcl}{{Su}}_{1} & = & \displaystyle \frac{3}{2}\displaystyle \sum _{j=0}^{\unicode{x0230A}\tfrac{n}{4}\unicode{x0230B}}\displaystyle \sum _{k=0}^{\unicode{x0230A}\tfrac{n}{4}\unicode{x0230B}}\displaystyle \frac{1}{| \cos (2\pi j/n)-\cos (2\pi k/n)+1| },\\ {{Su}}_{2} & = & \displaystyle \frac{3}{2}\displaystyle \sum _{j=0}^{\unicode{x0230A}\tfrac{n}{4}\unicode{x0230B}}\displaystyle \sum _{k=\lceil \tfrac{n}{4}\rceil }^{(n-1)/2}\displaystyle \frac{1}{| \cos (2\pi j/n)-\cos (2\pi k/n)+1| },\\ {{Su}}_{3} & = & \displaystyle \frac{3}{2}\displaystyle \sum _{j=\lceil \tfrac{n}{4}\rceil }^{(n-1)/2}\displaystyle \sum _{k=0}^{\unicode{x0230A}\tfrac{n}{4}\unicode{x0230B}}\displaystyle \frac{1}{| \cos (2\pi j/n)-\cos (2\pi k/n)+1| },\\ {{Su}}_{4} & = & \displaystyle \frac{3}{2}\displaystyle \sum _{j=\lceil \tfrac{n}{4}\rceil }^{(n-1)/2}\displaystyle \sum _{k=\lceil \tfrac{n}{4}\rceil }^{(n-1)/2}\displaystyle \frac{1}{| \cos (2\pi j/n)-\cos (2\pi k/n)+1| }.\end{array}\end{eqnarray}$
We bound each Sul for 1 ≤ l ≤ 4 separately. The proofs of bounds on Su1, Su2, and Su4 are given in supplementary material B. The bounds are as follows: $\begin{eqnarray}\begin{array}{rcl}{{Su}}_{1} & \leqslant & \displaystyle \frac{3}{8}{n}^{2}\mathrm{log}(n),\\ {{Su}}_{2} & \leqslant & \displaystyle \frac{3}{32}{n}^{2},\\ {{Su}}_{4} & \leqslant & \displaystyle \frac{3}{32}{n}^{2}\mathrm{log}(n).\end{array}\end{eqnarray}$
We could not prove the upper bound on Su3 rigorously. Hence, we propose conjecture 1 . We give a numerical argument for the bound on Su3. The following conjecture is for n = 4p + 1; similarly, we do for n = 4p + 3 (refer to supplementary material C).
Consider $n=4p+1$ type, where $p\in {{\mathbb{Z}}}_{+}$, let $\alpha =\arccos \left(1-\sin \left(\tfrac{2\pi }{n}(b+\tfrac{3}{4})\right)\right)$, and $N(\alpha )=\lfloor \tfrac{n}{2\pi }\alpha \rfloor $ for $b\in [0,p-1]$ then
$\begin{eqnarray}\begin{array}{rcl}{{Su}}_{3} & \leqslant & f(n)=\displaystyle \sum _{b=0}^{p-1}{f}_{\alpha }(b)\\ & \leqslant & 100{n}^{2}{\left(\mathrm{log}(n)\right)}^{5},\end{array}\end{eqnarray}$
where $\begin{eqnarray*}\begin{array}{rcl}{f}_{\alpha }(b) & = & \displaystyle \frac{\pi }{2\alpha }\left[\displaystyle \frac{1}{\alpha }+\displaystyle \frac{1}{\alpha -\tfrac{2\pi }{n}N(\alpha )}+\displaystyle \frac{1}{\tfrac{2\pi }{n}(N(\alpha )+1)-\alpha }\right]\\ & & +\displaystyle \frac{n}{4\alpha }\mathrm{ln}\left[\displaystyle \frac{\tfrac{{\pi }^{2}}{2}}{\left(\alpha -\tfrac{2\pi }{n}N(\alpha ))(\tfrac{2\pi }{n}(N(\alpha )+1)-\alpha \right)}\right].\end{array}\end{eqnarray*}$
By conducting numerical simulations, we provide evidence supporting the validity of the conjecture (see supplementary material C). Consequently, we establish a bound on Su3 as $100{n}^{2}{(\mathrm{log}(n))}^{5}$.
Lastly, we analyze the other two sums from equation (19 ) where λj ≠ λk. We show that (refer to supplementary material B, case 5 for the proof)
$\begin{eqnarray}\displaystyle \sum _{j\in {C}_{1}}\displaystyle \sum _{k\in {C}_{1},{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }\leqslant {\left(\displaystyle \frac{8n}{\pi }\mathrm{log}(n)\right)}^{2}.\end{eqnarray}$
Similarly, we prove $\begin{eqnarray}\displaystyle \sum _{j\in {C}_{2}}\displaystyle \sum _{k\in {C}_{2},{\lambda }_{j}\ne {\lambda }_{k}}\displaystyle \frac{1}{| {\lambda }_{j}-{\lambda }_{k}| }\leqslant {\left(\displaystyle \frac{8n}{\pi }\mathrm{log}(n)\right)}^{2}.\end{eqnarray}$
Now, we state our main theorem and give the proof using the bounds and conjecture mentioned above.
For a time T of order $O{(n(\mathrm{log}(n))}^{5})$ and $T^{\prime} =O\left(\mathrm{log}(1/\epsilon )\right)$ iterations, the repeated continuous-time quantum walk on the graph ${\rm{\Gamma }}({D}_{2n},S)$ with $S=\{a,{a}^{-1},b\}$ converges to the uniform distribution when n is odd.
We combine the bounds given in equations (
$\begin{eqnarray*}\begin{array}{rcl}\parallel {\bar{P}}_{T}-{\rm{\Pi }}{\parallel }_{1} & \leqslant & \displaystyle \frac{1}{{nT}}\left(3{n}^{2}\mathrm{log}(n)+\displaystyle \frac{3}{4}{n}^{2}+\displaystyle \frac{3}{4}{n}^{2}\right.\\ & + & 800{n}^{2}{\left(\mathrm{log}(n)\right)}^{5}+\displaystyle \frac{256}{\pi }{\left(n\mathrm{log}(n)\right)}^{2}\\ & + & \left.\displaystyle \frac{256}{\pi }{\left(n\mathrm{log}(n)\right)}^{2}\right)\\ & \leqslant & \displaystyle \frac{1}{T}\left(3n\mathrm{log}(n)+2n+800n{\left(\mathrm{log}(n)\right)}^{5}\right.\\ & + & \left.163n{\left(\mathrm{log}(n)\right)}^{2}\right).\end{array}\end{eqnarray*}$
For $T=4800n{\left(\mathrm{log}(n)\right)}^{5}$ $\begin{eqnarray*}\begin{array}{rcl}\parallel {\bar{P}}_{T}-{\rm{\Pi }}{\parallel }_{1} & \leqslant & \left(\displaystyle \frac{1}{1600{\left(\mathrm{log}(n)\right)}^{4}}+\displaystyle \frac{1}{2400{\left(\mathrm{log}(n)\right)}^{5}}+\displaystyle \frac{1}{6}\right.\\ & + & \left.\displaystyle \frac{163}{4800{\left(\mathrm{log}(n)\right)}^{3}}\right)\\ & \leqslant & \left(\displaystyle \frac{1}{6}+\displaystyle \frac{1}{10{\left(\mathrm{log}(n)\right)}^{3}}\right).\end{array}\end{eqnarray*}$
For all $n\geqslant 100$, $\parallel {\bar{P}}_{T}-{\rm{\Pi }}{\parallel }_{1}\leqslant 1/2e$. According to theorem 6. Summary and outlook
In this study, we focus on the quantum mixing time of Cayley graphs associated with D2n. We present an upper bound for the mixing time of a continuous-time quantum walk with repeated measurements on D2n. Our results show that within $O{(n(\mathrm{log}(n))}^{5})$ time, the quantum walk approaches the limiting distribution. By performing $O(\mathrm{log}(1/\epsilon ))$ iterations, we achieve uniform sampling, surpassing the classical lower bound of ${\rm{\Omega }}({n}^{2}\mathrm{log}(1/2\epsilon ))$.
Additionally, we put forward a conjecture that relates to the sum of a subset of the reciprocals of eigenvalue gaps. This conjecture is supported by numerical evidence. Moreover, we highlight the quadratic advantage offered for the classical shuffling problem with the D2n group. This study raises the question of the potential advantages of quantum walks on finite groups in general.
Overall, our work expands the range of classical Markov chain Monte Carlo processes in which quantum walks with repeated measurements exhibit a speedup advantage. This study encourages further investigation into potential applications, especially sampling algorithms. Also, testing graph isomorphism is a hard problem in general, with applications in chemistry, network analysis, and computer vision. Quantum walks on Cayley graphs can construct canonical forms of graphs, which are unique representations that can be compared efficiently with a speed faster than that of a random walk.
