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

Uniform mixing on integral abelian Cayley graph

Xiwang Cao

Published Nov 18, 2019• 2 citations
arXivHTMLPDF

Abstract

In the past few decades, quantum algorithms have become a popular research area of both mathematicians and engineers. Among them, uniform mixing provides a uniform probability distribution of quantum 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, a characterization of abelian Cayley graphs having uniform mixing is presented. Some concrete constructions of such graphs are provided. Specifically, for cubelike graphs, it is shown that the Cayley graph ${\rm Cay}(\mathbb{F}_2^{2k};S)$ has uniform mixing if the characteristic function of $S$ is bent. Moreover, a difference-balanced property of the eigenvalues of an integral abelian Cayley graph having uniform mixing is established. Some nonexistence results of uniform mixing on abelian Cayley graphs are presented also. Notably, for a linear abelian Cayley graph $Γ$ over $\mathbb{Z}_n^r$, it is proved that uniform mixing occurs on this graph only if $n=2,3,4$ which partially confirms a long-standing conjecture. Finally, with some restrictions on the connection set, we show that if a cyclic group $G$ whose order is divisible by an odd prime such that ${\rm Cay}(G,S)$ has uniform mixing at some time $t$ being a rational multiple of $π$, then the graph should be integral. An interesting reduction method on the circulant Cayley graphs having uniform mixing has been established. Using this method, we can answer some related open questions. For example, we can show that the only two cycles having uniform mixing are $C_3$ and $C_4$.

DOI
10.48550/arxiv.1911.07495

Related papers

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

Uniform Mixing on Cayley Graphs

Chris D. Godsil, Hanmeng Zhan

We provide new examples of Cayley graphs on which the quantum walks reach uniform mixing. Our first result is a complete characterization of all $2(d+2)$-regular Cayley graphs over $\mathbb{Z}_3^d$ that admit uniform mixing at time $2\pi/9$. Our second result shows that for every integer $k\ge 3$, we can construct Cayley graphs over $\mathbb{Z}_q^d$ that admit uniform mixing at time $2\pi/q^k$, where $q=3, 4$.We also find the first family of irregular graphs, the Cartesian powers of the star $K_{1,3}$, that admit uniform mixing.

arXiv:1504.00721•The Electronic Journal of Combinatorics•Jul 28, 2017•11 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

Perfect state transfer and Cayley presentations

Arnbjörg Soffía Árnadóttir, Krystal Guo

We study perfect state transfer on Cayley graphs from the point of view that state transfer is a property of a graph and not of a group. This paper is a bridge between the classical question about isomorphic Cayley graphs of non-isomorphic groups and quantum walks on graphs. We show that a Cayley graph of a group with an abelian subgroup of index two is a Cayley graph of an abelian group under any one of three hypotheses, two drawn from the theory of isomorphic Cayley graphs. A statement of the same kind holds for extraspecial groups: every Cayley graph of an extraspecial $p$-group of order $p^{2n+1}$ with a conjugacy-closed connection set is a Cayley graph of $Z_p^{2n+1}$. From these results we deduce that every explicit construction of perfect state transfer in the six papers we survey, on dihedral, dicyclic, generalized dihedral, $V_{8n}$ and extraspecial $2$-groups, is a non-abelian presentation of an abelian Cayley graph. Moreover, we show that a non-abelian group with an abelian subgroup of index two admits a connected Cayley graph with perfect state transfer if and only if its order is divisible by four. Genuinely non-abelian examples do exist. We prove that, for every odd prime power $q\ge 5$, the $SL(2,q)$ graph of Pantangi and Sin, which they showed to admit perfect state transfer, is a Cayley graph of no abelian group; to our knowledge, this is the first infinite family of Cayley graphs with perfect state transfer provably admitting no abelian Cayley presentation. We also construct an infinite family of Cayley graphs with peak state transfer and determine all regular subgroups of the automorphism group of every member. An appendix records a census of the connected vertex-transitive graphs with perfect state transfer on at most $30$ vertices.

math.COCross-listedarXiv:2608.20476•Aug 24, 2026•1 citation

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

Perfect State Transfer on Cayley Graphs over Dihedral Groups: The Non-Normal Case

Xiwang Cao, Bocong Chen, San Ling

Recently, perfect state transfer (PST for short) on graphs has attracted great attention due to their applications in quantum information processing and quantum computations. Many constructions and results have been established through various graphs. However, most of the graphs previously investigated are abelian Cayley graphs. Necessary and sufficient conditions for Cayley graphs over dihedral groups having perfect state transfer were studied recently. The key idea in that paper is the assumption of the normality of the connection set. In those cases, viewed as an element in a group algebra, the connection set is in the center of the group algebra, which makes the situations just like in the abelian case. In this paper, we study the non-normal case. In this case, the discussion becomes more complicated. Using the representations of the dihedral group $D_n$, we show that ${\rm Cay}(D_n,S)$ cannot have PST if $n$ is odd. For even integers $n$, it is proved that if ${\rm Cay}(D_n,S)$ has PST, then $S$ is normal.

