Transitioning from quantum to classical random walks on the line

Question

Quick version

Are there models of decoherence for the quantum walk on the line such that we can tune the walk to spread as $\Theta(t^k)$ for any $1/2 \leq k \leq 1$?

---

Motivation

Classical random walks are useful in algorithm design, and quantum random walks have proven useful for making a number of cool quantum algorithm (sometimes with provable exponential speed-ups). Thus, it is important to understand the difference between quantum and classical random walks. Sometimes, the easiest way to do this is to consider toy models, such as walks on the line.

There is a physics motivation as well: it is interesting to know how quantum mechanics scales to classical mechanics. But this is not very relevant to cstheory.

My personal motivation is completely orthogonal: I am trying to match some experimental data with a model that transitions smoothly from quantum to classical and is relatively intuitive.

Background

When considering quantum and classical walks on the integer line, a key difference is that the standard deviation (of the position distribution) of the quantum walk goes as $\Theta(t)$ and classical ones as $\Theta({t^{1/2}})$ where $t$ is the number of steps for a discrete model, or time in a continuous model. Note that this is not restricted to the line, and for many graphs you will see a similar quadratic relationship between the quantum and classical mixing time, I consider the restricted case of the line since I think it is easier to analyze.

As we introduce decoherence to a quantum walk (either through measurement or noise) the walk starts to behave more classically. In fact, for most measurements, we just end up with a classical walk that spreads as $\Theta(t^{1/2})$ if viewed from the right timescale. For other forms of decoherence (such as dephasing the coin, or introducing imperfections in the line) there is usually a sharp threshold below which the walk behaves quantumly (spread as $\Theta(t)$) and above which the walk starts to be classical (spread as $\Theta(t^{1/2})$). In fact, this scaling has even been suggested as the definition of a quantum walk.

---

Long version of question

Are there models of decoherence for a random walk on the line, such that as we vary the amount of decoherence we can achieve a standard deviation in position that scales as $\Theta(t^k)$ for any $1/2 \leq k \leq 1$? Alternatively for other graphs with a gap in mixing or hitting time, is there forms of decoherence so that we can have the mixing/hitting/standard deviation that goes as $f(t)$ for any $f \in \Sigma(g(t))$ and $f \in O(h(t))$ where $g(t)$ is the classical mixing/hitting/STD and $h(t)$ is the pure quantum. If this is not possible then is there a deeper reason why we see this sort of one-or-the-other behavior?

Answer 1

Great question. Actually, the same question popped up in something I was working on a few months ago (arXiv:1011.1217). It seems that any natural kind of decoherence leads to behaviour that looks initially balistic, but which becomes diffusive as time increases, so you are transitionioning between a $t$ regime and a $t^{\frac{1}{2}}$ regime. See figure 2 in the above paper for an example of this. This seems to be the natural behaviour as your state gradually loses coherence.

This would seem to suggest that the variance only ever scales as $t$ or $t^2$, and hence the walk spreads as $t^{\frac{1}{2}}$ or $t$.

However, exactly the same thing happens in quantum metrology when noise is introduced, but can be overcome to yield an intermediate scaling (see for example J. A. Jones et al, Science, 324, 5931 (2009), arXiv:1103.1219, arXiv:1101.2561, etc.). One way this can be achieved is by making intermediate measurements.

Imagine you measure the position of the walker after every period of time $T$ collapsing the wavefunction, and allow free evolution in between. Now, imagine we want to evolve the system for total time $t=nT$. Then the variance in the position of the walker after this time will be $\mbox{Var}(x(nT)) = \sum_{i = 1}^n \mbox{Var}(x(T)) = n \mbox{Var}(x(T))$. In the absence of other decoherence we know the walker moves ballistically, and hence $\mbox{Var}(x(T)) = T^2$, and so the $\mbox{Var}(x(t)) = n T^2$. However, as $t=nT$, we can take $n\propto t^k$ and $T\propto t^{1-k}$. Thus $\mbox{Var}(x(t)) = t^{2-k}$. This way you can achieve any intermediate scaling, by chosing the measurement interval appropriately.