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

Laziness of Quantum Walks on Graphs

Amulya Mohan, Christino Tamon, Yichi Xu, Hanmeng Zhan

math.COcs.DMquant-phSubmitted Aug 21, 2026• Announced Aug 24, 2026• 0 citations
arXivHTMLPDF

Abstract

The trace of the average mixing matrix of a quantum walk measures the "laziness" of the walk: the higher the trace, the more likely that the walker returns home in the long run. In this paper, we develop tools to study this graph invariant arising from Laplacian quantum walks. It is known that the complete graph $K_n$ is the laziest connected graph on $n$ vertices. Using our machinery, we show that the star $S_n$ is the second laziest connected graph on $n$ vertices (and hence the laziest tree on $n$ vertices), the complete multipartite graph $K_{n-2,1,1}$ is the third laziest connected graph on $n$ vertices, and the double star $DS(n-3,1)$ is the second laziest tree on $n$ vertices. We also show that on the same number of vertices, more unbalanced double stars are lazier.

Related papers

Quantum walks as a probe of structural anomalies in graphs

Mark S. Hillery, Hongjun Zheng, Edgar Feldman +2 more

We study how quantum walks can be used to find structural anomalies in graphs via several examples. Two of our examples are based on star graphs, graphs with a single central vertex to which the other vertices, which we call external vertices, are connected by edges. In the basic star graph, these are the only edges. If we now connect a subset of the external vertices to form a complete subgraph, a quantum walk can be used to find these vertices with a quantum speedup. Thus, under some circumstances, a quantum walk can be used to locate where the connectivity of a network changes. We also look at the case of two stars connected at one of their external vertices. A quantum walk can find the vertex shared by both graphs, again with a quantum speedup. This provides an example of using a quantum walk in order to find where two networks are connected. Finally, we use a quantum walk on a complete bipartite graph to find an extra edge that destroys the bipartite nature of the graph.

arXiv:1206.6298•Physical Review A•Jun 27, 2012•24 citations

Laplacian Fractional Revival on Graphs

Ada Chan, Bobae Johnson, Mengzhen Liu +3 more

We develop the theory of fractional revival in the quantum walk on a graph using its Laplacian matrix as the Hamiltonian. We first give a spectral characterization of Laplacian fractional revival, which leads to a polynomial time algorithm to check this phenomenon and find the earliest time when it occurs. We then apply the characterization theorem to special families of graphs. In particular, we show that no tree admits Laplacian fractional revival except for the paths on two and three vertices, and the only graphs on a prime number of vertices that admit Laplacian fractional revival are double cones. Finally, we construct, through Cartesian products and joins, several infinite families of graphs that admit Laplacian fractional revival; some of these graphs exhibit polygamous fractional revival.

arXiv:2010.10413•The Electronic Journal of Combinatorics•Jul 16, 2021•8 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

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

Quantum walks and graph operations

Joy Cooper, Homer De Vera, Hermie Monterde +3 more

Let $U_X(t)$ be the transition matrix of a quantum walk on a graph $X$ relative to its adjacency matrix $A$ or the Laplacian matrix $L$. This paper investigates the behavior of quantum walks under Cartesian products, joins, and graph complements. We have two main goals. First, we characterize the conditions such that peak state transfer and pretty good state transfer are preserved under these operations, allowing us to construct new families of graphs admitting these properties. Our second goal is to analyze the relationship between the quantum walks on a graph and its complement. We provide bounds for $f_{u,v}(t)=\big|U_{X^c}(t)_{u,v}-e^{itδ}U_X(-t)_{u,v}\big|$ and $g_{u,v}(t)=\big||U_X(t)_{u,v}|-|U_{X^c}(t)_{u,v}|\big|$, where $δ=-1$ when dealing with $A$ and $δ=n$ otherwise. Note that $f_{u,v}(t)$ and $g_{u,v}(t)$ both measure the difference between the behavior of quantum state transfer between vertices $u$ and $v$ in a graph and its complement. If $X$ is regular or $M=L$, then $f_{u,v}(t)$ is bounded above by $\frac{2}{|V(X)|}$. If $X$ is non-regular and $M=A$, then we utilize the main eigenvalues of a graph to obtain an upper bound for $f_{u,v}(t)$ which depends only on $A$. We also use the bounding matrix of the graph to give bounds for the Nordhaus-Gaddum type relations $|U_X(t)_{u,v}|+|U_{X^c}(t)_{u,v}|$ and $|U_X(t)_{u,v}|\cdot |U_{X^c}(t)_{u,v}|$. Finally, we demonstrate that most of our bounds are sharp for certain families of graphs.

