⚛️ quantum physics

The cycle C9 does not admit uniform mixing

This paper proves that the cycle graph $C_9$ does not admit uniform mixing at any time by employing algebraic geometry and Gröbner basis techniques to demonstrate the non-existence of cyclic 9-roots.

Original authors: Alison Gray, Pransu Patel, Isaiah Young

Published 2026-07-31

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Alison Gray, Pransu Patel, Isaiah Young

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a tiny, invisible particle playing a game of "hot potato" on a playground made of connected dots. In the world of quantum physics, this isn't just a game; it's a "quantum walk." Unlike a regular person walking down a street who picks one path at a time, a quantum particle is like a magical ghost that can walk down all the paths at once, spreading out like a ripple in a pond. Scientists love studying these walks because they might help build super-fast quantum computers that can solve problems regular computers can't touch.

One of the most exciting things a quantum walk can do is "uniform mixing." Picture the ghost spreading out until it is equally likely to be found at any single dot on the playground. If the ghost is perfectly mixed, it has an equal chance of being at every spot, like a perfectly shuffled deck of cards where every card has the same odds of being drawn. For some shapes, like triangles or squares, we know this perfect mixing happens. But for other shapes, it's a mystery. The question is: Can a specific shape called a "cycle" with nine dots (a nonagon) ever let this ghost spread out perfectly evenly?

This paper tackles that exact mystery. The authors, Alison Gray, Pransu Patel, and Isaiah Young, set out to solve the case of the nine-dot cycle, known as $C_9$ . They didn't just guess or run a simulation; they used a powerful mathematical toolkit called algebraic geometry and "Gröbner bases" (think of these as a super-organized filing system for complex equations) to prove a definitive answer. They discovered that the nine-dot cycle is a "no-go" zone for perfect mixing. No matter how long you wait, the quantum ghost on a nine-dot loop can never spread out to be perfectly equal at every spot.

To understand how they proved this, imagine the nine dots as a ring of dancers. For the dance to be "uniformly mixed," the rhythm and steps must align perfectly so that every dancer has the exact same probability of being in the spotlight at a specific moment. The authors looked at all the possible ways these dancers could move (mathematically represented as "cyclic 9-roots"). They found that there are thousands of isolated ways to dance and six big families of dance routines. They took these routines and tried to match them against the "perfect rhythm" required for uniform mixing.

Using their mathematical filing system, they showed that the only way to get the perfect rhythm would require the time to be an integer multiple of $\pi$ (like $\pi$ , $2\pi$ , $3\pi$ , etc.). However, further calculations revealed that for the mixing to actually work, this time would also have to be an irrational number involving complex trigonometric values that cannot be expressed as a simple multiple of $\pi$ . It's like trying to fit a square peg into a round hole, or trying to dance to a beat that requires you to take a step that doesn't exist in the rhythm. The math simply doesn't add up.

The authors proved that because the required time for perfect mixing leads to a mathematical contradiction, the cycle $C_9$ simply cannot admit uniform mixing at any time. They didn't just say it's unlikely; they ruled it out completely. This solves a puzzle that had been open for years, as $C_9$ was the first odd-numbered cycle that wasn't a prime number (like 3 or 5), making it a tricky middle ground that previous methods couldn't crack.

So, what's next? The authors point out that while they solved the nine-dot case, the next challenge is a cycle with 21 dots ( $C_{21}$ ). However, their current mathematical tools are too heavy and slow to handle such a large number of dancers. They conclude that while the nine-dot loop is a dead end for perfect mixing, the door remains open for other shapes, provided someone can invent a new, lighter set of mathematical tools to unlock the secrets of the larger cycles.

Technical Summary: The Cycle $C_9$ Does Not Admit Uniform Mixing

Problem Statement
The paper addresses the open problem of determining whether the cycle graph $C_9$ admits uniform mixing in the context of continuous-time quantum walks (CTQWs). Uniform mixing occurs at a specific time $t \in \mathbb{R}$ if every entry of the transition matrix $U(t) = e^{itA(G)}$ has a squared magnitude of $1/n$ , where $n$ is the number of vertices. While uniform mixing has been established for various graph families (including complete graphs, hypercubes, and cycles $C_3, C_4$ ) and ruled out for even cycles $C_n$ ( $n>4$ ) and odd prime cycles $C_n$ ( $n>3$ ), $C_9$ remained the first unresolved odd composite cycle. Previous work by Mullin [Mul13] identified $C_9$ as a remaining open case, noting that methods used for prime cycles do not apply to composite numbers.

