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

Scientists are finding signals of long covid in blood. They could lead to new treatments.

Faults in a certain part of the immune system might be at the root of some long covid cases, new research suggests.

Large language models can do jaw-dropping things. But nobody knows exactly why.

And that's a problem. Figuring it out is one of the biggest scientific puzzles of our time and a crucial step towards controlling more powerful future models.

OpenAI teases an amazing new generative video model called Sora

The firm is sharing Sora with a small group of safety testers but the rest of us will have to wait to learn more.

Google’s Gemini is now in everything. Here’s how you can try it out.

Gmail, Docs, and more will now come with Gemini baked in. But Europeans will have to wait before they can download the app.

Stay connected

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