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.
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.
A weighted graph G with countable vertex set is bounded if there is an upper bound on the maximum of the sum of absolute values of all edge weights incident to a vertex in G. In this paper, we prove a fundamental result on equitable partitions of bounded weighted graphs with twin subgraphs and use this fact to construct finite and bounded infinite graphs with pair and plus state transfer with the adjacency matrix as a Hamiltonian. We show that for each k≥3, (i) there are infinitely many connected unweighted graphs with maximum degree k admitting pair state transfer at τ∈{2π,2π}, and (ii) there are infinitely many signed graphs with exactly one negative edge weight and whose underlying unweighted graphs have maximum degree k admitting plus state transfer at τ∈{2π,2π}. Parallel results are proven for perfect state transfer between a plus state and a pair state, and for the existence of sedentary pair and plus states. We further prove that almost all connected unweighted finite planar graphs admit pair state transfer at τ∈{2π,2π}, and almost all connected unweighted finite planar graphs can be assigned a single negative edge weight resulting in plus state transfer, or perfect state transfer between a plus state and a pair state, at τ∈{2π,2π}. Analogous results are shown to hold for unweighted finite trees. Using blow-up graphs, Cayley graphs and graphs with tails, we construct new infinite families of (finite and infinite) unweighted graphs and signed graphs admitting pair or plus state transfer.
A continuous-time quantum walk (CTQW) is sedentary if the return probability in the starting vertex is close to one at all times. Recent results imply that, when starting from a maximal degree vertex, the CTQW dynamics generated by the Laplacian and adjacency matrices are typically sedentary. In this paper, we show that the addition of appropriate complex phases to the edges of the graph, defining a chiral CTQW, can cure sedentarity and lead to swift chiral quantum walks of the adjacency type, which bring the return probability to zero in the shortest time possible. We also provide a no-go theorem for swift chiral CTQWs of the Laplacian type. Our results provide one of the first, general characterization of tasks that can and cannot be achieved with chiral CTQWs.
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.
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.
For a simple graph Γ, a (bipartite)tree-line graph and a tree-graph of Γ can be defined. With a (bipartite)tree-line graph constructed by the function (b)ℓ, we study the continuous quantum walk on (b)ℓnΓ. An equitable partition of a bipartite tree-line graph is obtained by its corresponding derived tree graph. This paper also examines quantum walks on derived graphs, whose vertices represent their basis state.
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.