Quantum Google in a Complex Network
Open accessThe DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Abstract
We investigate the behaviour of the recently proposed Quantum PageRank algorithm, in large complex networks. We find that the algorithm is able to univocally reveal the underlying topology of the network and to identify and order the most relevant nodes. Furthermore, it is capable to clearly highlight the structure of secondary hubs and to resolve the degeneracy in importance of the low lying part of the list of rankings. The quantum algorithm displays an increased stability with respect to a variation of the damping parameter, present in the Google algorithm, and a more clearly pronounced power-law behaviour in the distribution of importance, as compared to the classical algorithm. We test the performance and confirm the listed features by applying it to real world examples from the WWW. Finally, we raise and partially address whether the increased sensitivity of the quantum algorithm persists under coordinated attacks in scale-free and random networks.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Complex networks: structure and dynamics
BOCCALETTI, S., LATORA, V, MORENO, Y., CHAVEZ, M., & HWANG, D. (2006) · Physics Reports · doi:10.1016/j.physrep.2005.10.009 · Cited by 11,010
Network biology: understanding the cell's functional organization
Barabási, A.-L., & Oltvai, Z. N. (2004) · Nature Reviews Genetics · doi:10.1038/nrg1272 · Cited by 7,903
Exploring Network Structure, Dynamics, and Function Using NetworkX
Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008) · Proceedings of the Python in Science Conference · doi:10.25080/tcwv9851 · Cited by 7,477
Newman, M. (2010) · doi:10.1093/acprof:oso/9780199206650.001.0001 · Cited by 6,595
Erdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
Hierarchical Organization of Modularity in Metabolic Networks
Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barabási, A.-L. (2002) · Science · doi:10.1126/science.1073374 · Cited by 4,224
Hierarchical organization in complex networks
Ravasz, E., & Barabási, A.-L. (2003) · Physical Review E · doi:10.1103/physreve.67.026112 · Cited by 2,160
Self-similarity of complex networks
Song, C., Havlin, S., & Makse, H. A. (2005) · Nature · doi:10.1038/nature03248 · Cited by 1,495
Universal Computation by Quantum Walk
Childs, A. M. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.180501 · Cited by 1,002
Aharonov, D., Ambainis, A., Kempe, J., & Vazirani, U. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380758 · Cited by 654
Research works printed but not linked: 48
- Brin, S. & Page, L. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems 30, 107–117 (1998). · DOI · Paper page
- Watts, D. & Strogatz, S. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998). · DOI · Paper page
- Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999). · DOI · Paper page
- Barabási, A.-L., Dezso, Z., Ravasz, E., Yook, S.-H. & Oltvai, Z. Scale-free and hierarchical structures in complex networks. In AIP Conference Proceedings, vol. 661, 1 (2003).
- Newman, M. E. The structure and function of complex networks. SIAM Review 45, 167–256 (2003). · DOI · Paper page
- Newman, M. Networks: an introduction (Oxford University Press, Inc., 2010). · DOI · Paper page
- Cohen, R. & Havlin, S. Complex networks: structure, robustness and function (Cambridge University Press, 2010). · DOI · Paper page
- Barabási, A.-L. Network science. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 371, ( 2013 March 28). · DOI · Paper page
- Bollobás, B., Borgs, C., Chayes, J. & Riordan, O. Directed scale-free graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms 132–139 (Society for Industrial and Applied Mathematics, 2003).
- Elliott, C. The DARPA quantum network. Quantum Communications and cryptography 83–102 (2006). · DOI
- Poppe, A., Peev, M. & Maurhart, O. Outline of the secoqc quantum-key-distribution network in Vienna. International Journal of Quantum Information 6, 209–218 (2008). · DOI
- Sasaki, M. et al. Field test of quantum key distribution in the tokyo qkd network. Optics Express 19, 10387–10409 (2011). · DOI · Paper page
- Lancho, D., Martinez, J., Elkouss, D., Soto, M. & Martin, V. Qkd in standard optical telecommunications networks. Quantum Communication and Quantum Networking 142–149 (2010). · DOI
- Länger, T. & Lenhart, G. Standardization of quantum key distribution and the etsi standardization initiative isg-qkd. New Journal of Physics 11, 055051 (2009). · DOI
- Szegedy, M. Quantum speed-up of Markov chain based algorithms. In: Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on 32–41 (IEEE, 2004). · DOI
- Albert, R. & Barabási, A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47 (2002). · DOI · Paper page
- Barabási, A.-L., Albert, R. & Jeong, H. Scale-free characteristics of random networks: the topology of the world-wide web. Physica A: Statistical Mechanics and its Applications 281, 69–77 (2000). · DOI · Paper page
- Barrat, A., Barthelemy, M., Pastor-Satorras, R. & Vespignani, A. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences of the United States of America 101, 3747–3752 (2004). · DOI · Paper page
- Jeong, H., Mason, P., Barabasi, A.-L. & Oltvai, Z. Lethality and centrality in protein networks. Nature 411, 41–42 (2001). · DOI · Paper page
- Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. & Barabási, A.-L. The large-scale organization of metabolic networks. Nature 407, 651–654 (2000). · DOI · Paper page
- Albert, R., Jeong, H. & Barabási, A.-L. Error and attack tolerance of complex networks. Nature 406, 378–382 (2000). · DOI · Paper page
- Callaway, D. S., Newman, M. E., Strogatz, S. H. & Watts, D. J. Network robustness and fragility: Percolation on random graphs. Phys. Rev. Lett. 85, 5468–5471 (2000). · DOI · Paper page
- Vázquez, A. & Moreno, Y. Resilience to damage of graphs with degree correlations. Phys. Rev. E 67, 015101 (2003). · DOI · Paper page
- Carmi, S., Carter, S., Sun, J. & Ben-Avraham, D. Asymptotic behavior of the Kleinberg model. Phys. Rev. Lett. 102, 238702 (2009). · DOI
- Lee, S. H. & Holme, P. Exploring maps with greedy navigators. Phys. Rev. Lett. 108, 128701 (2012). · DOI
- Liu, Y.-Y., Slotine, J.-J. & Barabási, A.-L. Controllability of complex networks. Nature 473, 167–173 (2011). · DOI · Paper page
- Nepusz, T. & Vicsek, T. Controlling edge dynamics in complex networks. Nat. Phys. 8, 568–573 (2012). · DOI · Paper page
- Nicosia, V., Criado, R., Romance, M., Russo, G. & Latora, V. Controlling centrality in complex networks. Sci. Rep. 2, 218 (2012). 10.1038/srep00218 · DOI · Paper page
- Albert, R., Jeong, H. & Barabasi, A.-L. Diameter of the world wide web. Nature 401, 130–131 (1999). · DOI · Paper page
- Erdős, P. & Rényi, A. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl 5, 17–61 (1960).
- Erdős, P. & Rényi, A. On the strength of connectedness of a random graph. Acta Mathematica Hungarica 12, 261–267 (1961). · DOI · Paper page
- Barabási, A.-L., Ravasz, E. & Vicsek, T. Deterministic scale-free networks. Physica A: Statistical Mechanics and its Applications 299, 559–564 (2001). · DOI · Paper page
- Noh, J. D. Exact scaling properties of a hierarchical network model. Phys. Rev. E 67, 045103 (2003). · DOI · Paper page
- Comellas, F. & Miralles, A. Modeling complex networks with self-similar outerplanar unclustered graphs. Physica A: Statistical Mechanics and its Applications 388, 2227–2233 (2009). · DOI
- Comellas, F. & Miralles, A. Vertex labeling and routing in self-similar outerplanar unclustered graphs modeling complex networks. Journal of Physics A: Mathematical and Theoretical 42, 425001 (2009). · DOI
- Brandstädt, A., Le, V. B. & Spinrad, J. P. Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, vol. 3. (Society for Industrial and Applied Mathematics, 1999). · doi:10.1137/1.9780898719796
- Evers, F. & Mirlin, A. D. Anderson transitions. Rev. Mod. Phys. 80, 1355 (2008). · DOI · Paper page
- Georgeot, B., Giraud, O. & Shepelyansky, D. L. Spectral properties of the Google matrix of the world wide web and other directed networks. Phys. Rev. E 81, 056109 (2010). · DOI · Paper page
- Galindo, A. & Martin-Delgado, M. A. Information and computation: Classical and quantum aspects. Rev. Mod. Phys. 74, 347 (2002). · DOI · Paper page
- Nielsen, M. A. & Chuang, I. L. Quantum computation and quantum information (Cambridge university press, 2010).
- Lo, H.-K., Spiller, T. & Popescu, S. Introduction to quantum computation and information (World Scientific Publishing Company, 1998). · DOI · Paper page
- Donato, D., Laura, L., Leonardi, S. & Millozzi, S. Large scale properties of the webgraph. The European Physical Journal B-Condensed Matter and Complex Systems 38, 239–243 (2004). · DOI
- Kendall, M. G. & Smith, B. B. The problem of m rankings. The annals of mathematical statistics 275–287 (1939). · DOI · Paper page
- Cuquet, M. & Calsamiglia, J. Growth of graph states in quantum networks. Phys. Rev. A 86, 042304 (2012). URL http://link.aps.org/doi/10.1103/PhysRevA.86.042304. · DOI
- Venegas-Andraca, S. E. Quantum walks: a comprehensive review. Quantum Information Processing 1–92 (2012). · DOI · Paper page
- de Lima Marquezino, F., Portugal, R. & Boettcher, S. Spatial search algorithms on hanoi networks. Phys. Rev. A 87, 012329 (2013). · DOI
- Verstraete, F., Wolf, M. M. & Cirac, J. I. Quantum computation and quantum-state engineering driven by dissipation. Nat. Phys. 5, 633–636 (2009). · DOI · Paper page
- Diehl, S. et al. Quantum states and phases in driven open quantum systems with cold atoms. Nat. Phys. 4, 878–883 (2008). · DOI · Paper page
Cited by
Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
Qiang, X., Zhou, X., Wang, J., Wilkes, C. M., Loke, T., O’Gara, S., Kling, L., Marshall, G. D., Santagati, R., Ralph, T. C., et al. (2018) · Nature Photonics · doi:10.1038/s41566-018-0236-y · Cited by 516
Random Walks: A Review of Algorithms and Applications
Xia, F., Liu, J., Nie, H., Fu, Y., Wan, L., & Kong, X. (2020) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2019.2952908 · Cited by 295
Quantum Speedup for Active Learning Agents
Paparo, G. D., Dunjko, V., Makmal, A., Martin-Delgado, M. A., & Briegel, H. J. (2014) · Physical Review X · doi:10.1103/physrevx.4.031002 · Cited by 192
Self-citationInterdisciplinary and physics challenges of network theory
Bianconi, G. (2015) · EPL (Europhysics Letters) · doi:10.1209/0295-5075/111/56001 · Cited by 126
Universally optimal noisy quantum walks on complex networks
Caruso, F. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/5/055015 · Cited by 54
Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer
Huerta Alderete, C., Singh, S., Nguyen, N. H., Zhu, D., Balu, R., Monroe, C., Chandrashekar, C. M., & Linke, N. M. (2020) · Nature Communications · doi:10.1038/s41467-020-17519-4 · Cited by 48
Exploring complex graphs using three-dimensional quantum walks of correlated photons
Ehrhardt, M., Keil, R., Maczewsky, L. J., Dittel, C., Heinrich, M., & Szameit, A. (2021) · Science Advances · doi:10.1126/sciadv.abc5266 · Cited by 42
Quantum Google algorithm: Construction and application to complex networks
Paparo, G. D., Müller, M., Comellas, F., & Martin-Delgado, M. A. (2014) · The European Physical Journal Plus · doi:10.1140/epjp/i2014-14150-y · Cited by 17
“In this paper we review the Quantum PageRank algorithm [1, 2] and illustrate the main findings when applied to complex networks of different sizes and topologies, like the scale-free and hierarchical ones.”
BackgroundMethodInfluentialSelf-citationMulti-particle quantum walks on 3D integrated photonic chip
Zhou, W.-H., Wang, X.-W., Ren, R.-J., Fu, Y.-X., Chang, Y.-J., Xu, X.-Y., Tang, H., & Jin, X.-M. (2024) · Light: Science & Applications · doi:10.1038/s41377-024-01627-7 · Cited by 16
Singh, S., Alderete, C. H., Balu, R., Monroe, C., Linke, N. M., & Chandrashekar, C. M. (2021) · Physical Review A · doi:10.1103/physreva.104.062401 · Cited by 13
Singh, S., Alderete, C. H., Balu, R., Monroe, C., Linke, N. M., & Chandrashekar, C. M. (2020) · arXiv · doi:10.48550/arxiv.2001.11197 · Cited by 13
Metadata
- Authors
- Paparo, G. D., Müller, M., Comellas, F., & Martin-Delgado, M. A.
- Venue
- Scientific Reports
- Published
- 2013-10-04
- Volume
- 3
- Issue
- 1
- Pages
- 2773-2773
- ISSN
- 2045-2322 (ISSN-L)
- OpenAlex
- W2117676143
- Cited by
- 93
- References
- 19
- FWCI
- 6.70
- Type
- journal article
- Language
- en
- Open access
- gold
- Licence
- creativecommons.org/licenses/by-nc-nd/3.0/ (tdm)
- creativecommons.org/licenses/by-nc-nd/3.0/ (vor)
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.