arXiv:2610.07673•Oct 6, 2026•0 citations

Local εεε-uniform mixing in continuous quantum walks

Hermie Monterde

Let $X$ be a weighted graph and $M$ be its adjacency, Laplacian or signless Laplacian matrix. In a continuous quantum walk on $X$, local $ε$-uniform mixing occurs at vertex $u$ if the $u$th column of the matrix $U(t)=e^{itM}$ can be made arbitrarily close to a vector whose all entries have equal magnitude. Using the spectral and combinatorial properties of $X$, we derive necessary conditions for local $ε$-uniform mixing to occur in $X$. This includes an inequality involving all entries of each eigenvector of $M$, as well as an upper bound on the degree of vertex $u$ when $M$ is the Laplacian or signless Laplacian matrix. We use these necessary conditions to rule out local $ε$-uniform mixing in numerous classes of graphs, most of which are non-regular. We also show that almost all planar graphs (resp., trees) contain a vertex that does not admit local $ε$-uniform mixing for any assignment of edge weights. Furthermore, we prove if $X$ has $n$ vertices and admits local $ε$-uniform mixing at a vertex contained in a subgraph with a twin, then the number of vertices of this twin subgraph must be at least $\sqrt{n}$. In particular, we establish that a graph on $n\geq 5$ vertices does not admit local $ε$-uniform mixing at a vertex with a twin.

