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

Local εεε-uniform mixing in continuous quantum walks

Hermie Monterde

Published Mar 21, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2603.20977

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

Uniform Mixing and Association Schemes

Chris D. Godsil, Natalie Mullin, Aidan Roy

We consider continuous-time quantum walks on distance-regular graphs. Using results about the existence of complex Hadamard matrices in association schemes, we determine which of these graphs have quantum walks that admit uniform mixing.First we apply a result due to Chan to show that the only strongly regular graphs that admit instantaneous uniform mixing are the Paley graph of order nine and certain graphs corresponding to regular symmetric Hadamard matrices with constant diagonal. Next we prove that if uniform mixing occurs on a bipartite graph $X$ with $n$ vertices, then $n$ is divisible by four. We also prove that if $X$ is bipartite and regular, then $n$ is the sum of two integer squares. Our work on bipartite graphs implies that uniform mixing does not occur on $C_{2m}$ for $m \geq 3$. Using a result of Haagerup, we show that uniform mixing does not occur on $C_p$ for any prime $p$ such that $p \geq 5$. In contrast to this result, we see that $\epsilon$-uniform mixing occurs on $C_p$ for all primes $p$.

arXiv:1301.5889•The Electronic Journal of Combinatorics•Aug 11, 2017•17 citations

Discrete quantum walks with marked vertices and their average vertex mixing matrices

Amulya Mohan, Hanmeng Zhan

We study the discrete quantum walk on a regular graph X that assigns negative identity coins to marked vertices S and Grover coins to the unmarked ones. We find combinatorial bases for the eigenspaces of the transition matrix, and derive a formula for the average vertex mixing matrix M ˆ . We then find bounds for entries in M ˆ , and study when these bounds are tight. In particular, the average probabilities between marked vertices are lower bounded by a matrix determined by the induced subgraph X [ S ] , the vertex-deleted subgraph ﹨ X ﹨ S , and the edge deleted subgraph X − E ( S ) . We show this bound is achieved if and only if the marked vertices have walk-equitable neighborhoods in the vertex-deleted subgraph. Finally, for quantum walks attaining this bound, we determine when M ˆ [ S , S ] is symmetric, positive semidefinite or uniform.

arXiv:2411.16676•Linear Algebra and its Applications•Aug 21, 2025•0 citations

Universal Mixing of Quantum Walk on Graphs

William Carlson, Allison For, Elizabeth Marie Harris +3 more

We study the set of probability distributions visited by a continuous-time quantum walk on graphs. An edge-weighted graph $G$ is {\em universal mixing} if the instantaneous or average probability distribution of the quantum walk on $G$ ranges over all probability distributions on the vertices as the weights are varied over non-negative reals. The graph is {\em uniform} mixing if it visits the uniform distribution. Our results include the following: 1) All weighted complete multipartite graphs are instantaneous universal mixing. This is in contrast to the fact that no {\em unweighted} complete multipartite graphs are uniform mixing (except for the four-cycle $K_{2,2}$). 2) For all $n \ge 1$, the weighted claw $K_{1,n}$ is a minimally connected instantaneous universal mixing graph. In fact, as a corollary, the unweighted $K_{1,n}$ is instantaneous uniform mixing. This adds a new family of uniform mixing graphs to a list that so far contains only the hypercubes. 3) Any weighted graph is average almost-uniform mixing unless its spectral type is sublinear in the size of the graph. This provides a nearly tight characterization for average uniform mixing on circulant graphs. 4) No weighted graphs are average universal mixing. This shows that weights do not help to achieve average universal mixing, unlike the instantaneous case. Our proofs exploit the spectra of the underlying weighted graphs and path collapsing arguments.

arXiv:quant-ph/0608044•Quantum Information and Computation•Nov 1, 2007•19 citations

Moment Methods for Uniform Average Mixing on Strongly Regular Graphs

Musung Kang

We study continuous-time quantum walks on connected strongly regular graphs that are not complete, observed at a random time drawn from a freely chosen probability law. Uniform average mixing (UAM) asks for a law under which every averaged transition probability equals $1/n$, where $n$ is the number of vertices. On a strongly regular graph this is equivalent to two affine constraints on three cosine moments. We construct a bounded, compactly supported time density for every strongly regular graph with nonintegral eigenvalues. For integral spectra we give an exact finite Toeplitz criterion and its Hankel form. Every averaged mixing matrix of such a graph is realized by at most two observation times. Three elementary inequalities on the moment line, which also give a short proof of Chan's classification of complex Hadamard matrices in the Bose-Mesner algebra, lead to a determination of all strongly regular graphs that admit UAM. Apart from the conference graphs of nonsquare order and the graphs with instantaneous uniform mixing, these are the members of two infinite families of parameter sets and their complements, and for them we give explicit laws with two observation times. The Petersen graph and its complement are the smallest members. A strongly regular graph with UAM admits a bounded time density exactly when it has no instantaneous uniform mixing. We also correct the classification of instantaneous uniform mixing on strongly regular graphs by Godsil, Mullin and Roy. Its sign condition excludes the halved $5$-cube, which mixes uniformly at time $π/4$. With the order $4θ^2$ read literally, its parity condition also excludes the Clebsch graph and includes the parameters $(36,14,4,6)$, for which no time law gives uniform average mixing.

