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:2404.02236 · Special Matrices

Selected open problems in continuous-time quantum walks

Gabriel Coutinho, Krystal Guo

Published Jan 1, 2024• 3 citations
arXivHTMLPDF

Abstract

Abstract Quantum walks on graphs are fundamental to quantum computing and have led to many interesting open problems in algebraic graph theory. This review article highlights three key classes of open problems in this domain: perfect state transfer, instantaneous uniform mixing, and average mixing matrices. In highlighting these open problems, our aim is to stimulate further research and exploration in this rapidly evolving field.

DOI
10.1515/spma-2024-0025

Related papers

Real State Transfer

Chris D. Godsil

A continuous quantum walk on a graph $X$ with adjacency matrix $A$ is specified by the 1-parameter family of unitary matrices $U(t)=\exp(itA)$. These matrices act on the state space of a quantum system, the states of which we may represent by density matrices, positive semidefinite matrices with rows and columns indexed by $V(X)$ and with trace $1$. The square of the absolute values of the entries of a column of $U(t)$ define a probability density on $V(X)$, and it is precisely these densities that predict the outcomes of measurements. There are two special cases of physical interest: when the column density is supported on a vertex, and when it is uniform. In the first case we have perfect state transfer; in the second, uniform mixing. There are many results concerning state transfer and uniform mixing. In this paper we show that these results on perfect state transfer hold largely because at the time it occurs, the density matrix is real. We also show that the results on uniform mixing obtained so far hold because the entries of the density matrix are algebraic numbers. As a consequence of these we derive strong restrictions on the occurence of uniform mixing on bipartite graphs and on oriented graphs.

arXiv:1710.04042•Oct 11, 2017•4 citations

Irrational Quantum Walks

Gabriel Coutinho, Pedro Ferreira Baptista, Chris D. Godsil +2 more

Abstract. The adjacency matrix of a graph [Formula: see text] is the Hamiltonian for a continuous-time quantum walk on the vertices of [Formula: see text]. Although the entries of the adjacency matrix are integers, its eigenvalues are generally irrational and, because of this, the behavior of the walk is typically not periodic. In this paper, we develop a theory to exactly study any quantum walk generated by an integral Hamiltonian, and we put emphasis on those with irrational eigenvalues—what we call irrational quantum walks. As a result, we provide exact methods to compute the average of the mixing matrices, and to decide whether pretty good (or almost perfect) state transfer occurs in a given graph. We also use our methods to study geometric properties of beautiful curves arising from entries of the quantum walk matrix and discuss possible applications of these results. Throughout the paper, we emphasize the interplay between different fields of mathematics applied to the study of quantum walks.

arXiv:2208.08971•SIAM Journal on Applied Algebra and Geometry•Jul 25, 2023•5 citations

Uniform Mixing of Quantum Walks and Association Schemes

Natalie Mullin

In recent years quantum algorithms have become a popular area of mathematical research. Farhi and Gutmann introduced the concept of a quantum walk in 1998. In this thesis we investigate mixing properties of continuous-time quantum walks from a mathematical perspective. We focus on the connections between mixing properties and association schemes. \n \nThere are three main goals of this thesis. Our primary goal is to develop the algebraic groundwork necessary to systematically study mixing properties of continuous-time quantum walks on regular graphs. Using these tools we achieve two additional goals: we construct new families of graphs that admit uniform mixing, and we prove that other families of graphs never admit uniform mixing. \n \nWe begin by introducing association schemes and continuous-time quantum walks. Within this framework we develop specific algebraic machinery to tackle the uniform mixing problem. Our main algebraic result shows that if a graph has an irrational eigenvalue, then its transition matrix has at least one transcendental coordinate at all nonzero times. \n \nNext we study algebraic varieties related to uniform mixing to determine information about the coordinates of the corresponding transition matrices. Combining this with our main algebraic result we prove that uniform mixing does not occur on even cycles or prime cycles. However, we show that the probability distribution of a quantum walk on a prime cycle gets arbitrarily close to uniform. \n \nFinally we consider uniform mixing on Cayley graphs of elementary abelian groups. We utilize graph quotients to connect the mixing properties of these graphs to Hamming graphs. This enables us to find new results about uniform mixing on Cayley graphs of certain elementary abelian groups.

•Sep 26, 2013•3 citations

A note on graphs resistant to quantum uniform mixing

William Adamczak, Kevin Andrew, Peter Hernberg +1 more

Continuous-time quantum walks on graphs is a generalization of continuous-time Markov chains on discrete structures. Moore and Russell proved that the continuous-time quantum walk on the $n$-cube is instantaneous exactly uniform mixing but has no average mixing property. On complete (circulant) graphs $K_{n}$, the continuous-time quantum walk is neither instantaneous (except for $n=2,3,4$) nor average uniform mixing (except for $n=2$). We explore two natural {\em group-theoretic} generalizations of the $n$-cube as a $G$-circulant and as a bunkbed $G \rtimes \Int_{2}$, where $G$ is a finite group. Analyses of these classes suggest that the $n$-cube might be special in having instantaneous uniform mixing and that non-uniform average mixing is pervasive, i.e., no memoryless property for the average limiting distribution; an implication of these graphs having zero spectral gap. But on the bunkbeds, we note a memoryless property with respect to the two partitions. We also analyze average mixing on complete paths, where the spectral gaps are nonzero.

arXiv:quant-ph/0308073•Aug 13, 2003•14 citations

Complex Hadamard matrices, instantaneous uniform mixing and cubes

Ada Chan

