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

Perfect State Transfer on Oriented Circulant Graphs: A Complete Classification

Xingkun Song

quant-phmath.COSubmitted Aug 12, 2026• Announced Aug 13, 2026• 0 citations
arXivHTMLPDF

Abstract

The continuous-time quantum walk on an oriented circulant graph is determined by the Fourier eigenvalues of its Hermitian adjacency matrix. We classify perfect state transfer (PST) between distinct vertices in every nonempty oriented circulant graph. We show that each such graph is described by an odd primitive quadratic Dirichlet character of conductor $Δ$, a set of gcd-classes, and a choice between the two orientations of each selected class. For a graph of order $n$, we derive an explicit formula for every Fourier eigenvalue without assuming that $n/Δ$ is coprime to $Δ$. We prove that PST occurs only for $Δ\in\{3,4,8\}$ and give necessary and sufficient conditions on the connection set for each conductor. Equivalently, the square-free radicands of oriented circulant graphs with PST are exactly $1$, $2$, and $3$. More generally, when $λ_j=\sqrt{D}η_j$ with $η_j\in\mathbb{Z}$, congruences satisfied by the integers $η_j$ determine all PST pairs and times, the minimum period, and the largest vertex sets supporting multiple state transfer (MST). In this class, pretty good state transfer is equivalent to PST. We also determine the connected orders and enumerate the resulting graphs.

Comments
31 pages

Related papers

State Transfer in Complex Quantum Walks

Antonio Acuaviva, Ada Chan, Eldridge, Summer +5 more

Given a graph with Hermitian adjacency matrix $H$, perfect state transfer occurs from vertex $a$ to vertex $b$ if the $(b,a)$-entry of the unitary matrix $\exp(-iHt)$ has unit magnitude for some time $t$. This phenomenon is relevant for information transmission in quantum spin networks and is known to be monogamous under real symmetric matrices. We prove the following results: 1. For oriented graphs (whose nonzero weights are $\pm i$), the oriented $3$-cycle and the oriented edge are the only graphs where perfect state transfer occurs between every pair of vertices. This settles a conjecture of Cameron et al. On the other hand, we construct an infinite family of oriented graphs with perfect state transfer between any pair of vertices on a subset of size four. 2. There are infinite families of Hermitian graphs with one-way perfect state transfer, where perfect state transfer occurs without periodicity. In contrast, perfect state transfer implies periodicity whenever the adjacency matrix has algebraic entries (as shown by Godsil). 3. There are infinite families with non-monogamous pretty good state transfer in rooted graph products. In particular, we generalize known results on double stars (due to Fan and Godsil) and on paths with loops (due to Kempton, Lippner and Yau). The latter extends the experimental observation of quantum transport (made by Zimborás et al.) and shows non-monogamous pretty good state transfer can occur amongst distant vertices.

arXiv:2301.01473•Jan 4, 2023•0 citations

Characterization of circulant graphs having perfect state transfer

Milan Bašić

