Quantum PageRank Algorithm Outperforms Classical Version
A quantum version of Google’s famous search algorithm could one day make web searches faster, say computer scientists
Google’s PageRank algorithm is the idea that the importance of a webpage can be measured by the number of important papers that point towards it. Sergey Brin and Larry Page applied the process to search engine rankings in 1998 and have since modified it in various ways that have maintained Google’s position as the world’s leading search engine.
Given the company’s huge success, it is no surprise that there is enormous interest in finding algorithms that outperform PageRank.
Today, Giuseppe Paparo and Miguel Martín-Delgado at The Complutense University in Madrid reveal a contender- a quantum version of the original algorithm.
This story is only available to subscribers.
Don’t settle for half the story.
Get paywall-free access to technology news for the here and now.
Subscribe now
Already a subscriber?
Sign in
You’ve read all your free stories.
MIT Technology Review provides an
intelligent and independent filter for the
flood of information about technology.
Subscribe now
Already a subscriber?
Sign in
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.
This kind of technology is widely regarded as more achievable than quantum computing and many groups around the world are working on the challenges it poses.
The possibility of quantum networks raises the question of the best way to search for quantum information on this net. To that end, Paparo and Martín-Delgado have devised a quantum version of the PageRank algorithm that does the trick.
The way they think about this is to imagine a quantum page crawler wandering around the network along paths that connect one quantum node to the next. While the quantum paths remain in a quantum superposition, the importance of a page is the probability of finding the crawler on that page at any instant.
Paparo and Martín-Delgado then outline a quantum algorithm that will produce a ranking of pages at any given instant using these quantum probabilities. They go on to simulate its performance on two relatively small networks: a tree-like network and a directed graph network with no specific structure.
What’s interesting is how this algorithm compares to the classical version. The nature of quantum algorithms produces results extremely rapidly–faster than any classical algorithm, in theory.
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.
But to see exactly how, these guys will have to tackle bigger quantum networks, something they clearly have on their radar. We’ll be watching.
Ref: arxiv.org/abs/1112.2079: Google in a Quantum Network
