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
C2m for
m≥3. Using a result of Haagerup, we show that uniform mixing does not occur on
Cp for any prime
p such that
p≥5. In contrast to this result, we see that
ϵ-uniform mixing occurs on
Cp for all primes
p.
Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that the continuous-time quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous exactly uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs of the symmetric group lack this mixing property as well.
Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that a continuous quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs lack this mixing property as well.
In the past few decades, quantum algorithms have become a popular research area of both mathematicians and engineers. Among them, uniform mixing provides a uniform probability distribution of quantum information over time which attracts a special attention. However, there are only a few known examples of graphs which admit uniform mixing. In this paper, a characterization of abelian Cayley graphs having uniform mixing is presented. Some concrete constructions of such graphs are provided. Specifically, for cubelike graphs, it is shown that the Cayley graph
Cay(F22k;S) has uniform mixing if the characteristic function of
S is bent. Moreover, a difference-balanced property of the eigenvalues of an integral abelian Cayley graph having uniform mixing is established. Some nonexistence results of uniform mixing on abelian Cayley graphs are presented also. Notably, for a linear abelian Cayley graph
Γ over
Znr, it is proved that uniform mixing occurs on this graph only if
n=2,3,4 which partially confirms a long-standing conjecture. Finally, with some restrictions on the connection set, we show that if a cyclic group
G whose order is divisible by an odd prime such that
Cay(G,S) has uniform mixing at some time
t being a rational multiple of
π, then the graph should be integral. An interesting reduction method on the circulant Cayley graphs having uniform mixing has been established. Using this method, we can answer some related open questions. For example, we can show that the only two cycles having uniform mixing are
C3 and
C4.
We study continuous-time quantum walks on cycles. We prove two complementary results. Firstly, the cycle
C9 does not admit uniform mixing at any time. Using the similar idea and Dickson polynomials, we prove that
C15 does not admit uniform mixing at any time neither. Secondly, for every prime
p, we show that the cycle
Cp2 admits
ε-uniform mixing.