Randomized SearchRank: A semiclassical approach to a quantum search engine
Physical Review Research · 04.10.2024 · 6 (4)
DOI: 10.1103/physrevresearch.6.043014 ↗Kurz gefasst
Fachartikel in der Zeitschrift Physical Review Research, online erschienen am 04.10.2024. Verfasst von Sergio A. Ortega und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 41 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministerio de Economía y Competitividad, Comunidad de Madrid, Army Research Office.
Abstract (Originalsprache)
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 N / M ratio between the network size N and the number of marked nodes M 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 N / M 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. Published by the American Physical Society 2024
Förderung
- Ministerio de Economía y Competitividad
- Comunidad de Madrid
- Army Research Office
- Universidad Complutense de Madrid
Zitieren
APA
Ortega, S. A., & Martin-Delgado, M. A. (2024). Randomized SearchRank: A semiclassical approach to a quantum search engine. Physical Review Research, 6(4). https://doi.org/10.1103/physrevresearch.6.043014
Vancouver
Ortega SA, Martin-Delgado MA. Randomized SearchRank: A semiclassical approach to a quantum search engine. Physical Review Research. 2024;6(4). doi:10.1103/physrevresearch.6.043014
BibTeX
@article{Ortega2024,
author = {Ortega, Sergio A. and Martin-Delgado, Miguel A.},
title = {Randomized SearchRank: A semiclassical approach to a quantum search engine},
journal = {Physical Review Research},
year = {2024},
volume = {6},
number = {4},
doi = {10.1103/physrevresearch.6.043014}
}
EUVIMED