next up previous
Next: Numerical experiments Up: A remark on quantum Previous: Spectral properties and the

Quantum dynamics versus random walks

Assume L is the generator of a random walk on a graph (V,E) where V is the set of vertices and E is the set of edges. The hopping probabilities tex2html_wrap_inline868 to the vertices so that tex2html_wrap_inline870 define the random walk. For example, if every edge has d neighbours and tex2html_wrap_inline874 for every vertex (w,v), we get a symmetric random walk on a regular graph. The operator tex2html_wrap_inline878 is selfadjoint and has norm 1. Let tex2html_wrap_inline882 be a wave which is localized initially at a vertex v. The quantum evolution tex2html_wrap_inline886 should be compared with the random walk tex2html_wrap_inline888 : while tex2html_wrap_inline890 is the probability that the walker starting at the vertex v returns to v in n steps, tex2html_wrap_inline898 is the probability that the wave tex2html_wrap_inline900 returns back after n steps of the quantum evolution. Opposite to the irreversible random walk, the discrete time quantum evolution is invertible in the sense that the pair tex2html_wrap_inline904 determines tex2html_wrap_inline906 . The Fourier coefficients tex2html_wrap_inline578 of tex2html_wrap_inline770 are easy to compute and determine the measures tex2html_wrap_inline912 of tex2html_wrap_inline678 with respect to L. In many examples of regular infinite graphs, one does not know the spectral type. Aperiodic graphs defined by aperiodic tilings of tex2html_wrap_inline918 (see [18, 17]) are examples, where the spectral type is unknown. The spectrum of a graph can be be pure point like in the case of a finite graph or certain self-similar graphs, it can be absolutely continuous like for tex2html_wrap_inline920 or for Cayley graphs of infinite Abelian discrete groups, it can also be singular continuous as has been pointed out recently in [26].

In order to relate the return probability of the random walk with the Fourier coefficients, we consider a one parameter family of operators tex2html_wrap_inline922 . Denote by tex2html_wrap_inline924 the Fourier coefficients of the spectral measure on the circle with respect to the operator tex2html_wrap_inline926 .





A measure tex2html_wrap_inline990 is called uniformly tex2html_wrap_inline606 -continuous if tex2html_wrap_inline994 for all intervals [a,b).



next up previous
Next: Numerical experiments Up: A remark on quantum Previous: Spectral properties and the

Oliver Knill
Tue Aug 18, 1998