Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine

Abstract

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.

arXiv commentRevTex 4.2, 14 color figures, 2 tables

References in corpus (14)

• The large-scale organization of metabolic networks
• Scale-free brain functional networks
• Quantum Internet: Networking Challenges in Distributed Quantum Computing
• Journal Status
• Google in a Quantum Network
• Quantum Navigation and Ranking in Complex Networks
• Adiabatic quantum algorithm for search engine ranking
• Quantum Google in a Complex Network
• Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State
• Discrete-time quantum walk algorithm for ranking nodes on a network
• Algebraic analysis of quantum search with pure and mixed states
• Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
• Discrete-time Semiclassical Szegedy Quantum Walks
• SQUWALS: A Szegedy QUantum WALks Simulator

Cited by in corpus (2)

• Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption
• Complex-Phase Extensions of Szegedy Quantum Walk on Graphs