Accelerating Internet search with quantum computing



Researchers at the University of Southern California (USC) recently demonstrated how quantum computing could theoretically accelerate the way web page ranks are calculated.



”Most people don’t think twice about how Internet search engines work. You type in a word or phrase, hit enter, and poof – a list of web pages pops up, organized by relevance,” explained Daniel Lidar. “[But] behind the scenes, a lot of math goes into figuring out exactly what qualifies as most relevant web page for your search.”



For example, Google uses a page ranking algorithm that is rumored to be the largest numerical calculation carried out anywhere in the world. With the web constantly expanding, USC researchers envision quantum computers helping to speed up the process.


“This work is about trying to speed up the way we search on the web,” said Lidar. “As the Internet continues to grow, the time and resources needed to run the calculation – which is done daily – grow with it.”



As opposed to traditional computer bits, which can encode distinctly either a one or a zero, quantum computers use quantum bits or “qubits,” which can simultaneously encode a one and a zero. This property, known as superposition, will allow future quantum computers to perform certain calculations much faster than traditional systems.

Currently, there isn’t a quantum computer in the world capable of running Google’s page ranking algorithm for the entire web. To simulate how a quantum computer might perform, the researchers generated models of the web that simulated a few thousand web pages.

The simulation illustrated that a quantum computer could, in principle, return the ranking of the most important pages in the web faster than traditional computers, and that this quantum speedup would improve the more pages needed to be ranked. 



Further, the researchers showed that to simply determine whether the web’s page rankings should be updated, a quantum computer would be able to spit out a yes-or-no answer exponentially faster than a traditional computer.