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

Quantum walks on finite and bounded infinite graphs

Chris D. Godsil, Steve Kirkland, Mohapatra, Sarojini, Monterde, Hermie, Hiranmoy Pal

Published Oct 6, 2025• 0 citations
arXivHTMLPDF

Abstract

A weighted graph $G$ with countable vertex set is bounded if there is an upper bound on the maximum of the sum of absolute values of all edge weights incident to a vertex in $G$. In this paper, we prove a fundamental result on equitable partitions of bounded weighted graphs with twin subgraphs and use this fact to construct finite and bounded infinite graphs with pair and plus state transfer with the adjacency matrix as a Hamiltonian. We show that for each $k \ge 3$, (i) there are infinitely many connected unweighted graphs with maximum degree $k$ admitting pair state transfer at $τ\in\{\fracπ{\sqrt{2}},\fracπ{2}\}$, and (ii) there are infinitely many signed graphs with exactly one negative edge weight and whose underlying unweighted graphs have maximum degree $k$ admitting plus state transfer at $τ\in\{\fracπ{\sqrt{2}},\fracπ{2}\}$. Parallel results are proven for perfect state transfer between a plus state and a pair state, and for the existence of sedentary pair and plus states. We further prove that almost all connected unweighted finite planar graphs admit pair state transfer at $τ\in\{\fracπ{\sqrt{2}},\fracπ{2}\}$, and almost all connected unweighted finite planar graphs can be assigned a single negative edge weight resulting in plus state transfer, or perfect state transfer between a plus state and a pair state, at $τ\in\{\fracπ{\sqrt{2}},\fracπ{2}\}$. Analogous results are shown to hold for unweighted finite trees. Using blow-up graphs, Cayley graphs and graphs with tails, we construct new infinite families of (finite and infinite) unweighted graphs and signed graphs admitting pair or plus state transfer.

DOI
10.48550/arxiv.2510.05306

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

Perfect state transfer from a pair state to a plus state in unweighted graphs

Shunpei Shimizu

Draft note (v0.1.3). We give a connected simple (unweighted) graph on 12 vertices in which the continuous-time quantum walk exp(itA) has perfect state transfer from the pair state e_1 - e_11 to the plus state e_0 + e_2 at time pi/sqrt(2), with a proof that can be checked by hand, and an infinite family obtained by Cartesian products with powers of the path P3. This concerns the question of Monterde and Pal (arXiv:2505.07982v5, Section 10). The product step is a known construction (Godsil, Kirkland and Monterde, SIAM J. Matrix Anal. Appl. 46 (2025) 2093-2115, Corollary 48 and Example 50 in arXiv:2502.08103v4; see also Monterde and Pal, Section 9, and Kirkland, Monterde and Plosker, arXiv:2609.10713, equation (4.1)); we did not find an example of perfect state transfer from a pair state to a plus state in these papers, and no claim of priority is made. Exhaustive computer searches, with numerical tests at stated tolerances, found no example on at most 10 vertices (adjacency and signless Laplacian matrices); these are finite computations, not proofs. Code and outputs are included. Versions 0.1.2 and 0.1.3 correct attribution and citations only. This is a personal hobby/independent research record in which AI was used for exploration, drafting proof candidates, checking and writing; it has not been peer-reviewed by human experts.

•Oct 20, 2026•0 citations

Quantum pure state transfer

Hermie Monterde