The Electronic Journal of Combinatorics•May 29, 2020•19 citations
In the past few decades, quantum algorithms have become a popular research area of both mathematicians and engineers. Among them, uniform mixing provides a uniform probability distribution of quantum 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, a characterization of abelian Cayley graphs having uniform mixing is presented. Some concrete constructions of such graphs are provided. Specifically, for cubelike graphs, it is shown that the Cayley graph Cay(F22k;S){\rm Cay}(\mathbb{F}_2^{2k};S)Cay(F22k​;S) has uniform mixing if the characteristic function of SSS is bent. Moreover, a difference-balanced property of the eigenvalues of an integral abelian Cayley graph having uniform mixing is established. Some nonexistence results of uniform mixing on abelian Cayley graphs are presented also. Notably, for a linear abelian Cayley graph ΓΓΓ over Znr\mathbb{Z}_n^rZnr​, it is proved that uniform mixing occurs on this graph only if n=2,3,4n=2,3,4n=2,3,4 which partially confirms a long-standing conjecture. Finally, with some restrictions on the connection set, we show that if a cyclic group GGG whose order is divisible by an odd prime such that Cay(G,S){\rm Cay}(G,S)Cay(G,S) has uniform mixing at some time ttt being a rational multiple of πππ, then the graph should be integral. An interesting reduction method on the circulant Cayley graphs having uniform mixing has been established. Using this method, we can answer some related open questions. For example, we can show that the only two cycles having uniform mixing are C3C_3C3​ and C4C_4C4​.
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 provide new examples of Cayley graphs on which the quantum walks reach uniform mixing. Our first result is a complete characterization of all 2(d+2)2(d+2)2(d+2)-regular Cayley graphs over Z3d\mathbb{Z}_3^dZ3d​ that admit uniform mixing at time 2π/92\pi/92π/9. Our second result shows that for every integer k≥3k\ge 3k≥3, we can construct Cayley graphs over Zqd\mathbb{Z}_q^dZqd​ that admit uniform mixing at time 2π/qk2\pi/q^k2π/qk, where q=3,4q=3, 4q=3,4.We also find the first family of irregular graphs, the Cartesian powers of the star K1,3K_{1,3}K1,3​, that admit uniform mixing.
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 perfect state transfer on Cayley graphs from the point of view that state transfer is a property of a graph and not of a group. This paper is a bridge between the classical question about isomorphic Cayley graphs of non-isomorphic groups and quantum walks on graphs. We show that a Cayley graph of a group with an abelian subgroup of index two is a Cayley graph of an abelian group under any one of three hypotheses, two drawn from the theory of isomorphic Cayley graphs. A statement of the same kind holds for extraspecial groups: every Cayley graph of an extraspecial ppp-group of order p2n+1p^{2n+1}p2n+1 with a conjugacy-closed connection set is a Cayley graph of Zp2n+1Z_p^{2n+1}Zp2n+1​. From these results we deduce that every explicit construction of perfect state transfer in the six papers we survey, on dihedral, dicyclic, generalized dihedral, V8nV_{8n}V8n​ and extraspecial 222-groups, is a non-abelian presentation of an abelian Cayley graph. Moreover, we show that a non-abelian group with an abelian subgroup of index two admits a connected Cayley graph with perfect state transfer if and only if its order is divisible by four. Genuinely non-abelian examples do exist. We prove that, for every odd prime power q≥5q\ge 5q≥5, the SL(2,q)SL(2,q)SL(2,q) graph of Pantangi and Sin, which they showed to admit perfect state transfer, is a Cayley graph of no abelian group; to our knowledge, this is the first infinite family of Cayley graphs with perfect state transfer provably admitting no abelian Cayley presentation. We also construct an infinite family of Cayley graphs with peak state transfer and determine all regular subgroups of the automorphism group of every member. An appendix records a census of the connected vertex-transitive graphs with perfect state transfer on at most 303030 vertices.
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.
Recently, perfect state transfer (PST for short) on graphs has attracted great attention due to their applications in quantum information processing and quantum computations. Many constructions and results have been established through various graphs. However, most of the graphs previously investigated are abelian Cayley graphs. Necessary and sufficient conditions for Cayley graphs over dihedral groups having perfect state transfer were studied recently. The key idea in that paper is the assumption of the normality of the connection set. In those cases, viewed as an element in a group algebra, the connection set is in the center of the group algebra, which makes the situations just like in the abelian case. In this paper, we study the non-normal case. In this case, the discussion becomes more complicated. Using the representations of the dihedral group DnD_nDn​, we show that Cay(Dn,S){\rm Cay}(D_n,S)Cay(Dn​,S) cannot have PST if nnn is odd. For even integers nnn, it is proved that if Cay(Dn,S){\rm Cay}(D_n,S)Cay(Dn​,S) has PST, then SSS is normal.