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 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.
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.
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 Kn, 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.
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 Kn is the laziest connected graph on n vertices. Using our machinery, we show that the star Sn is the second laziest connected graph on n vertices (and hence the laziest tree on n vertices), the complete multipartite graph Kn−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.
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 K2,2). 2) For all n≥1, the weighted claw K1,n is a minimally connected instantaneous universal mixing graph. In fact, as a corollary, the unweighted 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.