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:2411.05560 · The Electronic Journal of Combinatorics

State Transfer in Discrete-Time Quantum Walks via Projected Transition Matrices

Krystal Guo, Vincent Schmeits

Published Oct 9, 2026• 1 citation
arXivHTMLPDF

Abstract

In this paper, we analyze state transfer in quantum walks by using combinatorial methods. We generalize perfect state transfer in two-reflection discrete-time quantum walks to a notion that we call peak state transfer; we define peak state transfer as the highest state transfer that can be achieved between an initial and a target state under unitary evolution, even when perfect state transfer is unattainable. We give a spectral characterization of peak state transfer that allows us to fully characterize peak state transfer in the arc-reversal (Grover) walk on various families of graphs, including strongly regular graphs and incidence graphs of block designs (assuming that the walk starts at a point of the design). In addition, we provide many examples of peak state transfer, including an infinite family where the amount of peak state transfer tends to $1$ as the number of vertices grows. We further demonstrate that peak state transfer properties extend to infinite families of graphs generated by vertex blow-ups, and we characterize periodicity in the vertex-face walk on toroidal grids. In our analysis, we make extensive use of the spectral decomposition of a matrix that is obtained by projecting the transition matrix down onto a subspace. Though we are motivated by a problem in quantum computing, we identify several open problems that are purely combinatorial, arising from the spectral conditions required for peak state transfer in discrete-time quantum walks.

DOI
10.37236/13764

Related papers

Perfect state transfer in quantum walks on orientable maps

Krystal Guo, Vincent Schmeits

A discrete-time quantum walk is the quantum analogue of a Markov chain on a graph. We show that the evolution of a general discrete-time quantum walk that consists of two reflections satisfies a Chebyshev recurrence, under a projection. We apply this to study perfect state transfer in a model of discrete-time quantum walk whose transition matrix is given by two reflections, defined by the face and vertex incidence relations of a graph embedded in an orientable surface, proposed by Zhan [ J. Algebraic Combin. 53(4):1187–1213, 2020]. For this model, called the vertex-face walk, we prove results about perfect state transfer and periodicity and give infinite families of examples where these occur. In doing so, we bring together tools from algebraic and topological graph theory to analyze the evolution of this walk.

arXiv:2211.12841•Algebraic Combinatorics•Jun 27, 2024•4 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

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

Peak state transfer in continuous quantum walks

Gabriel Coutinho, Krystal Guo, Vincent Schmeits

We introduce and study peak state transfer, a notion of high state transfer in qubit networks modeled by continuous-time quantum walks. Unlike perfect or pretty good state transfer, peak state transfer does not require fidelity arbitrarily close to 1, but crucially allows for an explicit determination of the time at which transfer occurs. We provide a spectral characterization of peak state transfer, which allows us to find many examples of peak state transfer, and we also establish tight lower bounds on fidelity and success probability. As a central example, we construct a family of weighted path graphs that admit peak state transfer over arbitrarily long distances with transfer probability approaching $π/4 \approx 0.78$. These graphs offer exponentially improved sensitivity over known perfect state transfer examples such as the weighted paths related to hypercubes, making them practical candidates for efficient quantum wires.

arXiv:2505.11986•May 17, 2025•0 citations

Perfect state transfer in Grover walks on normal Cayley graphs

Koushik Bhakta, Bikash Bhattacharjya

A Cayley graph $\operatorname{Cay}(Γ,S)$ over a finite group $Γ$ is said to be normal if its connection set $S$ is a union of some conjugacy classes of $Γ$. This paper investigates perfect state transfer in Grover walks on normal Cayley graphs. The Grover walk is a widely studied discrete-time quantum walk. We establish a necessary and sufficient condition for the occurrence of perfect state transfer on normal Cayley graphs. As applications, we derive explicit spectral criteria for perfect state transfer on Cayley graphs over abelian groups, dicyclic groups, and dihedral groups. These results yield several infinite families of Cayley graphs exhibiting perfect state transfer. We further obtain simple combinatorial characterizations of the existence of perfect state transfer on Cayley graphs over dihedral and dicyclic groups. Our general characterization also recovers a number of previously known results as special cases. As a further consequence, we obtain a complete characterization of perfect state transfer on unitary Cayley graphs. In particular, we prove that exactly four graphs in the class of unitary Cayley graphs exhibit perfect state transfer.

