Skip to Content

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

Keep Reading

Most Popular

2021 tech fails concept
2021 tech fails concept

The worst technology of 2021

Face filters, billionaires in space, and home-buying algorithms that overpay all made our annual list of technology gone wrong.

conceptual illustration showing various women's faces being scanned
conceptual illustration showing various women's faces being scanned

A horrifying new AI app swaps women into porn videos with a click

Deepfake researchers have long feared the day this would arrive.

Death and Jeff Bezos
Death and Jeff Bezos

Meet Altos Labs, Silicon Valley’s latest wild bet on living forever

Funders of a deep-pocketed new "rejuvenation" startup are said to include Jeff Bezos and Yuri Milner.

surgery
surgery

A gene-edited pig’s heart has been transplanted into a human for the first time

The procedure is a one-off, and highly experimental, but the technique could help reduce transplant waiting lists in the future.

Stay connected

Illustration by Rose WongIllustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.