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:2607.28345

The cycle C9 does not admit uniform mixing

Alison Gray, Pransu Patel, Isaiah Young

math.COquant-phSubmitted Jul 30, 2026• Announced Jul 31, 2026• 0 citations
arXivHTMLPDF

Abstract

We study continuous-time quantum walks (CTQWs) on cycles. In particular, we prove that the cycle $C_9$ does not admit uniform mixing at any time via algebraic geometry and Gröbner basis techniques to rule out all cyclic 9-roots.

Related papers

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•1 citation

NON-UNIFORM MIXING OF QUANTUM WALK ON CYCLES

William Adamczak, Kevin Andrew, Leon Bergen +4 more

A classical lazy random walk on cycles is known to mix with the uniform distribution. In contrast, we show that a continuous-time quantum walk on cycles exhibits strong non-uniform mixing properties. First, we prove that the instantaneous distribution of a quantum walk on most even-length cycles is never uniform. More specifically, we prove that a quantum walk on a cycle Cnis not instantaneous uniform mixing, whenever n satisfies either: (a) n = 2u, for u ≥ 3; or (b) n = 2uq, for u ≥ 1 and q ≡ 3 (mod 4). Second, we prove that the average distribution of a quantum walk on any Abelian circulant graph is never uniform. As a corollary, the average distribution of a quantum walk on any standard circulant graph, such as the cycles, complete graphs, and even hypercubes, is never uniform. Nevertheless, we show that the average distribution of a quantum walk on the cycle Cnis O(1/n)-uniform.

arXiv:0708.2096•International Journal of Quantum Information•Dec 1, 2007•29 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•51 citations

Uniform Mixing in Chiral Quantum Walks

Luke Levine, Jessy Jacob Mesapam, Benjamin Mustico +3 more

This paper studies uniform mixing in continuous-time quantum walks. We show that for some unitary signing $σ$, the complete graph $K^σ_n$ has probabilistic uniform mixing. In contrast, Ahmadi \etal (2003) proved that no complete graph has uniform mixing except for $K_2$, $K_3$, and $K_4$. Our technique is based on a stopping rule for quantum walks which reduces global to local uniform mixing. As a corollary, we found an orientation of $H(n,4)$ that mixes to uniform faster than any other Hamming graphs, which improves a result of Godsil and Zhan (2019). We also show that there are infinite families of oriented circulants with average uniform mixing. This is a chiral violation of a No-Go theorem due to Godsil (2013) which states that no graph has average uniform mixing except for $K_2$.

math.COCross-listedarXiv:2605.04414•May 7, 2026•0 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•17 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
We study continuous-time quantum walks (CTQWs) on cycles. In particular, we prove that the cycle C9C_9C9​ does not admit uniform mixing at any time via algebraic geometry and Gröbner basis techniques to rule out all cyclic 9-roots.
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.
A classical lazy random walk on cycles is known to mix with the uniform distribution. In contrast, we show that a continuous-time quantum walk on cycles exhibits strong non-uniform mixing properties. First, we prove that the instantaneous distribution of a quantum walk on most even-length cycles is never uniform. More specifically, we prove that a quantum walk on a cycle Cnis not instantaneous uniform mixing, whenever n satisfies either: (a) n = 2u, for u ≥ 3; or (b) n = 2uq, for u ≥ 1 and q ≡ 3 (mod 4). Second, we prove that the average distribution of a quantum walk on any Abelian circulant graph is never uniform. As a corollary, the average distribution of a quantum walk on any standard circulant graph, such as the cycles, complete graphs, and even hypercubes, is never uniform. Nevertheless, we show that the average distribution of a quantum walk on the cycle Cnis O(1/n)-uniform.
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.
This paper studies uniform mixing in continuous-time quantum walks. We show that for some unitary signing σσσ, the complete graph KnσK^σ_nKnσ​ has probabilistic uniform mixing. In contrast, Ahmadi \etal (2003) proved that no complete graph has uniform mixing except for K2K_2K2​, K3K_3K3​, and K4K_4K4​. Our technique is based on a stopping rule for quantum walks which reduces global to local uniform mixing. As a corollary, we found an orientation of H(n,4)H(n,4)H(n,4) that mixes to uniform faster than any other Hamming graphs, which improves a result of Godsil and Zhan (2019). We also show that there are infinite families of oriented circulants with average uniform mixing. This is a chiral violation of a No-Go theorem due to Godsil (2013) which states that no graph has average uniform mixing except for K2K_2K2​.
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.
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.