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:2412.16351 · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences

Orthogonal polynomials and perfect state transfer

Rachel Bailey

Published Oct 9, 2025• 1 citation
arXivHTMLPDF

Abstract

The aim of this review is to discuss some applications of orthogonal polynomials in quantum information processing. The hope is to keep the paper self-contained so that someone wanting a brief introduction to the theory of orthogonal polynomials and continuous time quantum walks on graphs may find it in one place. In particular, we focus on the associated Jacobi operators and discuss how these can be used to detect perfect state transfer (PST). We also discuss how orthogonal polynomials have been used to give results which are analogous to those given by Karlin and McGregor when studying classical birth and death processes. Finally, we show how these ideas have been extended to quantum walks with more than nearest-neighbour interactions using exceptional orthogonal polynomials (XOPs). We also provide a (non-exhaustive) list of related open questions.This article is part of the theme issue 'Numerical analysis, spectral graph theory, orthogonal polynomials and quantum algorithms'.

DOI
10.1098/rsta.2024.0414

Related papers

Quantum Walks

M. Štefaňák

Over the last two decades quantum walks have proven to be a very useful concept in quantum information processing, quantum communication and quantum simulations. The presented thesis reviews our contribution to this field of research. We provide a thorough introduction to methods used for the study of quantum walks and their potential applications. To keep the presentation intelligible we focus on specific examples. In particular, we analyze in detail the properties of homogeneous quantum walks on a one-dimensional lattice with two and three internal states. The application of the obtained results is illustrated on the examples persistence of unvisited sites and quantum transport to an absorbing sink. We also discuss quantum walks on finite graphs and their applications to quantum search and perfect state transfer. Extension of the presented results, which can be found in enclosed published papers, is discussed in detail.

•Jan 1, 2017•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•35 citations

Symmetric perfect state transfer on bipartite graphs

Xi Li, Xiao Chen, Shouwei Hu +1 more

Abstract Continuous-time quantum walks (CTQW) becoming more significant for quantum information and quantum computation. The perfect state transfer (PST) on graphs is a specific phenomena of CTQW which is widely used in quantum communication of small system, and be found critical for quantum algorithm design recently, such as quantum approximate optimization algorithms and quantum search. If a network $G$ contains $2N$ vertices, and PST occurs between $N$ pairs of vertices at the same time $T$, then we say $G$ admits symmetric PST (SPST). In this work, we will study the SPST on bipartite graphs via spectra. And then, we will present how to set couplings of special bipartite graphs such as cycles, grids and chains to admit SPST is given. For cycles with 6, 8, 10, 12 vertices, we give the analytical method to obtain the couplings to admit SPST. Analogously, the couplings for chains and grids to admit SPST are analytical obtained. We also present a typical approach by using the graph tensor product to construct new quantum networks that admit SPST, in which the new quantum networks are derived from special kinds of integral graphs, such as complete graphs, strongly regular graphs and distance regular graphs.

•Apr 15, 2024•0 citations

Quantum Random Walks

Swarnadeep Majumder, Austen Couvertier

The focus of this project is continuous time quantum walks (QW) on finite graphs. QW are important because they offer one route to universal quantum computation. We studied Perfect State Transfer in a variety of regular graphs, some of which have not been studied earlier. Our work has led to a method of achieving PST between any two nodes of d-dimensional hypercube graph.

•Apr 27, 2018•1 citation

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•Discrete Mathematics•Jun 24, 2026•1 citation

Quantum state transfer in spin chains withq-deformed interaction terms

E. I. Jafarov, Joris Van Der Jeugt

We study the time evolution of a single spin excitation state in certain linear spin chains, as a model for quantum communication. Some years ago it was discovered that when the spin chain data (the nearest neighbour interaction strengths and the magnetic field strengths) are related to the Jacobi matrix entries of Krawtchouk polynomials or dual Hahn polynomials, so-called perfect state transfer takes place. The extension of these ideas to other types of discrete orthogonal polynomials did not lead to new models with perfect state transfer, but did allow more insight in the general computation of the correlation function. In the present paper, we extend the study to discrete orthogonal polynomials of q-hypergeometric type. A remarkable result is a new analytic model where perfect state transfer is achieved: this is when the spin chain data are related to the Jacobi matrix of q-Krawtchouk polynomials. The other cases studied here (affine q-Krawtchouk polynomials, quantum q-Krawtchouk polynomials, dual q-Krawtchouk polynomials, q-Hahn polynomials, dual q-Hahn polynomials and q-Racah polynomials) do not give rise to models with perfect state transfer. However, the computation of the correlation function itself is quite interesting, leading to advanced q-series manipulations.