Quantum spin systems carry information in the form of quantum states, and the propagation of these quantum states is described by a quantum walk. In order to construct an operational quantum computer, the task of reliably transmitting quantum states from one part of a quantum computer to another must be accomplished. Quantum walks are known to be powerful tools in achieving this task. Pure states are quantum states represented by unit complex vectors. In this thesis, we use algebraic and combinatorial techniques to develop the theory of perfect state transfer on pure states in quantum walks, with emphasis on the adjacency and Laplacian matrices as Hamiltonians of a graph representing a spin network. We prove basic results about eigenvalue supports, periodicity, and strong cospectrality on pure states. We investigate a special type of strong cospectrality called m-strong cospectrality, and show that m-strongly cospectral pure states admit desirable quantum state transfer properties. Several characterisations of perfect state transfer are also given, one for general pure states, one for m-strongly pure states, and another one for real pure states. These characterisations give rise to algebraic and analytic properties of pure states admitting perfect state transfer. Moreover, we determine all complete graphs, complete bipartite graphs, cycles, and paths that admit perfect state transfer between m-strongly pure states. Constructions of infinite families of graphs admitting perfect state transfer are also given. We also characterise perfect state transfer between vertex states in joins and blowup graphs. We determine when the join operation preserves or induces perfect state transfer in the resulting graph. We also use blow-up graphs to construct new families of regular graphs with perfect state transfer. We use these two graph operations to demonstrate that graphs with perfect state transfer can be constructed from graphs that do not exhibit such a property. Finally, we investigate perfect state transfer on s-pair states – pure states that represent entanglement between two vertices. We establish combinatorial and spectral properties of s-pair states with perfect state transfer, and characterise its existence in complete graphs, complete bipartite graphs, paths and distance-regular graphs. Further, we construct infinite families of graphs with s-pair state transfer.

•Aug 14, 2025•0 citations

Adjacency peak state transfer on trees: an elementary infinite family

Shunpei Shimizu

