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

Average mixing of continuous quantum walks

Chris D. Godsil

Published Mar 14, 2011• 5 citations
arXivHTMLPDF

Abstract

If $X$ is a graph with adjacency matrix $A$, then we define $H(t)$ to be the operator $\exp(itA)$. The Schur (or entrywise) product $H(t)\circ H(-t)$ is a doubly stochastic matrix and, because of work related to quantum computing, we are concerned the \textsl{average mixing matrix}. This can be defined as the limit of $C^{-1} \int_0^C H(t)\circ H(-t)\dt$ as $C\to\infty$. We establish some of the basic properties of this matrix, showing that it is positive semidefinite and that its entries are always rational. We find that for paths and cycles this matrix takes on a surprisingly simple form, thus for the path it is a linear combination of $I$, $J$ (the all-ones matrix), and a permutation matrix.

DOI
10.48550/arxiv.1103.2578

Related papers

A New Perspective on the Average Mixing Matrix

Gabriel Coutinho, Chris D. Godsil, Krystal Guo +1 more

We consider the continuous-time quantum walk defined on the adjacency matrix of a graph. At each instant, the walk defines a mixing matrix which is doubly-stochastic. The average of the mixing matrices contains relevant information about the quantum walk and about the graph. We show that it is the matrix of transformation of the orthogonal projection onto the commutant algebra of the adjacency matrix, restricted to diagonal matrices. Using this formulation of the average mixing matrix, we find connections between its rank and automorphisms of the graph.

arXiv:1709.03591•Sep 11, 2017•1 citation

Diagonal entries of the average mixing matrix

Chris D. Godsil, Krystal Guo, Mariia Sobchuk

We study the diagonal entries of the average mixing matrix of continuous quantum walks. The average mixing matrix is a graph invariant; it is the sum of the Schur squares of spectral idempotents of the Hamiltonian. It is non-negative, doubly stochastic and positive semi-definite. We investigate the diagonal entries of this matrix. We study the graphs for which the trace of the average mixing matrix is maximum or minimum and we classify those which are maximum. We give two constructions of graphs whose average mixing matrices have constant diagonal.

arXiv:1910.02039•Oct 4, 2019•1 citation

A New Perspective on the Average Mixing Matrix

Gabriel Coutinho, Chris D. Godsil, Krystal Guo +1 more

We consider the continuous-time quantum walk defined on the adjacency matrix of a graph. At each instant, the walk defines a mixing matrix which is doubly-stochastic. The average of the mixing matrices contains relevant information about the quantum walk and about the graph. We show that it is the matrix of transformation of the orthogonal projection onto the commutant algebra of the adjacency matrix, restricted to diagonal matrices. Using this formulation of the average mixing matrix, we find connections between its rank and automorphisms of the graph.

The Electronic Journal of Combinatorics•Oct 19, 2018•5 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

Mixing of quantum walk on circulant bunkbeds

P. Lo, Siddharth Rajaram, Diana R. Schepens +3 more

This paper gives new observations on the mixing dynamics of a continuous-time quantum walk on circulants and their bunkbeds. These bunkbeds are defined through two standard graph operators: the join G + H and the Cartesian product G \cprod H of graphs G and H. Our results include the following: (i) The quantum walk is average uniform mixing on circulants with bounded eigenvalue multiplicity; this extends a known fact about the cycles C_{n}. (ii) Explicit analysis of the probability distribution of the quantum walk on the join of circulants; this explains why complete multipartite graphs are not average uniform mixing, using the fact K_{n} = K_{1} + K_{n-1} and K_{n,\ldots,n} = \overline{K}_{n} + \ldots + \overline{K}_{n}. (iii) The quantum walk on the Cartesian product of a $m$-vertex path P_{m} and a circulant G, namely, P_{m} \cprod G, is average uniform mixing if G is; this highlights a difference between circulants and the hypercubes Q_{n} = P_{2} \cprod Q_{n-1}. Our proofs employ purely elementary arguments based on the spectra of the graphs.

arXiv:quant-ph/0509059•Quantum Information and Computation•Jul 1, 2006•13 citations

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
If XXX is a graph with adjacency matrix AAA, then we define H(t)H(t)H(t) to be the operator exp⁡(itA)\exp(itA)exp(itA). The Schur (or entrywise) product H(t)∘H(−t)H(t)\circ H(-t)H(t)∘H(−t) is a doubly stochastic matrix and, because of work related to quantum computing, we are concerned the \textsl{average mixing matrix}. This can be defined as the limit of C−1∫0CH(t)∘H(−t)\dtC^{-1} \int_0^C H(t)\circ H(-t)\dtC−1∫0C​H(t)∘H(−t)\dt as C→∞C\to\inftyC→∞. We establish some of the basic properties of this matrix, showing that it is positive semidefinite and that its entries are always rational. We find that for paths and cycles this matrix takes on a surprisingly simple form, thus for the path it is a linear combination of III, JJJ (the all-ones matrix), and a permutation matrix.
We consider the continuous-time quantum walk defined on the adjacency matrix of a graph. At each instant, the walk defines a mixing matrix which is doubly-stochastic. The average of the mixing matrices contains relevant information about the quantum walk and about the graph. We show that it is the matrix of transformation of the orthogonal projection onto the commutant algebra of the adjacency matrix, restricted to diagonal matrices. Using this formulation of the average mixing matrix, we find connections between its rank and automorphisms of the graph.
We study the diagonal entries of the average mixing matrix of continuous quantum walks. The average mixing matrix is a graph invariant; it is the sum of the Schur squares of spectral idempotents of the Hamiltonian. It is non-negative, doubly stochastic and positive semi-definite. We investigate the diagonal entries of this matrix. We study the graphs for which the trace of the average mixing matrix is maximum or minimum and we classify those which are maximum. We give two constructions of graphs whose average mixing matrices have constant diagonal.
We consider the continuous-time quantum walk defined on the adjacency matrix of a graph. At each instant, the walk defines a mixing matrix which is doubly-stochastic. The average of the mixing matrices contains relevant information about the quantum walk and about the graph. We show that it is the matrix of transformation of the orthogonal projection onto the commutant algebra of the adjacency matrix, restricted to diagonal matrices. Using this formulation of the average mixing matrix, we find connections between its rank and automorphisms of the graph.
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.
This paper gives new observations on the mixing dynamics of a continuous-time quantum walk on circulants and their bunkbeds. These bunkbeds are defined through two standard graph operators: the join G + H and the Cartesian product G \cprod H of graphs G and H. Our results include the following: (i) The quantum walk is average uniform mixing on circulants with bounded eigenvalue multiplicity; this extends a known fact about the cycles C_{n}. (ii) Explicit analysis of the probability distribution of the quantum walk on the join of circulants; this explains why complete multipartite graphs are not average uniform mixing, using the fact K_{n} = K_{1} + K_{n-1} and K_{n,\ldots,n} = \overline{K}_{n} + \ldots + \overline{K}_{n}. (iii) The quantum walk on the Cartesian product of a mmm-vertex path P_{m} and a circulant G, namely, P_{m} \cprod G, is average uniform mixing if G is; this highlights a difference between circulants and the hypercubes Q_{n} = P_{2} \cprod Q_{n-1}. Our proofs employ purely elementary arguments based on the spectra of the graphs.
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.