<p>With the exception of cryptography applications like <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="noreferrer">Shor's algorithm</a> and <a href="https://en.wikipedia.org/wiki/Quantum_key_distribution" rel="noreferrer">quantum key distribution</a>, 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.</p>
<p>First, just like with classical random walks, we can use quantum random walks in the <strong>design of algorithms</strong>. This can give us <strong>complexity seperations</strong> in the <a href="http://egtheory.wordpress.com/2013/12/09/quantum-query-complexity/" rel="noreferrer">quantum query model</a> 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:</p>
<blockquote>
<p>Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., &amp; Spielman, D. A. (2003). Exponential algorithmic speedup by a quantum walk. In <em>SToC</em> (pp. 59-68). ACM.</p>
</blockquote>
<p>Of course, this relies on this problem being a partial function, since <a href="https://cstheory.stackexchange.com/q/6077/1037">for total-functions we know that exponential separations are not possible, and expect quadratic separation to be the best generally achievable result</a> 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:</p>
<blockquote>
<p>Szegedy, M. (2004). Quantum speed-up of Markov chain based algorithms. In <em>FoCS</em> (pp. 32-41). IEEE.</p>
</blockquote>
<p>Quantum walk approaches also resulted in optimal query algorithms for less &quot;artificial&quot; problems like element distinctness, where it is the best known algorithm:</p>
<blockquote>
<p>Ambainis, A. (2007). Quantum walk algorithm for element distinctness. <em>SIAM Journal on Computing</em>, 37(1), 210-239.</p>
</blockquote>
<p>In general, quantum walks are very powerful, and could also be used as <strong>models of universal computation</strong>:</p>
<blockquote>
<p>Childs, A. M. (2009). Universal computation by quantum walk. <em>Physical Review Letters</em>, 102(18), 180501.</p>
<p>Childs, A. M., Gosset, D., &amp; Webb, Z. (2013). Universal Computation by Multiparticle Quantum Walk. <em>Science</em>, 339(6121), 791-794.</p>
</blockquote>
<p>If you want to take your applications outside of theoretical computer science and into the <em>real-world</em> 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 <strong>modeling photosynthesis</strong>:</p>
<blockquote>
<p>Engel GS, Calhoun TR, Read EL, Ahn TK, Mancal T, Cheng YC et al. (2007). Evidence for wavelike energy transfer through quantum coherence in photosynthetic systems. <em>Nature</em> 446 (7137): 782–6.</p>
<p>Rebentrost, P., Mohseni, M., Kassal, I., Lloyd, S., &amp; Aspuru-Guzik, A. (2009). Environment-assisted quantum transport. <em>New Journal of Physics</em>, 11(3), 033003.</p>
</blockquote>
<p>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 <a href="http://egtheory.wordpress.com/2013/04/08/cell-computer/" rel="noreferrer">suggest a nature-inspired model of computation</a> but there is no reason to believe it could be anything better than a toy due to the fast decoherence times.</p>

CC BY-SA 3.0
2014-03-11T12:58:30.267Z
2014-03-11T13:09:04.780Z
2020-06-17T09:38:08.363Z
Artem Kaznatcheev
<p>Quantum statistics are also recreated in <a href="https://en.wikipedia.org/wiki/Maximal_entropy_random_walk" rel="nofollow noreferrer"><strong>Maximal Entropy Random Walk</strong></a>, which has lots of known applications:</p>

<p>"MERW is used in various fields of science. A direct application is choosing probabilities to <strong>maximize transmission rate through a constrained channel</strong>, analogously to Fibonacci coding. Its properties also made it useful for example in <strong>analysis of complex networks</strong>(1), like <strong>link prediction</strong>[2], <strong>community detection</strong>[3] <strong>and centrality measures</strong>[4]. Also in <strong>image analysis</strong>, for example for <strong>detecting visual saliency regions</strong>[5], <strong>object localization</strong>[6], <strong>tampering detection</strong>[7], or <strong>tractography problem</strong>[8].</p>

<p>Additionally, it recreates some properties of quantum mechanics, suggesting a way to repair the discrepancy between diffusion models and quantum predictions, like Anderson localization[9].</p>

<p>(...)</p>

<p>(1) R. Sinatra, J. Gómez-Gardenes, R. Lambiotte, V. Nicosia, Maximal-entropy random walks in complex networks with limited information, Phys. Rev. E, 2011.</p>

<p>[2] R.H. Li, J.X. Yu, J. Liu, Link Prediction: the Power of Maximal Entropy Random Walk, CIKM '11, 2011.</p>

<p>[3] J. Ochab, Z. Burda, Maximal entropy random walk in community detection, Z. Eur. Phys. J., 2013.</p>

<p>[4] J.C. Delvenne, A.S. Libert, Centrality measures and thermodynamic formalism for complex networks, Phys. Rev. E, 2011.</p>

<p>[5] J.G. Yu, J. Zhao, J. Tian, Y. Tan, Maximal entropy random walk for region-based visual saliency, IEEE Transactions on Cybernetics, 2014.</p>

<p>[6] L. Wang, J. Zhao, X. Hu, J. Lu, Weakly supervised object localization via maximal entropy random walk, ICIP, 2014.</p>

<p>[7] P. Korus, J. Huang, Improved Tampering Localization in Digital Image Forensics Based on Maximal Entropy Random Walk, IEEE Signal Processing Letters, 2016.</p>

