Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2312.15693 · Communications in Theoretical Physics

Quantum walks advantage on the dihedral group for uniform sampling problem

Shyam Dhamapurkar, Yu–Hang Dang, Saniya Wagh, Xiu–Hao Deng

Published Sep 26, 2024• 0 citations
arXivHTMLPDF

Abstract

Abstract Random walk algorithms are crucial for sampling and approximation problems in statistical physics and theoretical computer science. The mixing property is necessary for Markov chains to approach stationary distributions and is facilitated by walks. Quantum walks show promise for faster mixing times than classical methods but lack universal proof, especially in finite group settings. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D 2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω ( n 2 log ( 1 / 2 ϵ ) ) , the continuous-time quantum walk mixing time on D 2n is of order O ( n ( log n ) 5 log ( 1 / ϵ ) ) , achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D 2n . This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.

DOI
10.1088/1572-9494/ad7fd5

Related papers

Quantum Walks Advantage on the Dihedral Group for Uniform Sampling Problem

Shyam Dhamapurkar, Yu–Hang Dang, Saniya Wagh +1 more

Random walk algorithms, including sampling and approximations, have played a significant role in statistical physics and theoretical computer science. Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω(n2log(1/2ε)), the continuous-time quantum walk mixing time on D2n is of order Ω($n(log n)$5log(1/ε)), achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D2n. This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Jul 1, 2024•1 citation

Almost uniform sampling via quantum walks

Peter C. Richter

