2026-06-28T09:58:28Zhttps://docta.ucm.es/rest/oai/requestoai:docta.ucm.es:20.500.14352/1368662026-05-22T00:11:23Zcom_20.500.14352_14col_20.500.14352_15
Docta Complutense
author
Ortega, Sergio A.
author
Martín-Delgado Alcántara, Miguel Ángel
2026-05-21T18:50:19Z
2026-05-21T18:50:19Z
2024-10-04
Ortega, S. A., & Martin-Delgado, M. A. (2024). Randomized SearchRank: A semiclassical approach to a quantum search engine. Physical Review Research, 6(4), 043014.
10.1103/PhysRevResearch.6.043014
https://hdl.handle.net/20.500.14352/136866
2643-1564
https://doi.org/10.1103/PhysRevResearch.6.043014
https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.6.043014
The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. However, this algorithm loses its functionality when the 𝑁/𝑀 ratio between the network size 𝑁 and the number of marked nodes 𝑀 is sufficiently large. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk. To maintain the same time complexity as the quantum SearchRank algorithm we propose a simplification of the algorithm. This new algorithm is called randomized SearchRank, since it corresponds to a quantum walk over a randomized mixed state. The performance of the SearchRank algorithms is first analyzed on an example network and then statistically on a set of different networks of increasing size and different number of marked nodes. On the one hand, to test the search ability of the algorithms, it is computed how the probability of measuring the marked nodes decreases with 𝑁/𝑀 for the quantum SearchRank, but remarkably it remains at a high value around 0.9 for our semiclassical algorithms, solving the quantum SearchRank problem. The time complexity of the algorithms is also analyzed, obtaining a quadratic speedup with respect to the classical ones. On the other hand, the ranking functionality of the algorithms has been investigated, obtaining a good agreement with the classical PageRank distribution. Finally, the dependence of these algorithms on the intrinsic PageRank damping parameter has been clarified. Our results suggest that this parameter should be below a threshold so that the execution time does not increase drastically.
eng
Attribution 4.0 International
Randomized SearchRank: a semiclassical approach to a quantum search engine
journal article
UGFyYSBxdWUgZWwgcmVwb3NpdG9yaW8gaW5zdGl0dWNpb25hbCBkZSBsYSBVbml2ZXJzaWRhZCBkZSBNYWRyaWQgcHVlZGEgYWxtYWNlbmFyIHkgZGlzdHJpYnVpciBlbCBvYmpldG8gZGlnaXRhbCBkZXBvc2l0YWRvLCBlcyBuZWNlc2FyaW8gcXVlIGxhIHBlcnNvbmEgcXVlIGhhZ2EgZWwgZGVww7NzaXRvIGxlYSB5IGFjZXB0ZSBsYXMgY29uZGljaW9uZXMgZXN0YWJsZWNpZGFzIGVuIGVzdGEgbGljZW5jaWE6CuKAoiBBY2VwdGFuZG8gZXN0YSBsaWNlbmNpYSwgdXN0ZWQgY29tbyBhdXRvci9yZXMgeS9vIHByb3BpZXRhcmlvL3MgZGUgbG9zIGRlcmVjaG9zIGRlIHByb3BpZWRhZCBpbnRlbGVjdHVhbCwgbyBsYSBwZXJzb25hIGRlbGVnYWRhIHBhcmEgaGFjZXJsbyAsIG90b3JnYSBhbCByZXBvc2l0b3JpbyBkZSBsYSBVbml2ZXJzaWRhZCBDb21wbHV0ZW5zZSBkZSBNYWRyaWQgZWwgZGVyZWNobyBubyBleGNsdXNpdm8gZGUgcmVwcm9kdWNjacOzbiB5IGRpc3RyaWJ1Y2nDs24gZGUgc3Ugb2JyYSBlbiBjdWFscXVpZXIgZm9ybWF0byB5IG1lZGlvLgrigKIgRWwgZGVwb3NpdGFudGUsIGVuIGNhc28gZGUgdW5hIG9icmEgY29uIG3DoXMgZGUgdW4gYXV0b3IsIGdhcmFudGl6YSBxdWUgbG8gaGFjZSByZXNwb25zYWJsZW1lbnRlIGVuIG5vbWJyZSB5IGNvbiBjb25zZW50aW1pZW50byBkZSBsb3MgZGVtw6FzIGF1dG9yZXMuCuKAoiBBY2VwdGEgcXVlIGVsIHJlcG9zaXRvcmlvIGRlIGxhIFVuaXZlcnNpZGFkIENvbXBsdXRlbnNlIGRlIE1hZHJpZCBwdWVkYSBjb25zZXJ2YXIgbcOhcyBkZSB1bmEgY29waWEgZGUgZXN0ZSBkb2N1bWVudG8geSwgc2luIGFsdGVyYXIgc3UgY29udGVuaWRvLCBjb252ZXJ0aXJsbyBhIGN1YWxxdWllciBmb3JtYXRvIGRlIGZpY2hlcm8sIG1lZGlvIG8gc29wb3J0ZSwgcGFyYSBwcm9ww7NzaXRvcyBkZSBzZWd1cmlkYWQgeSBwcmVzZXJ2YWNpw7NuLgrigKIgRGVjbGFyYSBxdWUgZWwgZG9jdW1lbnRvIGVzIHVuIHRyYWJham8gb3JpZ2luYWwgc3V5bywgbyBxdWUgZXMgbGEgcGVyc29uYSBkZWxlZ2FkYSBwYXJhIHJlYWxpemFyIGVsIGRlcMOzc2l0byB5LCBwb3IgdGFudG8sIGN1ZW50YSBjb24gbGEgcG90ZXN0YWQgcGFyYSBvdG9yZ2FyIGxvcyBkZXJlY2hvcyBjb250ZW5pZG9zIGVuIGVzdGEgbGljZW5jaWEuIFRhbWJpw6luIGRlY2xhcmEgcXVlIHN1IGRvY3VtZW50byBubyBpbmZyaW5nZSBsbyBlc3RhYmxlY2lkbyBlbiBsYSB2aWdlbnRlIGxlZ2lzbGFjacOzbiBkZSBwcm9waWVkYWQgaW50ZWxlY3R1YWwuCuKAoiBTaSBlbCBkb2N1bWVudG8gY29udGllbmUgbWF0ZXJpYWxlcyBkZSBsb3MgY3VhbGVzIG5vIHRpZW5lIGxvcyBkZXJlY2hvcyBkZSBhdXRvciwgZGVjbGFyYSBxdWUgaGEgb2J0ZW5pZG8gZWwgcGVybWlzbyBzaW4gcmVzdHJpY2Npw7NuIGRlbCBwcm9waWV0YXJpbyBwYXJhIG90b3JnYXIgYSBsYSBVbml2ZXJzaWRhZCBDb21wbHV0ZW5zZSBkZSBNYWRyaWQgbG9zIGRlcmVjaG9zIHJlcXVlcmlkb3MgcG9yIGVzdGEgbGljZW5jaWEsIHkgcXVlIGVzZSBtYXRlcmlhbCwgY3V5b3MgZGVyZWNob3Mgc29uIGRlIHRlcmNlcm9zLCBlc3TDoSBjbGFyYW1lbnRlIGlkZW50aWZpY2FkbyB5IHJlY29ub2NpZG8gZGVudHJvIGRlbCBjb250ZW5pZG8gZGVsIGRvY3VtZW50by4K4oCiIFNpIGVsIGRvY3VtZW50byBzZSBiYXNhIGVuIHVuYSBvYnJhIHF1ZSBoYSBzaWRvIHBhdHJvY2luYWRhIG8gYXBveWFkYSBwb3IgdW5hIGFnZW5jaWEgdSBvcmdhbml6YWNpw7NuIGRpZmVyZW50ZSBkZSBsYSBVbml2ZXJzaWRhZCBDb21wbHV0ZW5zZSBkZSBNYWRyaWQsIHVzdGVkIGRlY2xhcmEgcXVlIGhhIGN1bXBsaWRvIGNvbiBsYXMgb2JsaWdhY2lvbmVzIHJlcXVlcmlkYXMgcG9yIGVzdGUgY29udHJhdG8gbyBhY3VlcmRvLgrigKIgTGEgVW5pdmVyc2lkYWQgQ29tcGx1dGVuc2UgZGUgTWFkcmlkIGlkZW50aWZpY2Fyw6EgY2xhcmFtZW50ZSBzdS9zIG5vbWJyZS9zIGNvbW8gZWwvbG9zIGF1dG9yL2VzIG8gcHJvcGlldGFyaW8vcyBkZSBsb3MgZGVyZWNob3MgZGVsIGRvY3VtZW50bywgeSBubyBoYXLDoSBuaW5ndW5hIGFsdGVyYWNpw7NuIGRlIHN1IGRvY3VtZW50byBkaWZlcmVudGUgYSBsYXMgcGVybWl0aWRhcyBlbiBlc3RhIGxpY2VuY2lhLgrigKIgVHJhYmFqb3MgZGVwb3NpdGFkb3MgcG9yIHN1IHByb3BpbyBhdXRvcjogYWwgYXV0by1hcmNoaXZhciBlc3RhIGNvbGVjY2nDs24gZGUgZmljaGVyb3MgeSBtZXRhZGF0b3MgYmlibGlvZ3LDoWZpY29zIGFzb2NpYWRvcywgb3RvcmdvIGFsIHJlcG9zaXRvcmlvIGluc3RpdHVjaW9uYWwgZGUgbGEgVW5pdmVyc2lkYWQgQ29tcGx1dGVuc2UgZGUgTWFkcmlkIGVsIGRlcmVjaG8gcGFyYSBhbG1hY2VuYXJsb3MgeSBkaXN0cmlidWlybG9zLiBEZWNsYXJvIHF1ZSBlc3RlIG1hdGVyaWFsIGVzIGRlIG1pIHByb3BpZWRhZCBpbnRlbGVjdHVhbCB5IHF1ZSBlbCByZXBvc2l0b3JpbyBpbnN0aXR1dGljaW9uYWwgZGUgbGEgVW5pdmVyc2lkYWQgQ29tcGx1dGVuc2UgZGUgTWFkcmlkLCBubyBhc3VtZSByZXNwb25zYWJpbGlkYWQgYWxndW5hIGVuIGNhc28gZGUgcXVlIHNlIHByb2R1emNhIHVuYSB2aW9sYWNpw7NuIGRlIGRlcmVjaG9zIGRlIHByb3BpZWRhZCBhbCBkaXN0cmlidWlyIGVzdG9zIGZpY2hlcm9zIG8gbWV0YWRhdG9zLgrigKIgVHJhYmFqb3MgZGVwb3NpdGFkb3MgcG9yIG90cm9zIHF1ZSBubyBzZWFuIHN1IGF1dG9yOiBkZWNsYXJvIHF1ZSBsb3MgbWV0YWRhdG9zIGJpYmxpb2dyw6FmaWNvcyBxdWUgZXN0b3kgYXJjaGl2YW5kbyBlbiBlbCByZXBvc2l0b3JpbyBpbnN0aXR1Y2lvbmFsIGRlIGxhIFVuaXZlcnNpZGFkIENvbXBsdXRlbnNlIGRlIE1hZHJpZCwgc29uIGRlIGRvbWluaW8gcMO6YmxpY28uIFNpIG5vIGZ1ZXNlIGVsIGNhc28sIGFjZXB0byBwbGVuYSByZXNwb25zYWJpbGlkYWQgcG9yIGN1YWxxdWllciBpbmZyYWNjacOzbiBkZSBkZXJlY2hvcyBkZSBhdXRvciBxdWUgY29ubGxldmUgbGEgZGlzdHJpYnVjacOzbiBkZSBlc3RvcyBmaWNoZXJvcyBvIG1ldGFkYXRvcy4K4oCiIFBvciB0YW50bywgdG9kb3MgbG9zIG1ldGFkYXRvcyBwdWJsaWNhZG9zIGVuIGVsIHJlcG9zaXRvcmlvIGluc3RpdHVjaW9uYWwgZGUgbGEgVW5pdmVyc2lkYWQgQ29tcGx1dGVuc2UgZGUgTWFkcmlkLCBlc3TDoW4gZGlzcG9uaWJsZXMgY29uIGxhIGxpY2VuY2lhIENyZWF0aXZlIENvbW1vbnMgQ0MwIDEuMCBVbml2ZXJzYWwgT2ZyZWNpbWllbnRvIGFsIERvbWluaW8gUMO6YmxpY28gKENDMCAxLjApLiBFc3RhIGxpY2VuY2lhIHBlcm1pdGUgY29waWFyLCBtb2RpZmljYXIsIGRpc3RyaWJ1aXIsIHJldXRpbGl6YXIgeSBjb21wYXJ0aXIgcMO6YmxpY2EgeSBsaWJyZW1lbnRlIGxvcyBtZXRhZGF0b3MgKGluY2x1eWVuZG8gc3UgdXNvIGNvbWVyY2lhbCksIHNpbiB0ZW5lciBxdWUgcGVkaXIgcGVybWlzby4gU2kgdGVyY2VyYXMgcGFydGVzIHVzYW4gZXN0b3MgbWV0YWRhdG9zLCBkZWJlbiBoYWNlciB1biByZWNvbm9jaW1pZW50byB5IHVuYSBhdHJpYnVjacOzbiBhIGxhcyBmdWVudGVzIGRlIGxvcyBtaXNtb3MuIExhIHJldXRpbGl6YWNpw7NuIGRlIGVzdG9zIG1ldGFkYXRvcyB0YW1iacOpbiBlcyBsaWJyZSwgdGFsIHkgY29tbyBlc3RhYmxlY2UgbGEgbGljZW5jaWEgZGUgdXNvIENDMC4K
URL
https://docta.ucm.es/bitstreams/71fbaf70-13f1-4894-927e-ba83e2c9d6ff/download
File
MD5
9cf55bb337923122ab0baeabb9981dab
2480204
application/pdf
Randomized SearchRank- A semiclassical approach to a quantum search engine.pdf