Pages

December 13, 2011

Quantum PageRank Algorithm Outperforms Classical Version

A quantum version of Google's famous search algorithm could one day make web searches faster

Giuseppe Paparo and Miguel Martín-Delgado at The Complutense University in Madrid reveal a contender- a quantum version of the original algorithm.

This approach is motivated by the progress being made towards quantum networks in which information is stored transmitted and routed as quantum bits, or qubits, rather than as classical bits. In this world, the information stays in superposition of states, dramatically changing the way it can be processed.




With a tree graph, the quantum algorithm outperforms the classical algorithm in ranking the root page. However, although the algorithms average ranking of other pages produces the same hierarchy as a classical network, the quantum hierarchy may be different at any specific instant. This reflects the quantum fluctuations that can occur in these kinds of experiments.

For a directed graph, the results are similar. The quantum algorithm spots the highest ranking page much more quickly than a classical algorithm but it only matches the classical hierarchy of other pages on average.

That's an interesting first step towards quantum search. On this evidence, it's easy to imagine that quantum and classical searches could complement each other.

Arxiv - Google in a Quantum Network

We introduce the characterization of a class of quantum PageRank algorithms in a scenario in which some kind of quantum network is realizable out of the current classical internet web, but no quantum computer is yet available. This class represents a quantization of the PageRank protocol currently employed to list web pages according to their importance. We have found an instance of this class of quantum protocols that outperforms its classical counterpart and may break the classical hierarchy of web pages depending on the topology of the web.

If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks
blog comments powered by Disqus