quant-pharXiv:2610.10017•Oct 8, 2026•0 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
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.
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.
We consider continuous-time quantum walks on distance-regular graphs. Using results about the existence of complex Hadamard matrices in association schemes, we determine which of these graphs have quantum walks that admit uniform mixing.First we apply a result due to Chan to show that the only strongly regular graphs that admit instantaneous uniform mixing are the Paley graph of order nine and certain graphs corresponding to regular symmetric Hadamard matrices with constant diagonal. Next we prove that if uniform mixing occurs on a bipartite graph XXX with nnn vertices, then nnn is divisible by four. We also prove that if XXX is bipartite and regular, then nnn is the sum of two integer squares. Our work on bipartite graphs implies that uniform mixing does not occur on C2mC_{2m}C2m​ for m≥3m \geq 3m≥3. Using a result of Haagerup, we show that uniform mixing does not occur on CpC_pCp​ for any prime ppp such that p≥5p \geq 5p≥5. In contrast to this result, we see that ϵ\epsilonϵ-uniform mixing occurs on CpC_pCp​ for all primes ppp.
We study the discrete quantum walk on a regular graph X that assigns negative identity coins to marked vertices S and Grover coins to the unmarked ones. We find combinatorial bases for the eigenspaces of the transition matrix, and derive a formula for the average vertex mixing matrix M ˆ . We then find bounds for entries in M ˆ , and study when these bounds are tight. In particular, the average probabilities between marked vertices are lower bounded by a matrix determined by the induced subgraph X [ S ] , the vertex-deleted subgraph ﹨ X ﹨ S , and the edge deleted subgraph X − E ( S ) . We show this bound is achieved if and only if the marked vertices have walk-equitable neighborhoods in the vertex-deleted subgraph. Finally, for quantum walks attaining this bound, we determine when M ˆ [ S , S ] is symmetric, positive semidefinite or uniform.
We study the set of probability distributions visited by a continuous-time quantum walk on graphs. An edge-weighted graph GGG is {\em universal mixing} if the instantaneous or average probability distribution of the quantum walk on GGG ranges over all probability distributions on the vertices as the weights are varied over non-negative reals. The graph is {\em uniform} mixing if it visits the uniform distribution. Our results include the following: 1) All weighted complete multipartite graphs are instantaneous universal mixing. This is in contrast to the fact that no {\em unweighted} complete multipartite graphs are uniform mixing (except for the four-cycle K2,2K_{2,2}K2,2​). 2) For all n≥1n \ge 1n≥1, the weighted claw K1,nK_{1,n}K1,n​ is a minimally connected instantaneous universal mixing graph. In fact, as a corollary, the unweighted K1,nK_{1,n}K1,n​ is instantaneous uniform mixing. This adds a new family of uniform mixing graphs to a list that so far contains only the hypercubes. 3) Any weighted graph is average almost-uniform mixing unless its spectral type is sublinear in the size of the graph. This provides a nearly tight characterization for average uniform mixing on circulant graphs. 4) No weighted graphs are average universal mixing. This shows that weights do not help to achieve average universal mixing, unlike the instantaneous case. Our proofs exploit the spectra of the underlying weighted graphs and path collapsing arguments.
We study continuous-time quantum walks on connected strongly regular graphs that are not complete, observed at a random time drawn from a freely chosen probability law. Uniform average mixing (UAM) asks for a law under which every averaged transition probability equals 1/n1/n1/n, where nnn is the number of vertices. On a strongly regular graph this is equivalent to two affine constraints on three cosine moments. We construct a bounded, compactly supported time density for every strongly regular graph with nonintegral eigenvalues. For integral spectra we give an exact finite Toeplitz criterion and its Hankel form. Every averaged mixing matrix of such a graph is realized by at most two observation times. Three elementary inequalities on the moment line, which also give a short proof of Chan's classification of complex Hadamard matrices in the Bose-Mesner algebra, lead to a determination of all strongly regular graphs that admit UAM. Apart from the conference graphs of nonsquare order and the graphs with instantaneous uniform mixing, these are the members of two infinite families of parameter sets and their complements, and for them we give explicit laws with two observation times. The Petersen graph and its complement are the smallest members. A strongly regular graph with UAM admits a bounded time density exactly when it has no instantaneous uniform mixing. We also correct the classification of instantaneous uniform mixing on strongly regular graphs by Godsil, Mullin and Roy. Its sign condition excludes the halved 555-cube, which mixes uniformly at time π/4π/4π/4. With the order 4θ24θ^24θ2 read literally, its parity condition also excludes the Clebsch graph and includes the parameters (36,14,4,6)(36,14,4,6)(36,14,4,6), for which no time law gives uniform average mixing.
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.