arXiv:1005.2912•Journal of Physics A Mathematical and Theoretical•Sep 3, 2010•19 citations
The aim of this review is to discuss some applications of orthogonal polynomials in quantum information processing. The hope is to keep the paper self-contained so that someone wanting a brief introduction to the theory of orthogonal polynomials and continuous time quantum walks on graphs may find it in one place. In particular, we focus on the associated Jacobi operators and discuss how these can be used to detect perfect state transfer (PST). We also discuss how orthogonal polynomials have been used to give results which are analogous to those given by Karlin and McGregor when studying classical birth and death processes. Finally, we show how these ideas have been extended to quantum walks with more than nearest-neighbour interactions using exceptional orthogonal polynomials (XOPs). We also provide a (non-exhaustive) list of related open questions.This article is part of the theme issue 'Numerical analysis, spectral graph theory, orthogonal polynomials and quantum algorithms'.
Over the last two decades quantum walks have proven to be a very useful concept in quantum information processing, quantum communication and quantum simulations. The presented thesis reviews our contribution to this field of research. We provide a thorough introduction to methods used for the study of quantum walks and their potential applications. To keep the presentation intelligible we focus on specific examples. In particular, we analyze in detail the properties of homogeneous quantum walks on a one-dimensional lattice with two and three internal states. The application of the obtained results is illustrated on the examples persistence of unvisited sites and quantum transport to an absorbing sink. We also discuss quantum walks on finite graphs and their applications to quantum search and perfect state transfer. Extension of the presented results, which can be found in enclosed published papers, is discussed in detail.
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.
Abstract Continuous-time quantum walks (CTQW) becoming more significant for quantum information and quantum computation. The perfect state transfer (PST) on graphs is a specific phenomena of CTQW which is widely used in quantum communication of small system, and be found critical for quantum algorithm design recently, such as quantum approximate optimization algorithms and quantum search. If a network GGG contains 2N2N2N vertices, and PST occurs between NNN pairs of vertices at the same time TTT, then we say GGG admits symmetric PST (SPST). In this work, we will study the SPST on bipartite graphs via spectra. And then, we will present how to set couplings of special bipartite graphs such as cycles, grids and chains to admit SPST is given. For cycles with 6, 8, 10, 12 vertices, we give the analytical method to obtain the couplings to admit SPST. Analogously, the couplings for chains and grids to admit SPST are analytical obtained. We also present a typical approach by using the graph tensor product to construct new quantum networks that admit SPST, in which the new quantum networks are derived from special kinds of integral graphs, such as complete graphs, strongly regular graphs and distance regular graphs.
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.
We study the time evolution of a single spin excitation state in certain linear spin chains, as a model for quantum communication. Some years ago it was discovered that when the spin chain data (the nearest neighbour interaction strengths and the magnetic field strengths) are related to the Jacobi matrix entries of Krawtchouk polynomials or dual Hahn polynomials, so-called perfect state transfer takes place. The extension of these ideas to other types of discrete orthogonal polynomials did not lead to new models with perfect state transfer, but did allow more insight in the general computation of the correlation function. In the present paper, we extend the study to discrete orthogonal polynomials of q-hypergeometric type. A remarkable result is a new analytic model where perfect state transfer is achieved: this is when the spin chain data are related to the Jacobi matrix of q-Krawtchouk polynomials. The other cases studied here (affine q-Krawtchouk polynomials, quantum q-Krawtchouk polynomials, dual q-Krawtchouk polynomials, q-Hahn polynomials, dual q-Hahn polynomials and q-Racah polynomials) do not give rise to models with perfect state transfer. However, the computation of the correlation function itself is quite interesting, leading to advanced q-series manipulations.