Take the 2-minute tour ×

Can someone explain to me what real world applications could potentially benefit from the study of quantum random walks?

I have researched a fair amount on how quantum walks operate and their properties but I would like to know the end goal of studying them at a deep level? Is it simply for the sake of it in terms of mathematics or computer science, or are there actual real-world applications that can benefit from this research?

share|improve this question
I answered and only after saw that you simultaneously cross-posted to physics.SE. This is unacceptable behavior and against site policy. I will have to close this question, or you need to delete the physics counter-part. –  Artem Kaznatcheev Mar 11 '14 at 13:11
Perhaps you can explain more what you mean by real-world application. Do classical random walks have "real-world application"? Does Shor's algorithm have "real-world application"? –  Robin Kothari Mar 13 '14 at 1:03

1 Answer 1

With the exception of cryptography applications like Shor's algorithm and quantum key distribution, I think engineering 'killer-apps' are not the norm for quantum computing, and nobody expects them to be. As such, quantum walks are a natural generalization of random walks and thus worth studying in their own right. However, to avoid side-stepping any longer, I can give you some motivation and past successes.

First, just like with classical random walks, we can use quantum random walks in the design of algorithms. This can give us complexity seperations in the quantum query model by looking at glued trees (two binary trees attached leaf-to-leaf via a random permutation); there is no classical randomized algorithm (walk or otherwise) to get from one root to the other in a polynomial number of queries, but the quantum walk does it in polynomial number of queries:

Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003). Exponential algorithmic speedup by a quantum walk. In SToC (pp. 59-68). ACM.

Of course, this relies on this problem being a partial function, since for total-functions we know that exponential separations are not possible, and expect quadratic separation to be the best generally achievable result for quantum query complexity of total-functions. However, if you have a good classical Markov-chain based algorithm then we know that in many cases, the quantum version will have a quadratically faster hitting time, saturating the expected speed up:

Szegedy, M. (2004). Quantum speed-up of Markov chain based algorithms. In FoCS (pp. 32-41). IEEE.

Quantum walk approaches also resulted in optimal query algorithms for less "artificial" problems like element distinctness, where it is the best known algorithm:

Ambainis, A. (2007). Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1), 210-239.

In general, quantum walks are very powerful, and could also be used as models of universal computation:

Childs, A. M. (2009). Universal computation by quantum walk. Physical Review Letters, 102(18), 180501.


If you want to take your applications outside of theoretical computer science and into the real-world of natural sciences, then you can also use quantum random walks just like classical ones: to model and understand certain natural processes. The paradigmatic example of this is for modeling photosynthesis:



In the above work it was shown (roughly) that after a photon hits the chlorophyll, it is transformed into an exciton which does a quantum random walk on the chlorophyll complex until it finds a binding site where it can share its energy to turn an ADP into ATP. A quantum random walk is required by nature, because the lifetime of the exciton is not sufficient for a classical random walk to have sufficient energy transfer. We could get speculative and combine the previous two observations to suggest a nature-inspired model of computation but there is no reason to believe it could be anything better than a toy due to the fast decoherence times.

share|improve this answer

Your Answer


