- Physical Review Journals
All JournalsPhysics Magazine

Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 3.0 License. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access

Degree Distribution in Quantum Walks on Complex Networks

Mauro Faccin1,*, Tomi Johnson1,2, Jacob Biamonte1, Sabre Kais3,4, and Piotr Migdał5,1

  • 1Institute for Scientific Interchange, Via Alassio 11/c, 10126 Torino, Italy
  • 2Clarendon Laboratory, University of Oxford, Parks Road, Oxford OX1 3PU, United Kingdom
  • 3Department of Chemistry, Physics, and Birck Nanotechnology Center, Purdue University, West Lafayette, Indiana 47907, USA
  • 4Qatar Environment and Energy Research Institute (QEERI), Doha, Qatar
  • 5ICFO–Institut de Ciències Fotòniques, 08860 Castelldefels (Barcelona), Spain

  • *mauro.faccin@isi.it
PDF

Phys. Rev. X 3, 041007 – Published 24 October, 2013

DOI: https://doi.org/10.1103/PhysRevX.3.041007

Abstract

In this theoretical study, we analyze quantum walks on complex networks, which model network-based processes ranging from quantum computing to biology and even sociology. Specifically, we analytically relate the average long-time probability distribution for the location of a unitary quantum walker to that of a corresponding classical walker. The distribution of the classical walker is proportional to the distribution of degrees, which measures the connectivity of the network nodes and underlies many methods for analyzing classical networks, including website ranking. The quantum distribution becomes exactly equal to the classical distribution when the walk has zero energy, and at higher energies, the difference, the so-called quantumness, is bounded by the energy of the initial state. We give an example for which the quantumness equals a Rényi entropy of the normalized weighted degrees, guiding us to regimes for which the classical degree-dependent result is recovered and others for which quantum effects dominate.

View figure in article

Popular Summary

Imagine a web surfer mindlessly wandering from one page to another by clicking randomly on one of the many hyperlinks on each page they encounter. Where would they end up? This question and the answer to it actually are essential to how Google’s web-search engine decides the relative importance of the world’s webpages. Algorithmically, the world’s webpages are represented by a huge network of nodes (pages) and links (hyperlinks) and the mindless internet surfer by a “random walker.” Now, what happens if the random walker is quantum mechanical instead? This may sound like a question for science fiction, but it is actually part of a recent fundamental drive toward merging the science of complex networks—relevant to many scientific disciplines, including statistical physics, biology, computer science, and social science—with quantum mechanics. In this paper, we make one of the first steps in that drive: to uncover and delineate some of the fundamental connections and differences between classical and quantum networks, by developing and investigating a revealing toy model of quantum random walks on complex networks.

It is well known that for a classical random walker on a complex network, the probability of finding the walker on a node after a long time is proportional to the probability of that node’s degree (or the number of links to other nodes), reflecting only the network’s connective topology. A quantum walker, however, brings conceptually nontrivial subtleties to the problem, including hallmark quantum effects such as quantum interference and the ability of a walker to be in a coherent superposition of states. In addition, the long-time state of a quantum walker depends on its initial state and most often does not converge to a steady state.

Here, we have constructed a model of a quantum walker on a network. The walker’s state is a multicomponent one, with the squared amplitude of the ith component representing the probability of finding the walker at node i of the network. This multicomponent state evolves in time according to a Schrödinger equation that has a correspondence with the classical walker. By investigating this model, we have succeeded in uncovering the following properties: (1) When the walker starts from its zero-energy ground state, the long-time average of probability of finding it at a node follows the classical result; (2) at higher energies, the walker’s long-time behavior deviates from the classical case, reflecting its quantumness, and this quantumness is quantitatively bounded by the initial energy of the walker and equal to Rényi entropy—a property associated with the network’s degree distribution.

Our paper thus provides the first analytical connection between classical and quantum walks on complex networks, as well as highlighting their differences. We see this work as the beginning of an exciting development that will involve quantum physics, graph and network theory, and the physics of stochastic processes.

Article Text