Many classical randomized algorithms (e.g. approximation algorithms for #P-complete problems) utilize the following random walk algorithm for almost uniform sampling from a state space S of cardinality N : run a symmetric ergodic Markov chain P on S for long enough to obtain a random state from within total variation distance of the uniform distribution over S . The running time of this algorithm, the so-called mixing time of P , is O (δ −1 (log N +log −1 )), where δ is the spectral gap of P . We present a natural quantum version of this algorithm based on repeated measurements of the quantum walk U t = e −i Pt . We show that it samples almost uniformly from S with logarithmic dependence on −1 just as the classical walk P does; previously, no such quantum walk algorithm was known. We then outline a framework for analysing its running time and formulate two plausible conjectures which together would imply that it runs in time O (δ −1/2 log N log −1 ) when P is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.

arXiv:quant-ph/0606202•New Journal of Physics•Mar 22, 2007•54 citations

Discrete-time quantum walk search on the dihedral Cayley graph

Yong Qing Tiong, Kai Lin Ong, Ian K. T. Tan +1 more

Quantum walk is the quantum analogue of the classical random walk. Its application in search has demonstrated the capability to solve certain types of problems more efficiently than classical methods. The quantum walk search on the dihedral Cayley graph with 2N vertices is examined under several generating sets \(\mathcal {S}\). With the minimal generating set, the results show that the layout is an exceptional configuration. By adding a self-loop edge with some weight w > 0, which coincides with the lackadaisical quantum walk framework, and extra edges for each vertex, a nearly constant success probability of around 0.80 can be obtained using the proposed weight \(w^{\prime }=\frac{1}{N}\). The fitted number of steps is given by τ′ = 1.221N − 0.391. A comparison with the cycle graph is made, demonstrating improvement in the expected number of steps under the same vertex set size.

International Conference on Software and Computer Applications (ICSCA)•Feb 3, 2026•0 citations

Uniform mixing on abelian Cayley graphs

Xiwang Cao, Keqin Feng

In the past few decades, quantum algorithms have become a popular research area of both mathematicians and engineers. In 2003, Childs et al. found a graph in which the continuous-time quantum walk spreads exponentially faster than any classical algorithm for a certain black-box problem. Since then, there are extensive explorations on quantum walks on graphs. Among them, uniform mixing provides a uniform probability distribution of information over time which attracts a special attention. However, there are only a few known examples of graphs which admit uniform mixing. In this paper, we give a characterization of abelian Cayley graphs having uniform mixing. Some concrete constructions of such graphs are provided. Particularly, for cubelike graphs, it is shown that the Cayley graph ${\rm Cay}(\mathbb{F}_2^{2k};S)$ having uniform mixing if and only if $f$ is a bent function, where $f$ is the characteristic function of $S$.

arXiv:1911.07495•Nov 18, 2019•0 citations

Perfect state transfer in Grover walks on dihedral Cayley graphs

Koushik Bhakta, Bikash Bhattacharjya, Xiwang Cao

The paper investigates perfect state transfer (PST) in Grover walks on Cayley graphs over the dihedral group $D_n$. The Grover walk is a discrete-time quantum walk widely studied in quantum information processing. A Cayley graph $\operatorname{Cay}(Γ,S)$ is called normal if $S$ is the union of some conjugacy classes of the group $Γ$; otherwise, it is called non-normal. Most existing studies have been restricted to Cayley graphs over abelian groups. In contrast, we investigate both normal and non-normal cases for Cayley graphs over the non-abelian group $D_n$. By examining the parity of $n$ and the normality of the Cayley graph, we obtain a complete characterization of PST on $\operatorname{Cay}(D_n,S)$. In particular, we establish necessary and sufficient conditions for the occurrence of PST in all possible cases, and prove that PST does not occur for normal Cayley graphs when $n$ is odd. Furthermore, we construct several infinite families of normal and non-normal Cayley graphs $\operatorname{Cay}(D_n,S)$ that exhibit PST, illustrating the application of the main result. Our approach is based on the representation theory of the dihedral group.

math.COCross-listedarXiv:2605.02254•May 5, 2026•0 citations

Uniform Mixing of Quantum Walks and Association Schemes

Natalie Mullin

In recent years quantum algorithms have become a popular area of mathematical research. Farhi and Gutmann introduced the concept of a quantum walk in 1998. In this thesis we investigate mixing properties of continuous-time quantum walks from a mathematical perspective. We focus on the connections between mixing properties and association schemes. \n \nThere are three main goals of this thesis. Our primary goal is to develop the algebraic groundwork necessary to systematically study mixing properties of continuous-time quantum walks on regular graphs. Using these tools we achieve two additional goals: we construct new families of graphs that admit uniform mixing, and we prove that other families of graphs never admit uniform mixing. \n \nWe begin by introducing association schemes and continuous-time quantum walks. Within this framework we develop specific algebraic machinery to tackle the uniform mixing problem. Our main algebraic result shows that if a graph has an irrational eigenvalue, then its transition matrix has at least one transcendental coordinate at all nonzero times. \n \nNext we study algebraic varieties related to uniform mixing to determine information about the coordinates of the corresponding transition matrices. Combining this with our main algebraic result we prove that uniform mixing does not occur on even cycles or prime cycles. However, we show that the probability distribution of a quantum walk on a prime cycle gets arbitrarily close to uniform. \n \nFinally we consider uniform mixing on Cayley graphs of elementary abelian groups. We utilize graph quotients to connect the mixing properties of these graphs to Hamming graphs. This enables us to find new results about uniform mixing on Cayley graphs of certain elementary abelian groups.

•Sep 26, 2013•3 citations
Abstract Random walk algorithms are crucial for sampling and approximation problems in statistical physics and theoretical computer science. The mixing property is necessary for Markov chains to approach stationary distributions and is facilitated by walks. Quantum walks show promise for faster mixing times than classical methods but lack universal proof, especially in finite group settings. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D 2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω ( n 2 log ( 1 / 2 ϵ ) ) , the continuous-time quantum walk mixing time on D 2n is of order O ( n ( log n ) 5 log ( 1 / ϵ ) ) , achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D 2n . This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.
Random walk algorithms, including sampling and approximations, have played a significant role in statistical physics and theoretical computer science. Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω(n2log(1/2ε)), the continuous-time quantum walk mixing time on D2n is of order Ω($n(log n)$5log(1/ε)), achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D2n. This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.
Many classical randomized algorithms (e.g. approximation algorithms for #P-complete problems) utilize the following random walk algorithm for almost uniform sampling from a state space S of cardinality N : run a symmetric ergodic Markov chain P on S for long enough to obtain a random state from within total variation distance of the uniform distribution over S . The running time of this algorithm, the so-called mixing time of P , is O (δ −1 (log N +log −1 )), where δ is the spectral gap of P . We present a natural quantum version of this algorithm based on repeated measurements of the quantum walk U t = e −i Pt . We show that it samples almost uniformly from S with logarithmic dependence on −1 just as the classical walk P does; previously, no such quantum walk algorithm was known. We then outline a framework for analysing its running time and formulate two plausible conjectures which together would imply that it runs in time O (δ −1/2 log N log −1 ) when P is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.
Quantum walk is the quantum analogue of the classical random walk. Its application in search has demonstrated the capability to solve certain types of problems more efficiently than classical methods. The quantum walk search on the dihedral Cayley graph with 2N vertices is examined under several generating sets S\mathcal {S}S. With the minimal generating set, the results show that the layout is an exceptional configuration. By adding a self-loop edge with some weight w > 0, which coincides with the lackadaisical quantum walk framework, and extra edges for each vertex, a nearly constant success probability of around 0.80 can be obtained using the proposed weight w′=1Nw^{\prime }=\frac{1}{N}w′=N1​. The fitted number of steps is given by τ′ = 1.221N − 0.391. A comparison with the cycle graph is made, demonstrating improvement in the expected number of steps under the same vertex set size.
In the past few decades, quantum algorithms have become a popular research area of both mathematicians and engineers. In 2003, Childs et al. found a graph in which the continuous-time quantum walk spreads exponentially faster than any classical algorithm for a certain black-box problem. Since then, there are extensive explorations on quantum walks on graphs. Among them, uniform mixing provides a uniform probability distribution of information over time which attracts a special attention. However, there are only a few known examples of graphs which admit uniform mixing. In this paper, we give a characterization of abelian Cayley graphs having uniform mixing. Some concrete constructions of such graphs are provided. Particularly, for cubelike graphs, it is shown that the Cayley graph Cay(F22k;S){\rm Cay}(\mathbb{F}_2^{2k};S)Cay(F22k​;S) having uniform mixing if and only if fff is a bent function, where fff is the characteristic function of SSS.
The paper investigates perfect state transfer (PST) in Grover walks on Cayley graphs over the dihedral group DnD_nDn​. The Grover walk is a discrete-time quantum walk widely studied in quantum information processing. A Cayley graph Cay⁡(Γ,S)\operatorname{Cay}(Γ,S)Cay(Γ,S) is called normal if SSS is the union of some conjugacy classes of the group ΓΓΓ; otherwise, it is called non-normal. Most existing studies have been restricted to Cayley graphs over abelian groups. In contrast, we investigate both normal and non-normal cases for Cayley graphs over the non-abelian group DnD_nDn​. By examining the parity of nnn and the normality of the Cayley graph, we obtain a complete characterization of PST on Cay⁡(Dn,S)\operatorname{Cay}(D_n,S)Cay(Dn​,S). In particular, we establish necessary and sufficient conditions for the occurrence of PST in all possible cases, and prove that PST does not occur for normal Cayley graphs when nnn is odd. Furthermore, we construct several infinite families of normal and non-normal Cayley graphs Cay⁡(Dn,S)\operatorname{Cay}(D_n,S)Cay(Dn​,S) that exhibit PST, illustrating the application of the main result. Our approach is based on the representation theory of the dihedral group.
In recent years quantum algorithms have become a popular area of mathematical research. Farhi and Gutmann introduced the concept of a quantum walk in 1998. In this thesis we investigate mixing properties of continuous-time quantum walks from a mathematical perspective. We focus on the connections between mixing properties and association schemes. \n \nThere are three main goals of this thesis. Our primary goal is to develop the algebraic groundwork necessary to systematically study mixing properties of continuous-time quantum walks on regular graphs. Using these tools we achieve two additional goals: we construct new families of graphs that admit uniform mixing, and we prove that other families of graphs never admit uniform mixing. \n \nWe begin by introducing association schemes and continuous-time quantum walks. Within this framework we develop specific algebraic machinery to tackle the uniform mixing problem. Our main algebraic result shows that if a graph has an irrational eigenvalue, then its transition matrix has at least one transcendental coordinate at all nonzero times. \n \nNext we study algebraic varieties related to uniform mixing to determine information about the coordinates of the corresponding transition matrices. Combining this with our main algebraic result we prove that uniform mixing does not occur on even cycles or prime cycles. However, we show that the probability distribution of a quantum walk on a prime cycle gets arbitrarily close to uniform. \n \nFinally we consider uniform mixing on Cayley graphs of elementary abelian groups. We utilize graph quotients to connect the mixing properties of these graphs to Hamming graphs. This enables us to find new results about uniform mixing on Cayley graphs of certain elementary abelian groups.