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:1108.0339 · Quantum Information and Computation

Perfect state transfer on quotient graphs

Rachel Elizabeth Bachman, Eric Fredette, Jessica Fuller, Michael P. Landry, Michael Opperman, Christino Tamon, Andrew Tollefson

Published Mar 1, 2012• 30 citations
arXivHTMLPDF

Abstract

We prove new results on perfect state transfer of quantum walks on quotient graphs. Since a graph G has perfect state transfer if and only if its quotient G/\pi, under any equitable partition \pi, has perfect state transfer, we exhibit graphs with perfect state transfer between two vertices but which lack automorphism swapping them. This answers a question of Godsil (Discrete Mathematics 312(1):129-147, 2011). We also show that the Cartesian product of quotient graphs \Box_{k} G_{k}/\pi_{k} is isomorphic to the quotient graph \Box_{k} G_{k}/\pi, for some equitable partition \pi. This provides an algebraic description of a construction due to Feder (Physical Review Letters 97, 180502, 2006) which is based on many-boson quantum walk.

DOI
10.26421/qic12.3-4-9

Related papers

Perfect state transfer on quotient graphs

BachmanRachel, FredetteEric, FullerJessica +4 more

We prove new results on perfect state transfer of quantum walks on quotient graphs. Since a graph G has perfect state transfer if and only if its quotient G/π, under any equitable partition π, has ...

Quantum Information and Computation•Mar 1, 2012•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

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

Perfect state transfer, integral circulants, and join of graphs

Ricardo Javier Angeles-Canul, R.M. Norton, Michael Opperman +3 more

We propose new families of graphs which exhibit quantum perfect state transfer. Our constructions are based on the join operator on graphs, its circulant generalizations, and the Cartesian product of graphs. We build upon the results of Ba\v{s}i\'{c} and Petkovi\'{c} ({\em Applied Mathematics Letters} {\bf 22}(10):1609-1615, 2009) and construct new integral circulants and regular graphs with perfect state transfer. More specifically, we show that the integral circulant $\textsc{ICG}_{n}(\{2,n/2^{b}\} \cup Q)$ has perfect state transfer, where $b \in \{1,2\}$, $n$ is a multiple of $16$ and $Q$ is a subset of the odd divisors of $n$. Using the standard join of graphs, we also show a family of double-cone graphs which are non-periodic but exhibit perfect state transfer. This class of graphs is constructed by simply taking the join of the empty two-vertex graph with a specific class of regular graphs. This answers a question posed by Godsil (arxiv.org math/08062074).

arXiv:0907.2148•Quantum Information and Computation•Mar 1, 2010•62 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•0 citations

PERFECT STATE TRANSFER, GRAPH PRODUCTS AND EQUITABLE PARTITIONS

Ge Yang, Benjamin Greenberg, Oscar Perez +1 more

We describe new constructions of graphs which exhibit perfect state transfer on continuous-time quantum walks. Our constructions are based on generalizations of the double cones and variants of the Cartesian graph products (which include the hypercube). We also describe a generalization of the path collapsing argument (which reduces questions about perfect state transfer to simpler weighted multigraphs) for graphs with equitable distance partitions.

arXiv:1009.1340•International Journal of Quantum Information•Apr 1, 2011•31 citations
We prove new results on perfect state transfer of quantum walks on quotient graphs. Since a graph G has perfect state transfer if and only if its quotient G/\pi, under any equitable partition \pi, has perfect state transfer, we exhibit graphs with perfect state transfer between two vertices but which lack automorphism swapping them. This answers a question of Godsil (Discrete Mathematics 312(1):129-147, 2011). We also show that the Cartesian product of quotient graphs \Box_{k} G_{k}/\pi_{k} is isomorphic to the quotient graph \Box_{k} G_{k}/\pi, for some equitable partition \pi. This provides an algebraic description of a construction due to Feder (Physical Review Letters 97, 180502, 2006) which is based on many-boson quantum walk.
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.
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.
We propose new families of graphs which exhibit quantum perfect state transfer. Our constructions are based on the join operator on graphs, its circulant generalizations, and the Cartesian product of graphs. We build upon the results of Ba\v{s}i\'{c} and Petkovi\'{c} ({\em Applied Mathematics Letters} {\bf 22}(10):1609-1615, 2009) and construct new integral circulants and regular graphs with perfect state transfer. More specifically, we show that the integral circulant $\textsc{ICG}_{n}(\{2,n/2^{b}\} \cup Q)$ has perfect state transfer, where b∈{1,2}b \in \{1,2\}b∈{1,2}, nnn is a multiple of 161616 and QQQ is a subset of the odd divisors of nnn. Using the standard join of graphs, we also show a family of double-cone graphs which are non-periodic but exhibit perfect state transfer. This class of graphs is constructed by simply taking the join of the empty two-vertex graph with a specific class of regular graphs. This answers a question posed by Godsil (arxiv.org math/08062074).
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.