References (52)

  1. Martí Cuquet and John Calsamiglia, Entanglement Percolation in Quantum Complex Networks, Phys. Rev. Lett. 103, 240503 (2009).
  2. S. Perseguers, M. Lewenstein, A. Acín, and J. I. Cirac, Quantum Random Networks, Nat. Phys. 6, 539 (2010).
  3. S. Perseguers, D. Cavalcanti, G. J. Lapeyre, M. Lewenstein, and A. Acín, Multipartite Entanglement Percolation, Phys. Rev. A 81, 032327 (2010).
  4. Richard P. Feynman, Robert B. Leighton, and Matthew Sands, The Feynman Lectures on Physics (Addison-Wesley, Reading, MA, 2005), 2nd ed.
  5. Richard P. Feynman and A. R. Hibbs, Quantum Mechanics and Path Integrals, International Series in Pure and Applied Physics (McGraw-Hill, New York, 1965).
  6. Andrew M. Childs, Universal Computation by Quantum Walk, Phys. Rev. Lett. 102, 180501 (2009).
  7. E. Farhi and S. Gutmann, Quantum Computation and Decision Trees, Phys. Rev. A 58, 915 (1998).
  8. F. Caruso, A. W. Chin, A. Datta, S. F. Huelga, and M. B. Plenio, Highly Efficient Energy Excitation Transfer in Light-Harvesting Complexes: The Fundamental Role of Noise-Assisted Transport, J. Chem. Phys. 131, 105106 (2009).
  9. M. Mohseni, P. Rebentrost, S. Lloyd, and A. Aspuru-Guzik, Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer, J. Chem. Phys. 129, 174106 (2008).
  10. Yuan-Chung Cheng and Graham R. Fleming, Dynamics of Light Harvesting in Photosynthesis, Annu. Rev. Phys. Chem. 60, 241 (2009).
  11. E. Sánchez-Burillo, J. Duch, J. Gómez-Gardeñes, and D. Zueco, Quantum Navigation and Ranking in Complex Networks, Nat. Sci. Rep. Ochanomizu Univ. 2, 605 (2012).
  12. G. D. Paparo and M. A. Martin-Delgado, Google in a Quantum Network, Sci. Rep. 2, 444 (2012).
  13. Silvano Garnerone, Paolo Zanardi, and Daniel A. Lidar, Adiabatic Quantum Algorithm for Search Engine Ranking, Phys. Rev. Lett. 108, 230506 (2012).
  14. Silvano Garnerone, Thermodynamic Formalism for Dissipative Quantum Walks, Phys. Rev. A 86, 032342 (2012).
  15. O. Mülken and A. Blumen, Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks, Phys. Rep. 502, 37 (2011).
  16. Oliver Muelken, Inefficient Quantum Walks on Networks: The Role of the Density of States, arXiv:0710.3453.
  17. Oliver Mülken, Veronika Bierbaum, and Alexander Blumen, Coherent Exciton Transport in Dendrimers and Continuous-Time Quantum Walks, J. Chem. Phys. 124, 124905 (2006).
  18. Chengzhen Cai and Zheng Yu Chen, Rouse Dynamics of a Dendrimer Model in the ϑ Condition, Macromolecules 30, 5104 (1997).
  19. S. Salimi, Continuous-Time Quantum Walks on Semi-Regular Spidernet Graphs via Quantum Probability Theory, Quantum Inf. Process. 9, 75 (2010).
  20. Herbert Spohn, An Algebraic Condition for the Approach to Equilibrium of an Open N-Level System, Lett. Math. Phys. 2, 33 (1977).
  21. James D. Whitfield, César A. Rodríguez-Rosario, and Alán Aspuru-Guzik, Quantum Stochastic Walks: A Generalization of Classical Random Walks and Quantum Walks, Phys. Rev. A 81, 022323 (2010).
  22. Oliver Mülken, Antonio Volta, and Alexander Blumen, Asymmetries in Symmetric Quantum Walks on Two-Dimensional Networks, Phys. Rev. A 72, 042334 (2005).
  23. Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos, On Power-Law Relationships of the Internet Topology, SIGCOMM Comput. Commun. Rev. 29, 251 (1999).
  24. R. Albert, H. Jeong, and A. L. Barabási, Internet: Diameter of the World-Wide Web, Nature (London) 401, 130 (1999).
  25. A.-L. Barabási and R. Albert, Emergence of Scaling in Random Networks, Science 286, 509 (1999).
  26. Réka Albert and Albert-László Barabási, Statistical Mechanics of Complex Networks, Rev. Mod. Phys. 74, 47 (2002).
  27. M. E. J. Newman, The Structure and Function of Complex Networks, SIAM Rev. 45, 167 (2003).
  28. Mark Newman, Networks: An Introduction (Oxford University Press, New York, NY, 2010).
  29. D. J. de Solla Price, Networks of Scientific Papers, Science 149, 510 (1965).
  30. Ernesto Estrada, The Structure of Complex Networks: Theory and Applications (Oxford University Press, New York, NY, 2011).
  31. Stanley Wasserman and Katherine Faust, Social Network Analysis. Methods and Applications (Cambridge University Press, Cambridge, England, 1994).
  32. Duncan J. Watts, Peter Sheridan Dodds, and M. E. J. Newman, Identity and Search in Social Networks, Science 296, 1302 (2002).
  33. M. E. J. Newman, Spread of Epidemic Disease on Networks, Phys. Rev. E 66, 016128 (2002).
  34. Zoltan Zimboras, Mauro Faccin, Zoltan Kadar, James Whitfield, Ben Lanyon, and Jacob Biamonte, Quantum Transport Enhancement by Time-Reversal Symmetry Breaking, Sci. Rep. 3, 2361 (2013).
  35. J. Kempe, Quantum Random Walks: An Introductory Overview, Contemp. Phys. 44, 307 (2003).
  36. Salvador Elias Venegas-Andraca, Quantum Walks for Computer Scientists, Synthesis Lectures on Quantum Computing 1, 1 (2008).
  37. Wayne W. Zachary, An Information Flow Model for Conflict and Fission in Small Groups, J. Anthropol. Res. 33, 452 (1977).
  38. Roger Guimera, Leon Danon, A Diaz-Guilera, Francesc Giralt, and Alex Arenas, Self-Similar Community Structure in a Network of Human Interactions, Phys. Rev. E 68, 065103 (2003).
  39. Jordi Duch and Alex Arenas, Community Detection in Complex Networks Using Extremal Optimization, Phys. Rev. E 72, 027104 (2005).
  40. Mark E. J. Newman, Finding Community Structure in Networks Using the Eigenvectors of Matrices, Phys. Rev. E 74, 036104 (2006).
  41. John C. Baez and Jacob Biamonte, A Course on Quantum Techniques for Stochastic Mechanics, arXiv:1209.3632.
  42. T. H. Johnson, S. R. Clark, and D. Jaksch, Dynamical Simulations of Classical Stochastic Systems Using Matrix Product States, Phys. Rev. E 82, 036702 (2010).
  43. J. C. Baez and B. Fong, A Noether Theorem for Markov Processes, J. Math. Phys. (N.Y.) 54, 013301 (2013).
  44. Joel Keizer, On the Solutions and the Steady States of a Master Equation, J. Stat. Phys. 6, 67 (1972).
  45. Peter Lancaster and Miron Tismenetsky, Theory of Matrices (Academic Press, New York, 1985), Vol. 2.
  46. James R. Norris, Markov Chains, 2008 (Cambridge University Press, Cambridge, England, 1998).
  47. Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani, Quantum Walks on Graphs, in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (Organization ACM, New York, NY, 2001), pp. 50–59.
  48. C. Beck and F. Schögl, Thermodynamics of Chaotic Systems: An Introduction (Cambridge University Press, Cambridge, England, 1993).
  49. P. Erdős and A. Rényi, On the Evolution of Random Graphs, in Publication of the Mathematical Institute of the Hungarian Academy of Sciences (Hungarian Academy of Science, Budapest, Hungary, 1960), pp. 17–61.
  50. D. J. Watts and S. H. Strogatz, Collective Dynamics of “Small-World” Networks, Nature (London) 393, 440 (1998).
  51. Mathew Penrose, Random Geometric Graphs (Oxford University Press on Demand, Oxford, England, 2003), Vol. 5.
  52. Alain Barrat and M. Weigt, On the Properties of Small-World Network Models, Eur. Phys. J. B 13, 547 (2000).

Outline

Information

Phys. Rev. X 3, 041007– Published 24 October, 2013
  • Received 29 May 2013
Creative Commons Logo

This article is available under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation