Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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 but there is no reason to believe it could be anything better than a toy due to the fast decoherence times.
Quantum statistics are also recreated in 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. "