Coutinho, Guo and Schmeits (arXiv:2505.11986v4) introduced peak state transfer for continuous quantum walks and remarked in Section 7 that, for adjacency-based dynamics, their computations suggest that there may be infinitely many trees that support peak state transfer. This note gives an elementary positive construction for that remark within unweighted trees; the source itself already gives an infinite family of edge-weighted trees (the weighted paths X_n of its Theorem 6.2) with adjacency peak state transfer, so the novelty claimed here, if any, is restricted to unweighted trees. Every star has adjacency peak state transfer between its centre and a leaf. The trees T(k,m), obtained by attaching k >= 2 copies of the star K_{1,m} to a common root through their centres, form an infinite family of pairwise non-isomorphic non-star trees with adjacency peak state transfer from the root. For vertices in different branches of T(k,m), peak state transfer occurs exactly when sqrt((k+m)/m) = p/q is rational in lowest terms and p, q satisfy an explicit parity or congruence condition; this yields infinitely many trees with adjacency peak state transfer at distance 3 and at distance 4. All peak times are determined. Finite numerical observations (not used in the proofs) and verification code are included. The remark in the source is an observation rather than a formal open problem, and this note makes no claim about stronger questions the source authors may have intended. Trees of the same root-hub-leaf shape were used before for the Laplacian analogue (Open Problem 7.1 of the source): in the-omega-institute/trureturing (issue #14801, pull request #14855, merged on 10 October 2026, Lean 4 formalisation; commit 71980b170a), in the author's own earlier record Zenodo 23216901 (DOI 10.5281/zenodo.23216901, 10 October 2026), and, for the ten-vertex member T(3,2), in Figure 10 of the source. Those results concern the Laplacian; the present note concerns the adjacency matrix and does not use them. The recent arXiv:2610.20855 (Awuah and Guo) reports experiments on perfect and peak state transfer on IBM quantum hardware; its full text contains no infinite family of trees, and its family X_n is the weighted path family of Section 6.3 of the source. Versions 0.1.4 and 0.1.5 change attribution and notation in the prior-work section only. Disclosure: This is a record of personal, independent (hobby) research in which AI was used for exploration, drafting of proof candidates, verification computations and writing. The claims were checked only by an internal AI reviewer; the work has not been reviewed by human experts. Files: main.pdf, main.tex, code.zip (folder code/: Python verification scripts and outputs; unchanged since v0.1.2), README.md, CHANGELOG.md.

•Oct 20, 2026•0 citations

Quantum State Transfer in Graphs

Gabriel Coutinho

Let X be a graph, A its adjacency matrix, and t a non-negative real number. The matrix exp(i t A) determines the evolution in time of a certain quantum system defined on the graph. It represents a continuous-time quantum walk in X. We say that X admits perfect state transfer from a vertex u to a vertex v if there is a time t such that \n| exp(i t A)_(u,v) | = 1. \n \nThe main problem we study in this thesis is that of determining which simple graphs admit perfect state transfer. For some classes of graphs the problem is solved. For example, a path on n vertices admits perfect state transfer if and only if n=2 or n=3. However, the general problem of determining all graphs that admit perfect state transfer is substantially hard. \n \nIn this thesis, we focus on some special cases. We provide necessary and sufficient conditions for a distance-regular graph to admit perfect state transfer. In particular, we provide a detailed account of which distance-regular graphs of diameter three do so. \n \nA graph is said to be spectrally extremal if the number of distinct eigenvalues is equal to the diameter plus one. Distance-regular graphs are examples of such graphs. We study perfect state transfer in spectrally extremal graphs and explore rich connections to the topic of orthogonal polynomials. We characterize perfect state transfer in such graphs. \n \nWe also provide a general framework in which perfect state transfer in graph products can be studied. We use this to determine when direct products and double covers of graphs admit perfect state transfer. As a consequence, we provide many new examples of simple graphs admitting perfect state transfer. We also provide some advances in the understanding of perfect state transfer in Cayley graphs for the groups (Z_2)^d and Z_n. \n \nFinally, we consider the problem of determining which trees admit perfect state transfer. We show more generally that, except for the path on two vertices, if a connected bipartite graph contains a unique perfect matching, then it cannot admit perfect state transfer. We also consider this problem in the context of another model of quantum walks determined by the matrix exp(i t L), where L is the Laplacian matrix of the graph. In particular, we show that no tree on an odd number of vertices admits perfect state transfer according to this model.

•Aug 13, 2014•34 citations

Sedentary quantum walks on bipartite and planar graphs

Karen Meagher, Hermie Monterde

If a quantum walk starting on a vertex tends to stay at home, then that vertex is said to be sedentary. We prove that almost all planar graphs and almost all trees contain at least two sedentary vertices for any assignment of edge weights --- a result that suggests vertex sedentariness is a common phenomenon in trees and planar graphs. For weighted bipartite graphs, we show that a vertex is not sedentary whenever 0 does not belong to its eigenvalue support. Consequently, each vertex in a nonsingular weighted bipartite graph is not sedentary, a stark contrast to weighted trees and weighted planar graphs. A corollary of this result is that every vertex in a bipartite graph with a unique perfect matching is not sedentary for any assignment of edge weights. We also construct new families of weighted bipartite graphs with sedentary vertices using the bipartite double, subdivision operation, and corona product. Finally, we show that unweighted paths and unweighted even cycles contain no sedentary vertices.

math.COCross-listedarXiv:2601.18964•Jan 28, 2026•0 citations
A weighted graph GGG with countable vertex set is bounded if there is an upper bound on the maximum of the sum of absolute values of all edge weights incident to a vertex in GGG. In this paper, we prove a fundamental result on equitable partitions of bounded weighted graphs with twin subgraphs and use this fact to construct finite and bounded infinite graphs with pair and plus state transfer with the adjacency matrix as a Hamiltonian. We show that for each k≥3k \ge 3k≥3, (i) there are infinitely many connected unweighted graphs with maximum degree kkk admitting pair state transfer at τ∈{π2,π2}τ\in\{\fracπ{\sqrt{2}},\fracπ{2}\}τ∈{2​π​,2π​}, and (ii) there are infinitely many signed graphs with exactly one negative edge weight and whose underlying unweighted graphs have maximum degree kkk admitting plus state transfer at τ∈{π2,π2}τ\in\{\fracπ{\sqrt{2}},\fracπ{2}\}τ∈{2​π​,2π​}. Parallel results are proven for perfect state transfer between a plus state and a pair state, and for the existence of sedentary pair and plus states. We further prove that almost all connected unweighted finite planar graphs admit pair state transfer at τ∈{π2,π2}τ\in\{\fracπ{\sqrt{2}},\fracπ{2}\}τ∈{2​π​,2π​}, and almost all connected unweighted finite planar graphs can be assigned a single negative edge weight resulting in plus state transfer, or perfect state transfer between a plus state and a pair state, at τ∈{π2,π2}τ\in\{\fracπ{\sqrt{2}},\fracπ{2}\}τ∈{2​π​,2π​}. Analogous results are shown to hold for unweighted finite trees. Using blow-up graphs, Cayley graphs and graphs with tails, we construct new infinite families of (finite and infinite) unweighted graphs and signed graphs admitting pair or plus state transfer.
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.
Draft note (v0.1.3). We give a connected simple (unweighted) graph on 12 vertices in which the continuous-time quantum walk exp(itA) has perfect state transfer from the pair state e_1 - e_11 to the plus state e_0 + e_2 at time pi/sqrt(2), with a proof that can be checked by hand, and an infinite family obtained by Cartesian products with powers of the path P3. This concerns the question of Monterde and Pal (arXiv:2505.07982v5, Section 10). The product step is a known construction (Godsil, Kirkland and Monterde, SIAM J. Matrix Anal. Appl. 46 (2025) 2093-2115, Corollary 48 and Example 50 in arXiv:2502.08103v4; see also Monterde and Pal, Section 9, and Kirkland, Monterde and Plosker, arXiv:2609.10713, equation (4.1)); we did not find an example of perfect state transfer from a pair state to a plus state in these papers, and no claim of priority is made. Exhaustive computer searches, with numerical tests at stated tolerances, found no example on at most 10 vertices (adjacency and signless Laplacian matrices); these are finite computations, not proofs. Code and outputs are included. Versions 0.1.2 and 0.1.3 correct attribution and citations only. This is a personal hobby/independent research record in which AI was used for exploration, drafting proof candidates, checking and writing; it has not been peer-reviewed by human experts.
Quantum spin systems carry information in the form of quantum states, and the propagation of these quantum states is described by a quantum walk. In order to construct an operational quantum computer, the task of reliably transmitting quantum states from one part of a quantum computer to another must be accomplished. Quantum walks are known to be powerful tools in achieving this task. Pure states are quantum states represented by unit complex vectors. In this thesis, we use algebraic and combinatorial techniques to develop the theory of perfect state transfer on pure states in quantum walks, with emphasis on the adjacency and Laplacian matrices as Hamiltonians of a graph representing a spin network. We prove basic results about eigenvalue supports, periodicity, and strong cospectrality on pure states. We investigate a special type of strong cospectrality called m-strong cospectrality, and show that m-strongly cospectral pure states admit desirable quantum state transfer properties. Several characterisations of perfect state transfer are also given, one for general pure states, one for m-strongly pure states, and another one for real pure states. These characterisations give rise to algebraic and analytic properties of pure states admitting perfect state transfer. Moreover, we determine all complete graphs, complete bipartite graphs, cycles, and paths that admit perfect state transfer between m-strongly pure states. Constructions of infinite families of graphs admitting perfect state transfer are also given. We also characterise perfect state transfer between vertex states in joins and blowup graphs. We determine when the join operation preserves or induces perfect state transfer in the resulting graph. We also use blow-up graphs to construct new families of regular graphs with perfect state transfer. We use these two graph operations to demonstrate that graphs with perfect state transfer can be constructed from graphs that do not exhibit such a property. Finally, we investigate perfect state transfer on s-pair states – pure states that represent entanglement between two vertices. We establish combinatorial and spectral properties of s-pair states with perfect state transfer, and characterise its existence in complete graphs, complete bipartite graphs, paths and distance-regular graphs. Further, we construct infinite families of graphs with s-pair state transfer.
Coutinho, Guo and Schmeits (arXiv:2505.11986v4) introduced peak state transfer for continuous quantum walks and remarked in Section 7 that, for adjacency-based dynamics, their computations suggest that there may be infinitely many trees that support peak state transfer. This note gives an elementary positive construction for that remark within unweighted trees; the source itself already gives an infinite family of edge-weighted trees (the weighted paths X_n of its Theorem 6.2) with adjacency peak state transfer, so the novelty claimed here, if any, is restricted to unweighted trees. Every star has adjacency peak state transfer between its centre and a leaf. The trees T(k,m), obtained by attaching k >= 2 copies of the star K_{1,m} to a common root through their centres, form an infinite family of pairwise non-isomorphic non-star trees with adjacency peak state transfer from the root. For vertices in different branches of T(k,m), peak state transfer occurs exactly when sqrt((k+m)/m) = p/q is rational in lowest terms and p, q satisfy an explicit parity or congruence condition; this yields infinitely many trees with adjacency peak state transfer at distance 3 and at distance 4. All peak times are determined. Finite numerical observations (not used in the proofs) and verification code are included. The remark in the source is an observation rather than a formal open problem, and this note makes no claim about stronger questions the source authors may have intended. Trees of the same root-hub-leaf shape were used before for the Laplacian analogue (Open Problem 7.1 of the source): in the-omega-institute/trureturing (issue #14801, pull request #14855, merged on 10 October 2026, Lean 4 formalisation; commit 71980b170a), in the author's own earlier record Zenodo 23216901 (DOI 10.5281/zenodo.23216901, 10 October 2026), and, for the ten-vertex member T(3,2), in Figure 10 of the source. Those results concern the Laplacian; the present note concerns the adjacency matrix and does not use them. The recent arXiv:2610.20855 (Awuah and Guo) reports experiments on perfect and peak state transfer on IBM quantum hardware; its full text contains no infinite family of trees, and its family X_n is the weighted path family of Section 6.3 of the source. Versions 0.1.4 and 0.1.5 change attribution and notation in the prior-work section only. Disclosure: This is a record of personal, independent (hobby) research in which AI was used for exploration, drafting of proof candidates, verification computations and writing. The claims were checked only by an internal AI reviewer; the work has not been reviewed by human experts. Files: main.pdf, main.tex, code.zip (folder code/: Python verification scripts and outputs; unchanged since v0.1.2), README.md, CHANGELOG.md.
Let X be a graph, A its adjacency matrix, and t a non-negative real number. The matrix exp(i t A) determines the evolution in time of a certain quantum system defined on the graph. It represents a continuous-time quantum walk in X. We say that X admits perfect state transfer from a vertex u to a vertex v if there is a time t such that \n| exp(i t A)_(u,v) | = 1. \n \nThe main problem we study in this thesis is that of determining which simple graphs admit perfect state transfer. For some classes of graphs the problem is solved. For example, a path on n vertices admits perfect state transfer if and only if n=2 or n=3. However, the general problem of determining all graphs that admit perfect state transfer is substantially hard. \n \nIn this thesis, we focus on some special cases. We provide necessary and sufficient conditions for a distance-regular graph to admit perfect state transfer. In particular, we provide a detailed account of which distance-regular graphs of diameter three do so. \n \nA graph is said to be spectrally extremal if the number of distinct eigenvalues is equal to the diameter plus one. Distance-regular graphs are examples of such graphs. We study perfect state transfer in spectrally extremal graphs and explore rich connections to the topic of orthogonal polynomials. We characterize perfect state transfer in such graphs. \n \nWe also provide a general framework in which perfect state transfer in graph products can be studied. We use this to determine when direct products and double covers of graphs admit perfect state transfer. As a consequence, we provide many new examples of simple graphs admitting perfect state transfer. We also provide some advances in the understanding of perfect state transfer in Cayley graphs for the groups (Z_2)^d and Z_n. \n \nFinally, we consider the problem of determining which trees admit perfect state transfer. We show more generally that, except for the path on two vertices, if a connected bipartite graph contains a unique perfect matching, then it cannot admit perfect state transfer. We also consider this problem in the context of another model of quantum walks determined by the matrix exp(i t L), where L is the Laplacian matrix of the graph. In particular, we show that no tree on an odd number of vertices admits perfect state transfer according to this model.
If a quantum walk starting on a vertex tends to stay at home, then that vertex is said to be sedentary. We prove that almost all planar graphs and almost all trees contain at least two sedentary vertices for any assignment of edge weights --- a result that suggests vertex sedentariness is a common phenomenon in trees and planar graphs. For weighted bipartite graphs, we show that a vertex is not sedentary whenever 0 does not belong to its eigenvalue support. Consequently, each vertex in a nonsingular weighted bipartite graph is not sedentary, a stark contrast to weighted trees and weighted planar graphs. A corollary of this result is that every vertex in a bipartite graph with a unique perfect matching is not sedentary for any assignment of edge weights. We also construct new families of weighted bipartite graphs with sedentary vertices using the bipartite double, subdivision operation, and corona product. Finally, we show that unweighted paths and unweighted even cycles contain no sedentary vertices.