<p>[8] V.L. Galinsky, L.R. Frank, Simultaneous multi-scale diffusion estimation and tractography guided by entropy spectrum pathways, IEEE Transactions on Medical Imaging, 2015.</p>

<p>[9] Z. Burda, J. Duda, J. M. Luck, and B. Waclaw, Localization of the Maximal Entropy Random Walk, Phys. Rev. Lett., 2009.
"</p>

CC BY-SA 3.0
2018-02-18T09:59:07.560Z
2018-02-18T09:59:07.560Z
Jarek Duda
<p>Can someone explain to me what real world applications could potentially benefit from the study of quantum random walks?</p>

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

CC BY-SA 3.0
2014-03-11T13:11:54.330Z
I answered and only after saw that you [simultaneously cross-posted](http://physics.stackexchange.com/q/102986) to physics.SE. This is unacceptable behavior and [against site policy](http://meta.cstheory.stackexchange.com/a/2682/1037). I will have to close this question, or you need to delete the physics counter-part.
Artem Kaznatcheev
CC BY-SA 3.0
2014-03-13T01:03:54.943Z
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
<quantum-computing><random-walks><quantum-walk>
Applications of Quantum Walks?
csss
# Applications of Quantum Walks?

(Asked by: username_0 on 2014-03-11)

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?

**Tags:** quantum-computing, random-walks, quantum-walk

> **Comments:**
> **username_1**: I answered and only after saw that you [simultaneously cross-posted](http://physics.stackexchange.com/q/102986) to physics.SE. This is unacceptable behavior and [against site policy](http://meta.cstheory.stackexchange.com/a/2682/1037). I will have to close this question, or you need to delete the physics counter-part.  
> **username_2**: 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"?  

---

## 2 answers

### Answer by username_1 on 2014-03-11. Score: 9

With the exception of cryptography applications like [Shor's algorithm](https://en.wikipedia.org/wiki/Shor%27s_algorithm) and [quantum key distribution](https://en.wikipedia.org/wiki/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](http://egtheory.wordpress.com/2013/12/09/quantum-query-complexity/) 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](https://cstheory.stackexchange.com/q/6077/1037) 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.
>
> Childs, A. M., Gosset, D., & Webb, Z. (2013). Universal Computation by Multiparticle Quantum Walk. *Science*, 339(6121), 791-794.

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**:

> Engel GS, Calhoun TR, Read EL, Ahn TK, Mancal T, Cheng YC et al. (2007). Evidence for wavelike energy transfer through quantum coherence in photosynthetic systems. *Nature* 446 (7137): 782–6.
>
> Rebentrost, P., Mohseni, M., Kassal, I., Lloyd, S., & Aspuru-Guzik, A. (2009). Environment-assisted quantum transport. *New Journal of Physics*, 11(3), 033003.

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](http://egtheory.wordpress.com/2013/04/08/cell-computer/) but there is no reason to believe it could be anything better than a toy due to the fast decoherence times.


---

### Answer by username_3 on 2018-02-18. Score: 1

Quantum statistics are also recreated in [**Maximal Entropy Random Walk**](https://en.wikipedia.org/wiki/Maximal_entropy_random_walk), which has lots of known applications:

"MERW is used in various fields of science. A direct application is choosing probabilities to **maximize transmission rate through a constrained channel**, analogously to Fibonacci coding. Its properties also made it useful for example in **analysis of complex networks**(1), like **link prediction**[2], **community detection**[3] **and centrality measures**[4]. Also in **image analysis**, for example for **detecting visual saliency regions**[5], **object localization**[6], **tampering detection**[7], or **tractography problem**[8].

Additionally, it recreates some properties of quantum mechanics, suggesting a way to repair the discrepancy between diffusion models and quantum predictions, like Anderson localization[9].

(...)

(1) R. Sinatra, J. Gómez-Gardenes, R. Lambiotte, V. Nicosia, Maximal-entropy random walks in complex networks with limited information, Phys. Rev. E, 2011.

[2] R.H. Li, J.X. Yu, J. Liu, Link Prediction: the Power of Maximal Entropy Random Walk, CIKM '11, 2011.

[3] J. Ochab, Z. Burda, Maximal entropy random walk in community detection, Z. Eur. Phys. J., 2013.

[4] J.C. Delvenne, A.S. Libert, Centrality measures and thermodynamic formalism for complex networks, Phys. Rev. E, 2011.

[5] J.G. Yu, J. Zhao, J. Tian, Y. Tan, Maximal entropy random walk for region-based visual saliency, IEEE Transactions on Cybernetics, 2014.

[6] L. Wang, J. Zhao, X. Hu, J. Lu, Weakly supervised object localization via maximal entropy random walk, ICIP, 2014.

[7] P. Korus, J. Huang, Improved Tampering Localization in Digital Image Forensics Based on Maximal Entropy Random Walk, IEEE Signal Processing Letters, 2016.

[8] V.L. Galinsky, L.R. Frank, Simultaneous multi-scale diffusion estimation and tractography guided by entropy spectrum pathways, IEEE Transactions on Medical Imaging, 2015.

[9] Z. Burda, J. Duda, J. M. Luck, and B. Waclaw, Localization of the Maximal Entropy Random Walk, Phys. Rev. Lett., 2009.
"


---

