Proof quantum random walk $\sigma \propto n$? In a classical random walk, the standard deviation $\sigma \propto \sqrt{n}$, while in a quantum random walk it goes as $\sigma \propto n$.
Both discrete time and continuous time quantum random walks have been shown to display the above behaviour.
I can prove the classical case, as it is just related to the variance of the binomial distribution, but how does one prove the relation for the quantum random walk? All the papers that I have read either assume it or derive it numerically.  Is an analytic proof possible?
 A: From the Wikipedia definition of a continuous time "quantum" random walk on a graph, it appears  to be just a fancy name for  the quantum evolution of a tight-binding hamiltonian on the  same graph. For an infinite  linear chain, such evolution is quite straightforward to compute.  The amplitude to be $n$ sites away from the start at time $t$ is given by the Bessel function ${\rm J}_n(2t)$  --- which is is exponentially small until $2t=n$ --- so the pulse is moving out at  speed "2". This is easy to understand intuitively: the energy of a momentum $k$ particle is $2\cos k$, so   the group velocity is $2\sin k$ which has a maximum value of 2. The   leading  edge (and most promiment part)  of the outgoing wave  therefore lies at $n=2t$. The quantum ``particle''  effectively moves ballistically rather than diffusively.
To see all this, observe  that the eigenvectors and eigenvalues of the adjancency matrix for an infinite  linear chain are found from
$$
u_{n+1}+ u_{n-1}= \lambda u_n.
$$ 
We read off  that 
 $u_n= e^{ikn}$ and  $\lambda=2 \cos k$. A complete set of eigenstates is obtained by taking   $k$ lying between $-\pi$ and $+\pi$.  Then if we start with $\psi(n, t=0) = \delta_{n,0}$ the time evolution is 
$$
\psi(n,t) = \frac 1{2\pi} \int_{-\pi}^{\pi} e^{ink- 2it \cos k}\, dk= i^n{\rm J}_n(2t)
$$  where the last step is from the integral definition of the Bessel function of integer order. (I have corrected a factor of two from my earlier version, and  I think have the phase $i^n$ correct, but check!) 
A: First note that the statement is generally true only in the translation-invariant setting. 
For an elementary proof of this in the discrete time setting using Fourier techniques, see the paper by Grimmett et al. in 
https://arxiv.org/abs/quant-ph/0309135
There, the weak convergence of $Q_t/t$ is proved for quantum walks on regular lattices, where $Q_t$ is the time-evolved position operator in the Heisenberg picture.
This statement also accounts for the ambiguity of the standard deviation which does not tell the whole story since it doesnt discriminate between different principal axes of the lattice.
