2011/09/30 by Silvano Garnerone, Paolo Zanardi, Daniel A. Lidar · 1 citation
Computer Science · Physics and Astronomy · #Adiabatic process #Algorithm #Computer science #Information retrieval #PageRank #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum computer #Quantum many-body systems #Quantum mechanics #Ranking (information retrieval) #Theoretical computer science #physics.soc-ph #quant-ph
paper · pdf · doi:10.1103/physrevlett.108.230506
published as Phys. Rev. Lett. 108, 230506 (2012) · 7 pages, 5 figures; closer to published version
arxiv created 2012/06/04 · openalex publication_date 2012/06/04 · arxiv updated 2012/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We propose an adiabatic quantum algorithm for generating a quantum pure state encoding of the PageRank vector, the most widely used tool in ranking the relative importance of internet pages. We present extensive numerical simulations which provide evidence that this algorithm can prepare the quantum PageRank state in a time which, on average, scales polylogarithmically in the number of web pages. We argue that the main topological feature of the underlying web graph allowing for such a scaling is the out-degree distribution. The top-ranked log(n) entries of the quantum PageRank state can then be estimated with a polynomial quantum speed-up. Moreover, the quantum PageRank state can be used in "q-sampling" protocols for testing properties of distributions, which require exponentially fewer measurements than all classical schemes designed for the same task. This can be used to decide whether to run a classical update of the PageRank.