I started typing up a question on transitioning from quantum to classical random walks on the line, with the punchline being along the lines of:

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

The question is tangentially related to cstheory because classical random walks are useful in algorithm design, and quantum random walks have proven useful for making a number of cool algorithms. 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.

Further, I think there are enough quantum folks at cstheory that I might get a very good answer.

On the other hand, the question is clearly physics-y and would be of little interest to non-quantum cstheory members. The question would be more at home at Theoretical Physics.SE but unfortunately the site has not made it to beta, yet. I could try physics.SE but a look the question list suggests that that site lost its research focus, and this is a research level question. Also, I check cstheory all the time and enjoy the community, so I prefer to ask questions here.

Should I try asking this question and removing it if the community doesn't approve? Or is this question so clearly off-topic that by asking it I would be setting a bad example?


After 3 proceed comments, I posted the question:

Transitioning from quantum to classical random walks on the line

If you think there is a way I can improve the question or make it clearer/better motivated please suggest it here or in the comments of the question.


3 Answers 3


I think that it is within the scope, just like questions in graph theory that are more mathematics than computer science but are more or less motivated by TCS. However, unlike graph theory, we cannot assume that everyone on this website knows how quantum walks are related to TCS. Therefore I think that a brief explanation of why they are related to TCS (or a link to an explanation) is desirable.

But take my words on this with a grain of salt, because I work in quantum computing and I may have a partial view about it.

  • $\begingroup$ I am most worried about the 'decoherence' part. I've only ever seen it in the more physics-y papers and don't have a good reference on how decoherence would be important to TCS. Any suggestions? $\endgroup$ Aug 5, 2011 at 1:30

well, I asked a question on quantum walks before, and Joe Fitzsimons gave me a lot of help on it.

In my opinion, quantum walks is a very important paradigm for designing quantum algorithms (not only quantum query algotihms), and is definitely in scope. But, like Tsuyoshi, I also have a bias here.

  • $\begingroup$ regarding your question, yes there are models of quantum walks that spread the way you want, and you don't need decoherence at all! $\endgroup$ Aug 5, 2011 at 0:17
  • $\begingroup$ "quantum walks is a very important paradigm for designing quantum algorithms (not only quantum query algotihms)" <<< haha, I guess I am the quantum query guy! Strangely enough, unlike most of my other questions, this one is not actually motivated by query complexity. Decoherence is really central to the question (so designing a graph in order to achieve the hitting time is not exactly what I am looking for), but that is not made clear in just the punchline. But I guess I should really ask the question before receiving a question on meta for it. $\endgroup$ Aug 5, 2011 at 1:27
  • $\begingroup$ also, thanks for the precedent reference. I actually haven't read that question before. $\endgroup$ Aug 5, 2011 at 1:33

I would strongly encourage asking this question. I think quantum random walks are quite an interesting topic (and actually have a bit of application in "classical" embedding theory).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .