Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo

 

Unsupported browser: Your browser does not meet modern web standards. See how it scores »

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 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

4 comments. Share your thoughts »

Tagged: Computing

Reprints and Permissions | Send feedback to the editor

From the Archives

Close

Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me