Methodology
The authors employ algebraic geometry and Gröbner basis techniques to analyze the conditions required for uniform mixing on $C_9$ . The proof proceeds by contradiction, assuming uniform mixing occurs at some time $t = \tau$ . The methodology involves the following steps:

Cyclic 9-Roots Analysis: The study utilizes the classification of cyclic 9-roots established by Sabeti [Sab15], which consists of six two-dimensional prime ideal families ( $C_{9,i}^2$ for $i=1,\dots,6$ ) and 6,642 isolated roots. The authors focus on the six 2-dimensional families, as the isolated roots were previously ruled out by machinery in [Mul13].
Type-II Matrix Construction: The authors convert the solutions of the cyclic 9-roots into Type-II matrices (complex Hadamard matrices satisfying specific Schur product and orthogonality conditions). They define the first row of these matrices using the roots $x_1, \dots, x_9$ derived from the ideals.
Comparison with Transition Matrix: The constructed Type-II matrices are compared against the theoretical transition matrix $U(\tau)$ of $C_9$ , which is derived via Fourier diagonalization of the adjacency matrix $A(C_9)$ . The eigenvalues of $A(C_9)$ are known to be $\lambda_k = 2\cos(2\pi k/9)$ .
Algebraic Contradiction: By equating the eigenvalues of the Type-II matrix (derived from the cyclic roots) with the eigenvalues of the transition matrix (derived from the graph structure), the authors derive necessary algebraic conditions on the parameters of the roots and the time $\tau$ $τ$ .
- Symmetry constraints on the matrix entries force specific relationships between the parameters $\rho, \sigma$ , and the root variables $u, v$ .
- These relationships lead to an equation linking the time $\tau$ to the irrational number $\sqrt{3}\sin(\pi/9)$ .
- Specifically, the derivation shows that for uniform mixing to occur, $\tau$ must satisfy an equation where an integer multiple of $\pi$ equals an irrational multiple of $\pi$ .

Key Results
The paper proves Theorem 2.1: The cycle graph $C_9$ does not exhibit uniform mixing at any time $t \in \mathbb{R}$ .

The proof demonstrates that the assumption of uniform mixing leads to a contradiction regarding the nature of the time parameter $t$ :

The algebraic constraints imply that if uniform mixing occurs, the time $t$ must be an integer multiple of $\pi$ (specifically $\tau = n\pi$ for $n \in \mathbb{Z}$ ).
However, further calculation involving the eigenvalues for $k=1$ and $k=2$ yields a condition where $n$ must equal $\frac{2-3m}{3\sqrt{3}\sin(\pi/9)}$ for some integer $m$ .
The authors prove that $\sqrt{3}\sin(\pi/9)$ is irrational by showing it is a root of the polynomial $8x^3 - 18x + 9 = 0$ , which has no rational roots by the Rational Root Theorem.
Consequently, the required time $t$ would have to be irrational, contradicting the earlier deduction that $t$ must be an integer multiple of $\pi$ . Thus, no such time exists.

Significance and Scope
The paper resolves the specific open problem of uniform mixing for $C_9$ , confirming that this graph, like other odd prime cycles and even cycles (with $n>4$ ), does not admit uniform mixing. The authors note that their work was proven independently and concurrently with [CZ26], though their approach differs by utilizing an existing Gröbner basis and comparing Type-II matrices to Fourier-diagonalized matrices, rather than constructing a new basis to show the transition matrix is never flat.

The authors explicitly state that their current techniques, which rely on constructing and utilizing Gröbner bases of cyclic $n$ -roots, are computationally too heavy for larger values of $n$ . Therefore, they do not extend these methods to the next open case, $C_{21}$ , and acknowledge that different methods will be required for larger odd composite cycles. The paper does not propose new applications or experimental setups, focusing strictly on the theoretical resolution of the mixing property for $C_9$ .

Technical Summary: The Cycle C9C_9C9​ Does Not Admit Uniform Mixing

More like this

Technical Summary: The Cycle $C_9$ Does Not Admit Uniform Mixing