In this paper we answer the question of when circulant quantum spin networks with nearest-neighbor couplings can give perfect state transfer. The network is described by a circulant graph $G$, which is characterized by its circulant adjacency matrix $A$. Formally, we say that there exists a {\it perfect state transfer} (PST) between vertices $a,b\in V(G)$ if $|F(τ)_{ab}|=1$, for some positive real number $τ$, where $F(t)=\exp(ıAt)$. Saxena, Severini and Shparlinski ({\it International Journal of Quantum Information} 5 (2007), 417--430) proved that $|F(τ)_{aa}|=1$ for some $a\in V(G)$ and $τ\in \R^+$ if and only if all eigenvalues of $G$ are integer (that is, the graph is integral). The integral circulant graph $\ICG_n (D)$ has the vertex set $Z_n = \{0, 1, 2, ..., n - 1\}$ and vertices $a$ and $b$ are adjacent if $\gcd(a-b,n)\in D$, where $D \subseteq \{d : d \mid n,\ 1\leq d

arXiv:1104.1825•Apr 11, 2011•12 citations

Perfect state transfer on mixed graphs: complete classes and transfer times

Xingkun Song

For perfect state transfer (PST) on unweighted mixed graphs, we classify the normalized transfer times of complete PST classes. A finite set $Λ\subset\mathbb R/\mathbb Z$ containing zero occurs at a nonstationary periodic vertex if and only if $\cos(2π(x-y))\in\mathbb Q$ for all $x,y\inΛ$. Every admissible set has a connected oriented realization. We also classify the possible return phases of oriented realizations at the minimum vertex period. Transfers at rational multiples of the common minimum vertex period partition a complete class into sets of size at most six, or at most three in an oriented graph with return phase $-1$; both bounds are sharp. We construct complete classes of every finite size, including classes in which all transfers between distinct vertices occur at irrational multiples of the period and no switching automorphism maps a class vertex to a distinct class vertex. We also characterize simultaneous realization in connected oriented graphs with prescribed relative minimum vertex periods and return phases. The proof combines an imaginary quadratic field restriction with an unweighted construction that selects the complete target set.

math.COCross-listedarXiv:2610.08333•Oct 7, 2026•0 citations

Perfect State Transfer on Quotient Graphs in Shunt Decomposition-Based Quantum Walks

Banita Katuwal, Srinath M S, Y Lakshmi Naidu +1 more

This paper investigates perfect state transfer (PST) in discrete-time quantum walks constructed via the shunt decomposition method. The walks are defined on a graph $G$ and its associated quotient graph $G/π$, induced by an equitable partition $π$. Through the shunt decomposition of $G$, we derive an explicit relation between the shift operator of the parent graph $G$ and that of its quotient graph $G/π$. We construct a reflection operator based on the characteristic matrix, which establishes a connection between the transition operator of the parent graph and that of its lower-dimensional quotient graph. We then prove that PST occurs on $G$ if and only if it occurs on $G/π$. Furthermore, we express the unitary evolution operator of the quotient graph in terms of Chebyshev polynomials of the first kind, from which we derive explicit criteria for PST. As an application, we establish PST on the cycle graph $C_{n}$ at time $k = n/2$, and lift the result to the parent graph $C_{2n}$ via the equitable partition $π$. We further show that if an equitable partition $π$ of $G$ induces a quotient isomorphic to $K_n^{\circlearrowleft}$, the complete digraph on $n$ vertices with a loop at every vertex, then PST occurs at step $k = n$, and the walk is periodic at $k = 2n$. This framework is applied to two families of graphs, which are the complete bipartite digraph $K_{n,n}^{\rightleftharpoons}$ and the circulant graph $\operatorname{Circ}(2n, S)$, where $S$ consists of all odd residues modulo $2n$ and $n = 2^s$ for some $s \geq 1$, establishing PST in their respective line digraphs. Collectively, these results also answer the question posed by Godsil and Zhan concerning which shunt decompositions or embeddings of a graph admit PST.

math.COCross-listedarXiv:2606.24440•Jun 24, 2026•0 citations

Quantum Walks on Oriented Graphs

Sabrina Lato

This thesis extends results about periodicity and perfect state transfer \nto oriented graphs. We prove that if a vertex a is periodic, then elements of \nthe eigenvalue support lie in Z √∆ for some squarefree negative integer \n∆. We find an infinite family of orientations of the complete graph that are \nperiodic. We find an example of a graph with both perfect state transfer \nand periodicity that is not periodic at an integer multiple of the period, and \nwe prove and use Gelfond-Schneider Theorem to show that every oriented \ngraph with perfect state transfer between two vertices will have both vertices \nperiodic. We find a complete characterization of when perfect state transfer \ncan occur in oriented graphs, and find a new example of a graph where one \nvertex has perfect state transfer to multiple other vertices.

•Jan 11, 2019•3 citations

A complete classification of perfect state transfer in Grover walks on abelian Cayley graphs

Koushik Bhakta, Bikash Bhattacharjya

We completely classify connected Cayley graphs over finite abelian groups that exhibit perfect state transfer in Grover walks. First, we show that a Cayley graph over any finite group exhibiting perfect state transfer has valency $1$, $2$, or $4$. For valency $4$, we prove that an abelian Cayley graph $\operatorname{Cay}(Γ,S)$ exhibits perfect state transfer if and only if $S=\{a,-a,a+h,-a+h\}$, where $h$ has order $2$, and $4\nmid |Γ|/2$. Combining this characterization with the valency-one and valency-two cases, we explicitly determine all pairs $(Γ,S)$ for which $\operatorname{Cay}(Γ,S)$ exhibits perfect state transfer. Our results extend the classification of circulant graphs of valency at most four obtained by Kubota and Yoshino [Circulant graphs with valency up to 4 that admit perfect state transfer in Grover walks, \emph{J. Comb. Theory Ser. A.}, 216 (2025) 106064] to Cayley graphs over arbitrary finite abelian groups and to all valencies.

math.COCross-listedarXiv:2610.21946•Oct 16, 2026•0 citations
The continuous-time quantum walk on an oriented circulant graph is determined by the Fourier eigenvalues of its Hermitian adjacency matrix. We classify perfect state transfer (PST) between distinct vertices in every nonempty oriented circulant graph. We show that each such graph is described by an odd primitive quadratic Dirichlet character of conductor ΔΔΔ, a set of gcd-classes, and a choice between the two orientations of each selected class. For a graph of order nnn, we derive an explicit formula for every Fourier eigenvalue without assuming that n/Δn/Δn/Δ is coprime to ΔΔΔ. We prove that PST occurs only for Δ∈{3,4,8}Δ\in\{3,4,8\}Δ∈{3,4,8} and give necessary and sufficient conditions on the connection set for each conductor. Equivalently, the square-free radicands of oriented circulant graphs with PST are exactly 111, 222, and 333. More generally, when λj=Dηjλ_j=\sqrt{D}η_jλj​=D​ηj​ with ηj∈Zη_j\in\mathbb{Z}ηj​∈Z, congruences satisfied by the integers ηjη_jηj​ determine all PST pairs and times, the minimum period, and the largest vertex sets supporting multiple state transfer (MST). In this class, pretty good state transfer is equivalent to PST. We also determine the connected orders and enumerate the resulting graphs.
Given a graph with Hermitian adjacency matrix HHH, perfect state transfer occurs from vertex aaa to vertex bbb if the (b,a)(b,a)(b,a)-entry of the unitary matrix exp⁡(−iHt)\exp(-iHt)exp(−iHt) has unit magnitude for some time ttt. This phenomenon is relevant for information transmission in quantum spin networks and is known to be monogamous under real symmetric matrices. We prove the following results: 1. For oriented graphs (whose nonzero weights are ±i\pm i±i), the oriented 333-cycle and the oriented edge are the only graphs where perfect state transfer occurs between every pair of vertices. This settles a conjecture of Cameron et al. On the other hand, we construct an infinite family of oriented graphs with perfect state transfer between any pair of vertices on a subset of size four. 2. There are infinite families of Hermitian graphs with one-way perfect state transfer, where perfect state transfer occurs without periodicity. In contrast, perfect state transfer implies periodicity whenever the adjacency matrix has algebraic entries (as shown by Godsil). 3. There are infinite families with non-monogamous pretty good state transfer in rooted graph products. In particular, we generalize known results on double stars (due to Fan and Godsil) and on paths with loops (due to Kempton, Lippner and Yau). The latter extends the experimental observation of quantum transport (made by Zimborás et al.) and shows non-monogamous pretty good state transfer can occur amongst distant vertices.
In this paper we answer the question of when circulant quantum spin networks with nearest-neighbor couplings can give perfect state transfer. The network is described by a circulant graph GGG, which is characterized by its circulant adjacency matrix AAA. Formally, we say that there exists a {\it perfect state transfer} (PST) between vertices a,b∈V(G)a,b\in V(G)a,b∈V(G) if ∣F(τ)ab∣=1|F(τ)_{ab}|=1∣F(τ)ab​∣=1, for some positive real number τττ, where F(t)=exp⁡(ıAt)F(t)=\exp(ıAt)F(t)=exp(ıAt). Saxena, Severini and Shparlinski ({\it International Journal of Quantum Information} 5 (2007), 417--430) proved that ∣F(τ)aa∣=1|F(τ)_{aa}|=1∣F(τ)aa​∣=1 for some a∈V(G)a\in V(G)a∈V(G) and τ∈R+τ\in \R^+τ∈R+ if and only if all eigenvalues of GGG are integer (that is, the graph is integral). The integral circulant graph $\ICG_n (D)$ has the vertex set Zn={0,1,2,...,n−1}Z_n = \{0, 1, 2, ..., n - 1\}Zn​={0,1,2,...,n−1} and vertices aaa and bbb are adjacent if gcd⁡(a−b,n)∈D\gcd(a-b,n)\in Dgcd(a−b,n)∈D, where $D \subseteq \{d : d \mid n,\ 1\leq d
For perfect state transfer (PST) on unweighted mixed graphs, we classify the normalized transfer times of complete PST classes. A finite set Λ⊂R/ZΛ\subset\mathbb R/\mathbb ZΛ⊂R/Z containing zero occurs at a nonstationary periodic vertex if and only if cos⁡(2π(x−y))∈Q\cos(2π(x-y))\in\mathbb Qcos(2π(x−y))∈Q for all x,y∈Λx,y\inΛx,y∈Λ. Every admissible set has a connected oriented realization. We also classify the possible return phases of oriented realizations at the minimum vertex period. Transfers at rational multiples of the common minimum vertex period partition a complete class into sets of size at most six, or at most three in an oriented graph with return phase −1-1−1; both bounds are sharp. We construct complete classes of every finite size, including classes in which all transfers between distinct vertices occur at irrational multiples of the period and no switching automorphism maps a class vertex to a distinct class vertex. We also characterize simultaneous realization in connected oriented graphs with prescribed relative minimum vertex periods and return phases. The proof combines an imaginary quadratic field restriction with an unweighted construction that selects the complete target set.
This paper investigates perfect state transfer (PST) in discrete-time quantum walks constructed via the shunt decomposition method. The walks are defined on a graph GGG and its associated quotient graph G/πG/πG/π, induced by an equitable partition πππ. Through the shunt decomposition of GGG, we derive an explicit relation between the shift operator of the parent graph GGG and that of its quotient graph G/πG/πG/π. We construct a reflection operator based on the characteristic matrix, which establishes a connection between the transition operator of the parent graph and that of its lower-dimensional quotient graph. We then prove that PST occurs on GGG if and only if it occurs on G/πG/πG/π. Furthermore, we express the unitary evolution operator of the quotient graph in terms of Chebyshev polynomials of the first kind, from which we derive explicit criteria for PST. As an application, we establish PST on the cycle graph CnC_{n}Cn​ at time k=n/2k = n/2k=n/2, and lift the result to the parent graph C2nC_{2n}C2n​ via the equitable partition πππ. We further show that if an equitable partition πππ of GGG induces a quotient isomorphic to Kn↺K_n^{\circlearrowleft}Kn↺​, the complete digraph on nnn vertices with a loop at every vertex, then PST occurs at step k=nk = nk=n, and the walk is periodic at k=2nk = 2nk=2n. This framework is applied to two families of graphs, which are the complete bipartite digraph Kn,n⇌K_{n,n}^{\rightleftharpoons}Kn,n⇌​ and the circulant graph Circ⁡(2n,S)\operatorname{Circ}(2n, S)Circ(2n,S), where SSS consists of all odd residues modulo 2n2n2n and n=2sn = 2^sn=2s for some s≥1s \geq 1s≥1, establishing PST in their respective line digraphs. Collectively, these results also answer the question posed by Godsil and Zhan concerning which shunt decompositions or embeddings of a graph admit PST.
This thesis extends results about periodicity and perfect state transfer \nto oriented graphs. We prove that if a vertex a is periodic, then elements of \nthe eigenvalue support lie in Z √∆ for some squarefree negative integer \n∆. We find an infinite family of orientations of the complete graph that are \nperiodic. We find an example of a graph with both perfect state transfer \nand periodicity that is not periodic at an integer multiple of the period, and \nwe prove and use Gelfond-Schneider Theorem to show that every oriented \ngraph with perfect state transfer between two vertices will have both vertices \nperiodic. We find a complete characterization of when perfect state transfer \ncan occur in oriented graphs, and find a new example of a graph where one \nvertex has perfect state transfer to multiple other vertices.
We completely classify connected Cayley graphs over finite abelian groups that exhibit perfect state transfer in Grover walks. First, we show that a Cayley graph over any finite group exhibiting perfect state transfer has valency 111, 222, or 444. For valency 444, we prove that an abelian Cayley graph Cay⁡(Γ,S)\operatorname{Cay}(Γ,S)Cay(Γ,S) exhibits perfect state transfer if and only if S={a,−a,a+h,−a+h}S=\{a,-a,a+h,-a+h\}S={a,−a,a+h,−a+h}, where hhh has order 222, and 4∤∣Γ∣/24\nmid |Γ|/24∤∣Γ∣/2. Combining this characterization with the valency-one and valency-two cases, we explicitly determine all pairs (Γ,S)(Γ,S)(Γ,S) for which Cay⁡(Γ,S)\operatorname{Cay}(Γ,S)Cay(Γ,S) exhibits perfect state transfer. Our results extend the classification of circulant graphs of valency at most four obtained by Kubota and Yoshino [Circulant graphs with valency up to 4 that admit perfect state transfer in Grover walks, \emph{J. Comb. Theory Ser. A.}, 216 (2025) 106064] to Cayley graphs over arbitrary finite abelian groups and to all valencies.