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.
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)∘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→∞. 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.
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.
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.