quant-pharXiv:2607.19309•Jul 22, 2026•0 citations

Edge State Transfer

Qiuting Chen

Let G be a graph and let t be a positive real number. Then the evolution of the continuous quantum walk defined on G is described by the transition matrix U(t)=exp(itH).The matrix H is called Hamiltonian. So far the most studied quantum walks are the ones whose Hamiltonians are the adjacency matrices of the underlying graphs and initial states are vertex states e_a, with e_a being the characteristic vector of vertex a. \n \nThis thesis focuses on Laplacian edge state transfer, that is, the quantum walks whose initial states are edge states e_a-e_b and Hamiltonians are the Laplacians of the underlying graphs. So far the research about perfect state transfer only involves vertex states and Laplacian edge state transfer has not been studied before. We extend the known results of perfect vertex state transfer and periodicity of vertex states to Laplacian edge state transfer. \n \nWe prove two useful closure properties for perfect Laplacian edge state transfer. One is that complementation preserves perfect edge state transfer. The other is that if G has perfect Laplacian edge state transfer at time τ and H has perfect Laplacian vertex state transfer also at time τ, then with some mild assumption on the pairs of vertex states and edge states that have perfect state transfer, the Cartesian product G □ H also admits perfect edge state transfer. Those two properties provide us new ways to construct graphs with perfect Laplacian edge state transfer. We also observe one phenomenon that happens in Laplacian edge state transfer which never happens in vertex state transfer: if there is perfect state transfer from e_a-e_b to e_α-e_β and also from e_b-e_c to e_β-e_γ at the same time t in G, then G admits perfect state transfer from e_a-e_c to e_α-e_γ at time t. \n \nWe give characterizations of perfect Laplacian edge state transfer in cycles, paths and complete bipartite graphs K_{2,4n}. We study perfect state transfer and periodicity on edge states with special spectral features. We also consider the case when the unsigned Laplacian is Hamiltonian and initial states are plus states of the form e_a+e_b. In this case, we characterize perfect state transfer in paths, cycles and bipartite graphs. \nWe close this thesis by a list of open questions.