We study the continuous-time quantum walks on graphs in the adjacency algebra of the n -cube and its related distance regular graphs. For k ≥ 2 , we find graphs in the adjacency algebra of ( 2 k + 2 - 8 ) -cube that admit instantaneous uniform mixing at time π / 2 k and graphs that have perfect state transfer at time π / 2 k . We characterize the folded n -cubes, the halved n -cubes and the folded halved n -cubes whose adjacency algebra contains a complex Hadamard matrix. We obtain the same conditions for the characterization of these graphs admitting instantaneous uniform mixing.

arXiv:1305.5811•Algebraic Combinatorics•Jun 2, 2020•24 citations

Orthogonal polynomials and perfect state transfer

Rachel Bailey

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'.

arXiv:2412.16351•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Oct 9, 2025•0 citations
Abstract Quantum walks on graphs are fundamental to quantum computing and have led to many interesting open problems in algebraic graph theory. This review article highlights three key classes of open problems in this domain: perfect state transfer, instantaneous uniform mixing, and average mixing matrices. In highlighting these open problems, our aim is to stimulate further research and exploration in this rapidly evolving field.
A continuous quantum walk on a graph XXX with adjacency matrix AAA is specified by the 1-parameter family of unitary matrices U(t)=exp⁡(itA)U(t)=\exp(itA)U(t)=exp(itA). These matrices act on the state space of a quantum system, the states of which we may represent by density matrices, positive semidefinite matrices with rows and columns indexed by V(X)V(X)V(X) and with trace 111. The square of the absolute values of the entries of a column of U(t)U(t)U(t) define a probability density on V(X)V(X)V(X), and it is precisely these densities that predict the outcomes of measurements. There are two special cases of physical interest: when the column density is supported on a vertex, and when it is uniform. In the first case we have perfect state transfer; in the second, uniform mixing. There are many results concerning state transfer and uniform mixing. In this paper we show that these results on perfect state transfer hold largely because at the time it occurs, the density matrix is real. We also show that the results on uniform mixing obtained so far hold because the entries of the density matrix are algebraic numbers. As a consequence of these we derive strong restrictions on the occurence of uniform mixing on bipartite graphs and on oriented graphs.
Abstract. The adjacency matrix of a graph [Formula: see text] is the Hamiltonian for a continuous-time quantum walk on the vertices of [Formula: see text]. Although the entries of the adjacency matrix are integers, its eigenvalues are generally irrational and, because of this, the behavior of the walk is typically not periodic. In this paper, we develop a theory to exactly study any quantum walk generated by an integral Hamiltonian, and we put emphasis on those with irrational eigenvalues—what we call irrational quantum walks. As a result, we provide exact methods to compute the average of the mixing matrices, and to decide whether pretty good (or almost perfect) state transfer occurs in a given graph. We also use our methods to study geometric properties of beautiful curves arising from entries of the quantum walk matrix and discuss possible applications of these results. Throughout the paper, we emphasize the interplay between different fields of mathematics applied to the study of quantum walks.
In recent years quantum algorithms have become a popular area of mathematical research. Farhi and Gutmann introduced the concept of a quantum walk in 1998. In this thesis we investigate mixing properties of continuous-time quantum walks from a mathematical perspective. We focus on the connections between mixing properties and association schemes. \n \nThere are three main goals of this thesis. Our primary goal is to develop the algebraic groundwork necessary to systematically study mixing properties of continuous-time quantum walks on regular graphs. Using these tools we achieve two additional goals: we construct new families of graphs that admit uniform mixing, and we prove that other families of graphs never admit uniform mixing. \n \nWe begin by introducing association schemes and continuous-time quantum walks. Within this framework we develop specific algebraic machinery to tackle the uniform mixing problem. Our main algebraic result shows that if a graph has an irrational eigenvalue, then its transition matrix has at least one transcendental coordinate at all nonzero times. \n \nNext we study algebraic varieties related to uniform mixing to determine information about the coordinates of the corresponding transition matrices. Combining this with our main algebraic result we prove that uniform mixing does not occur on even cycles or prime cycles. However, we show that the probability distribution of a quantum walk on a prime cycle gets arbitrarily close to uniform. \n \nFinally we consider uniform mixing on Cayley graphs of elementary abelian groups. We utilize graph quotients to connect the mixing properties of these graphs to Hamming graphs. This enables us to find new results about uniform mixing on Cayley graphs of certain elementary abelian groups.
Continuous-time quantum walks on graphs is a generalization of continuous-time Markov chains on discrete structures. Moore and Russell proved that the continuous-time quantum walk on the nnn-cube is instantaneous exactly uniform mixing but has no average mixing property. On complete (circulant) graphs KnK_{n}Kn​, the continuous-time quantum walk is neither instantaneous (except for n=2,3,4n=2,3,4n=2,3,4) nor average uniform mixing (except for n=2n=2n=2). We explore two natural {\em group-theoretic} generalizations of the nnn-cube as a GGG-circulant and as a bunkbed $G \rtimes \Int_{2}$, where GGG is a finite group. Analyses of these classes suggest that the nnn-cube might be special in having instantaneous uniform mixing and that non-uniform average mixing is pervasive, i.e., no memoryless property for the average limiting distribution; an implication of these graphs having zero spectral gap. But on the bunkbeds, we note a memoryless property with respect to the two partitions. We also analyze average mixing on complete paths, where the spectral gaps are nonzero.
We study the continuous-time quantum walks on graphs in the adjacency algebra of the n -cube and its related distance regular graphs. For k ≥ 2 , we find graphs in the adjacency algebra of ( 2 k + 2 - 8 ) -cube that admit instantaneous uniform mixing at time π / 2 k and graphs that have perfect state transfer at time π / 2 k . We characterize the folded n -cubes, the halved n -cubes and the folded halved n -cubes whose adjacency algebra contains a complex Hadamard matrix. We obtain the same conditions for the characterization of these graphs admitting instantaneous uniform mixing.
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'.