Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

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

  • December 13, 2011

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

Get stories like this before anyone else with First Look.

Subscribe today
Already a Premium subscriber? Log in.

Uh oh–you've read all of your free articles for this month.

Insider Premium
$179.95/yr US PRICE

More from Intelligent Machines

Artificial intelligence and robots are transforming how we work and live.

Want more award-winning journalism? Subscribe and become an Insider.
  • Insider Premium {! insider.prices.premium !}*

    {! insider.display.menuOptionsLabel !}

    Our award winning magazine, unlimited access to our story archive, special discounts to MIT Technology Review Events, and exclusive content.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

    First Look. Exclusive early access to stories.

    Insider Conversations. Listen in as our editors talk to innovators from around the world.

  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus ad-free web experience, select discounts to partner offerings and MIT Technology Review events

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning magazine and daily delivery of The Download, our newsletter of what’s important in technology and innovation.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

/
You've read all of your free articles this month. This is your last free article this month. You've read of free articles this month. or  for unlimited online access.