Ranking websites with a quantum speed-up
IQC researcher Silvano Garnerone co-authored a Physical Review Letters paper explaining a quantum speed-up to Google's system for ranking the importance of websites.
A research team including IQC postdoctoral fellow Silvano Garnerone has demonstrated a quantum speed-up to an important application — the algorithm used by Google to rank the importance of webpages.
Their result, published recently in Physical Review Letters, represents an important step in the development of quantum algorithms for quickly and efficiently retrieving useful information in a vast sea of data.
"We wondered if quantum computation could provide some speed-up in the evaluation of structural properties of complex networks," says Garnerone, who co-authored the paper with University of Southern California researchers Paolo Zanardi and Daniel A. Lidar.
"The PageRank algorithm, which is used by Google to rank the importance of webpages in the webgraph, was a perfect candidate problem to work on."
The team showed that a quantum adiabatic computation could be superior to the classical approach to estimate the most important part of PageRank.
Though the speed-up is not exponential (an advantage some quantum algorithms are known to provide), it is nonetheless a significant result.
"The World Wide Web is one of the most relevant instances of a complex network, and trying to find quantum algorithms that can outperform classical ones in this context will provide new motivations for quantum research," said Garnerone.
"In a world where the problem is not a lack of information, but rather a fast way to find useful information, these new algorithms will become more and more important."