<p>Great question. Actually, the same question popped up in something I was working on a few months ago (<a href="http://arxiv.org/abs/1011.1217" rel="nofollow">arXiv:1011.1217</a>). 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.</p>

<p>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$.</p>

<p>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), <a href="http://arxiv.org/abs/1103.1219" rel="nofollow">arXiv:1103.1219</a>, <a href="http://arxiv.org/abs/1101.2561" rel="nofollow">arXiv:1101.2561</a>, etc.). One way this can be achieved is by making intermediate measurements.</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-05T15:54:06.390Z
what is 'ballistic' behaviour ?
Suresh Venkat
CC BY-SA 3.0
2011-08-05T16:28:37.487Z
@Suresh: Sorry, slipped into physics nomenclature. It means the variance scales as $t^2$ rather than $t$. It basically means the wave is propagating with constant speed, rather than dispersing.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-07T13:31:25.663Z
the last paragraph seems a little bit unnatural. Although valid if we know that we are going to run our walker for a fixed time, aren't we usually interested in the asymptotics as $t \rightarrow \infty$? For this to work in the limit, it seems we won't be able to define $T$ appropriately. I think with a little care we could define a function $f(n)$ which tells us how long to wait until the $n$-th measurement, and then tweak that to get any scaling, but that also seems very much a hack, since I imagine environments would not naturally implement such a precise measurement scheme.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-07T17:51:45.123Z
@Artem: Yes, I agree it is weird andd unnatural, but there is a reason for it, at least in the metrology context in which it originally appears. The idea is that decoherence would normally impose the $t^\frac{1}{2}$ limit, but if you know how long you want to evolve for, you can slice it up into periodic measurements and do better than the shot noise limit. This answer is just applying those results to a quantum random walk.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-07T18:06:29.020Z
@Artem: For natural evolution you tend to simply have a region where there is ballistic diffusion, with a transition region, slowing to sustained growth at $t^\frac{1}{2}$. It's easy to see how this occurs: for short time scales there is little decoherence, and so the evolution looks quantum. However, if we zoom out enough, breaking the chain into regions and considering the dynamics of hopping between these regions, the evolution eventually looks classical, since coherence isn't sustained long enough to cross such a block, and hence we have a classical random walk.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-05T08:23:54.640Z
2013-11-25T04:16:33.373Z
2013-11-25T04:16:33.373Z
Joe Fitzsimons
<h3>Quick version</h3>
<blockquote>
<p>Are there models of decoherence for the quantum walk on the line such that we can tune the walk to spread as <span class="math-container">$\Theta(t^k)$</span> for any <span class="math-container">$1/2 \leq k \leq 1$</span>?</p>
</blockquote>
<hr />
<h3>Motivation</h3>
<p>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 <a href="http://arxiv.org/abs/quant-ph/0209131" rel="noreferrer">provable exponential speed-ups</a>). 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.</p>
<p>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.</p>
<p>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.</p>
<h3>Background</h3>
<p>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 <span class="math-container">$\Theta(t)$</span> and classical ones as <span class="math-container">$\Theta({t^{1/2}})$</span> where <span class="math-container">$t$</span> 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.</p>
<p>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 <span class="math-container">$\Theta(t^{1/2})$</span> 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 <span class="math-container">$\Theta(t)$</span>) and above which the walk starts to be classical (spread as <span class="math-container">$\Theta(t^{1/2})$</span>). In fact, this scaling has even been suggested as the definition of a quantum walk.</p>
<hr />
<h3>Long version of question</h3>
<p>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 <span class="math-container">$\Theta(t^k)$</span> for any <span class="math-container">$1/2 \leq k \leq 1$</span>? 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 <span class="math-container">$f(t)$</span> for any <span class="math-container">$f \in \Sigma(g(t))$</span> and <span class="math-container">$f \in O(h(t))$</span> where <span class="math-container">$g(t)$</span> is the classical mixing/hitting/STD and <span class="math-container">$h(t)$</span> 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?</p>

CC BY-SA 3.0
2011-08-05T05:39:34.763Z
if you want me to refine something in the question then please point it out. If you are worried about the scope of this question then contribute to the [meta discussion](http://meta.cstheory.stackexchange.com/q/1243/1037).
Artem Kaznatcheev
<quantum-computing><random-walks><quantum-walk>
Transitioning from quantum to classical random walks on the line
Artem Kaznatcheev
# Transitioning from quantum to classical random walks on the line

(Asked by: username_0 on 2011-08-05)

### 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](http://arxiv.org/abs/quant-ph/0209131)). 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?

**Tags:** quantum-computing, random-walks, quantum-walk
> **Comments:**
> **username_0**: if you want me to refine something in the question then please point it out. If you are worried about the scope of this question then contribute to the [meta discussion](http://meta.cstheory.stackexchange.com/q/1243/1037).  

---

## 1 answers

### Answer by username_1 on 2011-08-05. Score: 12 | Accepted answer

Great question. Actually, the same question popped up in something I was working on a few months ago ([arXiv:1011.1217](http://arxiv.org/abs/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](http://arxiv.org/abs/1103.1219), [arXiv:1101.2561](http://arxiv.org/abs/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.

> **Comments:**
> **username_2**: what is 'ballistic' behaviour ?  
> **username_1**: @Suresh: Sorry, slipped into physics nomenclature. It means the variance scales as $t^2$ rather than $t$. It basically means the wave is propagating with constant speed, rather than dispersing.  
> **username_0**: the last paragraph seems a little bit unnatural. Although valid if we know that we are going to run our walker for a fixed time, aren't we usually interested in the asymptotics as $t \rightarrow \infty$? For this to work in the limit, it seems we won't be able to define $T$ appropriately. I think with a little care we could define a function $f(n)$ which tells us how long to wait until the $n$-th measurement, and then tweak that to get any scaling, but that also seems very much a hack, since I imagine environments would not naturally implement such a precise measurement scheme.  
> **username_1**: @Artem: Yes, I agree it is weird andd unnatural, but there is a reason for it, at least in the metrology context in which it originally appears. The idea is that decoherence would normally impose the $t^\frac{1}{2}$ limit, but if you know how long you want to evolve for, you can slice it up into periodic measurements and do better than the shot noise limit. This answer is just applying those results to a quantum random walk.  
> **username_1**: @Artem: For natural evolution you tend to simply have a region where there is ballistic diffusion, with a transition region, slowing to sustained growth at $t^\frac{1}{2}$. It's easy to see how this occurs: for short time scales there is little decoherence, and so the evolution looks quantum. However, if we zoom out enough, breaking the chain into regions and considering the dynamics of hopping between these regions, the evolution eventually looks classical, since coherence isn't sustained long enough to cross such a block, and hence we have a classical random walk.  

---