arXiv:2603.20977•Mar 21, 2026•0 citations
The trace of the average mixing matrix of a quantum walk measures the "laziness" of the walk: the higher the trace, the more likely that the walker returns home in the long run. In this paper, we develop tools to study this graph invariant arising from Laplacian quantum walks.
It is known that the complete graph KnK_nKn​ is the laziest connected graph on nnn vertices. Using our machinery, we show that the star SnS_nSn​ is the second laziest connected graph on nnn vertices (and hence the laziest tree on nnn vertices), the complete multipartite graph Kn−2,1,1K_{n-2,1,1}Kn−2,1,1​ is the third laziest connected graph on nnn vertices, and the double star DS(n−3,1)DS(n-3,1)DS(n−3,1) is the second laziest tree on nnn vertices. We also show that on the same number of vertices, more unbalanced double stars are lazier.
We study how quantum walks can be used to find structural anomalies in graphs via several examples. Two of our examples are based on star graphs, graphs with a single central vertex to which the other vertices, which we call external vertices, are connected by edges. In the basic star graph, these are the only edges. If we now connect a subset of the external vertices to form a complete subgraph, a quantum walk can be used to find these vertices with a quantum speedup. Thus, under some circumstances, a quantum walk can be used to locate where the connectivity of a network changes. We also look at the case of two stars connected at one of their external vertices. A quantum walk can find the vertex shared by both graphs, again with a quantum speedup. This provides an example of using a quantum walk in order to find where two networks are connected. Finally, we use a quantum walk on a complete bipartite graph to find an extra edge that destroys the bipartite nature of the graph.
We develop the theory of fractional revival in the quantum walk on a graph using its Laplacian matrix as the Hamiltonian. We first give a spectral characterization of Laplacian fractional revival, which leads to a polynomial time algorithm to check this phenomenon and find the earliest time when it occurs. We then apply the characterization theorem to special families of graphs. In particular, we show that no tree admits Laplacian fractional revival except for the paths on two and three vertices, and the only graphs on a prime number of vertices that admit Laplacian fractional revival are double cones. Finally, we construct, through Cartesian products and joins, several infinite families of graphs that admit Laplacian fractional revival; some of these graphs exhibit polygamous fractional revival.
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.
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.
Let UX(t)U_X(t)UX​(t) be the transition matrix of a quantum walk on a graph XXX relative to its adjacency matrix AAA or the Laplacian matrix LLL. This paper investigates the behavior of quantum walks under Cartesian products, joins, and graph complements. We have two main goals. First, we characterize the conditions such that peak state transfer and pretty good state transfer are preserved under these operations, allowing us to construct new families of graphs admitting these properties. Our second goal is to analyze the relationship between the quantum walks on a graph and its complement. We provide bounds for fu,v(t)=∣UXc(t)u,v−eitδUX(−t)u,v∣f_{u,v}(t)=\big|U_{X^c}(t)_{u,v}-e^{itδ}U_X(-t)_{u,v}\big|fu,v​(t)=​UXc​(t)u,v​−eitδUX​(−t)u,v​​ and gu,v(t)=∣∣UX(t)u,v∣−∣UXc(t)u,v∣∣g_{u,v}(t)=\big||U_X(t)_{u,v}|-|U_{X^c}(t)_{u,v}|\big|gu,v​(t)=​∣UX​(t)u,v​∣−∣UXc​(t)u,v​∣​, where δ=−1δ=-1δ=−1 when dealing with AAA and δ=nδ=nδ=n otherwise. Note that fu,v(t)f_{u,v}(t)fu,v​(t) and gu,v(t)g_{u,v}(t)gu,v​(t) both measure the difference between the behavior of quantum state transfer between vertices uuu and vvv in a graph and its complement. If XXX is regular or M=LM=LM=L, then fu,v(t)f_{u,v}(t)fu,v​(t) is bounded above by 2∣V(X)∣\frac{2}{|V(X)|}∣V(X)∣2​. If XXX is non-regular and M=AM=AM=A, then we utilize the main eigenvalues of a graph to obtain an upper bound for fu,v(t)f_{u,v}(t)fu,v​(t) which depends only on AAA. We also use the bounding matrix of the graph to give bounds for the Nordhaus-Gaddum type relations ∣UX(t)u,v∣+∣UXc(t)u,v∣|U_X(t)_{u,v}|+|U_{X^c}(t)_{u,v}|∣UX​(t)u,v​∣+∣UXc​(t)u,v​∣ and ∣UX(t)u,v∣⋅∣UXc(t)u,v∣|U_X(t)_{u,v}|\cdot |U_{X^c}(t)_{u,v}|∣UX​(t)u,v​∣⋅∣UXc​(t)u,v​∣. Finally, we demonstrate that most of our bounds are sharp for certain families of graphs.
Let XXX be a weighted graph and MMM be its adjacency, Laplacian or signless Laplacian matrix. In a continuous quantum walk on XXX, local εεε-uniform mixing occurs at vertex uuu if the uuuth column of the matrix U(t)=eitMU(t)=e^{itM}U(t)=eitM can be made arbitrarily close to a vector whose all entries have equal magnitude. Using the spectral and combinatorial properties of XXX, we derive necessary conditions for local εεε-uniform mixing to occur in XXX. This includes an inequality involving all entries of each eigenvector of MMM, as well as an upper bound on the degree of vertex uuu when MMM is the Laplacian or signless Laplacian matrix. We use these necessary conditions to rule out local εεε-uniform mixing in numerous classes of graphs, most of which are non-regular. We also show that almost all planar graphs (resp., trees) contain a vertex that does not admit local εεε-uniform mixing for any assignment of edge weights. Furthermore, we prove if XXX has nnn vertices and admits local εεε-uniform mixing at a vertex contained in a subgraph with a twin, then the number of vertices of this twin subgraph must be at least n\sqrt{n}n​. In particular, we establish that a graph on n≥5n\geq 5n≥5 vertices does not admit local εεε-uniform mixing at a vertex with a twin.