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

Uniform Mixing of Quantum Walks and Association Schemes

Natalie Mullin

Published Sep 26, 2013• 3 citations
OpenAlex

Abstract

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.

Related papers

Uniform Mixing and Association Schemes

Chris D. Godsil, Natalie Mullin, Aidan Roy

We consider continuous-time quantum walks on distance-regular graphs. Using results about the existence of complex Hadamard matrices in association schemes, we determine which of these graphs have quantum walks that admit uniform mixing.First we apply a result due to Chan to show that the only strongly regular graphs that admit instantaneous uniform mixing are the Paley graph of order nine and certain graphs corresponding to regular symmetric Hadamard matrices with constant diagonal. Next we prove that if uniform mixing occurs on a bipartite graph $X$ with $n$ vertices, then $n$ is divisible by four. We also prove that if $X$ is bipartite and regular, then $n$ is the sum of two integer squares. Our work on bipartite graphs implies that uniform mixing does not occur on $C_{2m}$ for $m \geq 3$. Using a result of Haagerup, we show that uniform mixing does not occur on $C_p$ for any prime $p$ such that $p \geq 5$. In contrast to this result, we see that $\epsilon$-uniform mixing occurs on $C_p$ for all primes $p$.

arXiv:1301.5889•The Electronic Journal of Combinatorics•Aug 11, 2017•17 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

On mixing in continuous-time quantum walks on some circulant graphs

A. Ahmadi, Ryan Belk, Christino Tamon +1 more

Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that the continuous-time quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous exactly uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs of the symmetric group lack this mixing property as well.

Quantum Information and Computation•Nov 1, 2003•54 citations

Mixing in Continuous Quantum Walks on Graphs

Ahmadi, Amir, Ryan Belk, Christino Tamon +1 more

Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that a continuous quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs lack this mixing property as well.

arXiv:quant-ph/0209106•Sep 18, 2002•5 citations

Continuous-time Quantum Walks on Cayley Graphs of Extraspecial Groups

Peter Sin, Julien Sorci

We study continuous-time quantum walks on normal Cayley graphs of certain non-abelian groups called extraspecial groups. By applying general results for graphs in association schemes we determine the precise conditions for perfect state transfer and fractional revival. Using partial spreads, we construct Cayley graphs on extraspecial 2 -groups that admit these phenomena. We also show that there is no normal Cayley graph of an extraspecial group that admits instantaneous uniform mixing.

arXiv:2011.07566•Algebraic Combinatorics•Sep 8, 2022•8 citations

Uniform mixing and εεε-uniform mixing on cycles

Xiwang Cao, Cuiwen Zhu

We study continuous-time quantum walks on cycles. We prove two complementary results. Firstly, the cycle $C_9$ does not admit uniform mixing at any time. Using the similar idea and Dickson polynomials, we prove that $C_{15}$ does not admit uniform mixing at any time neither. Secondly, for every prime $p$, we show that the cycle $C_{p^2}$ admits $ε$-uniform mixing.

math.COCross-listedarXiv:2607.04207•Jul 7, 2026•0 citations
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.
We consider continuous-time quantum walks on distance-regular graphs. Using results about the existence of complex Hadamard matrices in association schemes, we determine which of these graphs have quantum walks that admit uniform mixing.First we apply a result due to Chan to show that the only strongly regular graphs that admit instantaneous uniform mixing are the Paley graph of order nine and certain graphs corresponding to regular symmetric Hadamard matrices with constant diagonal. Next we prove that if uniform mixing occurs on a bipartite graph XXX with nnn vertices, then nnn is divisible by four. We also prove that if XXX is bipartite and regular, then nnn is the sum of two integer squares. Our work on bipartite graphs implies that uniform mixing does not occur on C2mC_{2m}C2m​ for m≥3m \geq 3m≥3. Using a result of Haagerup, we show that uniform mixing does not occur on CpC_pCp​ for any prime ppp such that p≥5p \geq 5p≥5. In contrast to this result, we see that ϵ\epsilonϵ-uniform mixing occurs on CpC_pCp​ for all primes ppp.
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.
Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that the continuous-time quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous exactly uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs of the symmetric group lack this mixing property as well.
Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that a continuous quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs lack this mixing property as well.
We study continuous-time quantum walks on cycles. We prove two complementary results. Firstly, the cycle C9C_9C9​ does not admit uniform mixing at any time. Using the similar idea and Dickson polynomials, we prove that C15C_{15}C15​ does not admit uniform mixing at any time neither. Secondly, for every prime ppp, we show that the cycle Cp2C_{p^2}Cp2​ admits εεε-uniform mixing.