Abstract
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 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 “-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.
- Received 25 October 2011
DOI:https://doi.org/10.1103/PhysRevLett.108.230506
© 2012 American Physical Society
Synopsis
Ranking Web Sites Quantum Mechanically
Published 4 June 2012
Quantum computing could be used to efficiently rank internet sites, according to a theoretical proposal.
See more in Physics