Sign In

Communications of the ACM

ACM News

Quantum Pagerank Algorithm Outperforms Classical Version

View as: Print Mobile App Share:
magnifying glass


Researchers from Complutense University of Madrid have developed a quantum version of Google's PageRank algorithm that outperforms the world's leading search engine.

The researchers, led by Giuseppe Paparo and Miguel Martin-Delgado, say they imagined a quantum page crawler wandering around the network along paths that connect one quantum node to the next. Although 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. The researchers then outlined an algorithm that will produce a ranking of pages at any given instant using these quantum probabilities. Their research is published as "Google in a Quantum Network."

In theory, the nature of the quantum algorithm produces results much faster than any traditional algorithm. With a tree graph, the quantum algorithm outperforms the classical algorithm in ranking the root page, but for other pages the quantum algorithm produces the same hierarchy as a classical network. The results are similar for a directed graph.

From Technology Review
View Full Article


Abstracts Copyright © 2011 Information Inc., Bethesda, Maryland, USA


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account