•Jan 11, 2019•2 citations
In this paper, we analyze state transfer in quantum walks by using combinatorial methods. We generalize perfect state transfer in two-reflection discrete-time quantum walks to a notion that we call peak state transfer; we define peak state transfer as the highest state transfer that can be achieved between an initial and a target state under unitary evolution, even when perfect state transfer is unattainable. We give a spectral characterization of peak state transfer that allows us to fully characterize peak state transfer in the arc-reversal (Grover) walk on various families of graphs, including strongly regular graphs and incidence graphs of block designs (assuming that the walk starts at a point of the design). In addition, we provide many examples of peak state transfer, including an infinite family where the amount of peak state transfer tends to 111 as the number of vertices grows. We further demonstrate that peak state transfer properties extend to infinite families of graphs generated by vertex blow-ups, and we characterize periodicity in the vertex-face walk on toroidal grids. In our analysis, we make extensive use of the spectral decomposition of a matrix that is obtained by projecting the transition matrix down onto a subspace. Though we are motivated by a problem in quantum computing, we identify several open problems that are purely combinatorial, arising from the spectral conditions required for peak state transfer in discrete-time quantum walks.
A discrete-time quantum walk is the quantum analogue of a Markov chain on a graph. We show that the evolution of a general discrete-time quantum walk that consists of two reflections satisfies a Chebyshev recurrence, under a projection. We apply this to study perfect state transfer in a model of discrete-time quantum walk whose transition matrix is given by two reflections, defined by the face and vertex incidence relations of a graph embedded in an orientable surface, proposed by Zhan [ J. Algebraic Combin. 53(4):1187–1213, 2020]. For this model, called the vertex-face walk, we prove results about perfect state transfer and periodicity and give infinite families of examples where these occur. In doing so, we bring together tools from algebraic and topological graph theory to analyze the evolution of this walk.
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.
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.
We introduce and study peak state transfer, a notion of high state transfer in qubit networks modeled by continuous-time quantum walks. Unlike perfect or pretty good state transfer, peak state transfer does not require fidelity arbitrarily close to 1, but crucially allows for an explicit determination of the time at which transfer occurs. We provide a spectral characterization of peak state transfer, which allows us to find many examples of peak state transfer, and we also establish tight lower bounds on fidelity and success probability. As a central example, we construct a family of weighted path graphs that admit peak state transfer over arbitrarily long distances with transfer probability approaching π/4≈0.78π/4 \approx 0.78π/4≈0.78. These graphs offer exponentially improved sensitivity over known perfect state transfer examples such as the weighted paths related to hypercubes, making them practical candidates for efficient quantum wires.
A Cayley graph Cay⁡(Γ,S)\operatorname{Cay}(Γ,S)Cay(Γ,S) over a finite group ΓΓΓ is said to be normal if its connection set SSS is a union of some conjugacy classes of ΓΓΓ. This paper investigates perfect state transfer in Grover walks on normal Cayley graphs. The Grover walk is a widely studied discrete-time quantum walk. We establish a necessary and sufficient condition for the occurrence of perfect state transfer on normal Cayley graphs. As applications, we derive explicit spectral criteria for perfect state transfer on Cayley graphs over abelian groups, dicyclic groups, and dihedral groups. These results yield several infinite families of Cayley graphs exhibiting perfect state transfer. We further obtain simple combinatorial characterizations of the existence of perfect state transfer on Cayley graphs over dihedral and dicyclic groups. Our general characterization also recovers a number of previously known results as special cases. As a further consequence, we obtain a complete characterization of perfect state transfer on unitary Cayley graphs. In particular, we prove that exactly four graphs in the class of unitary Cayley graphs exhibit perfect state transfer.
Let G be a graph and let t be a positive real number. Then the evolution of the continuous quantum walk defined on G is described by the transition matrix U(t)=exp(itH).The matrix H is called Hamiltonian. So far the most studied quantum walks are the ones whose Hamiltonians are the adjacency matrices of the underlying graphs and initial states are vertex states e_a, with e_a being the characteristic vector of vertex a. \n \nThis thesis focuses on Laplacian edge state transfer, that is, the quantum walks whose initial states are edge states e_a-e_b and Hamiltonians are the Laplacians of the underlying graphs. So far the research about perfect state transfer only involves vertex states and Laplacian edge state transfer has not been studied before. We extend the known results of perfect vertex state transfer and periodicity of vertex states to Laplacian edge state transfer. \n \nWe prove two useful closure properties for perfect Laplacian edge state transfer. One is that complementation preserves perfect edge state transfer. The other is that if G has perfect Laplacian edge state transfer at time τ and H has perfect Laplacian vertex state transfer also at time τ, then with some mild assumption on the pairs of vertex states and edge states that have perfect state transfer, the Cartesian product G □ H also admits perfect edge state transfer. Those two properties provide us new ways to construct graphs with perfect Laplacian edge state transfer. We also observe one phenomenon that happens in Laplacian edge state transfer which never happens in vertex state transfer: if there is perfect state transfer from e_a-e_b to e_α-e_β and also from e_b-e_c to e_β-e_γ at the same time t in G, then G admits perfect state transfer from e_a-e_c to e_α-e_γ at time t. \n \nWe give characterizations of perfect Laplacian edge state transfer in cycles, paths and complete bipartite graphs K_{2,4n}. We study perfect state transfer and periodicity on edge states with special spectral features. We also consider the case when the unsigned Laplacian is Hamiltonian and initial states are plus states of the form e_a+e_b. In this case, we characterize perfect state transfer in paths, cycles and bipartite graphs. \nWe close this thesis by a list of open questions.