Quantum Computers Could Help Search Engines Keep Up With the Internet’s Growth
USC scientists demonstrate that quantum computing could speed up the way Web page ranks are calculated on the ever-expanding Internet.
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.
Behind the scenes, a lot of math goes into figuring out exactly what qualifies as most relevant Web page for your search. Google, for example, 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, researchers at USC have proposed — and demonstrated the feasibility of —using quantum computers to speed up that process.
“This work is about trying to speed up the way we search on the Web,” said Daniel Lidar, corresponding author of a paper on the research that appeared in the journal Physical Review Letters on June 4.
As the Internet continues to grow, the time and resources needed to run the calculation — which is done daily — grow with it, Lidar said.
Lidar, who holds appointments at the USC Viterbi School of Engineering and the USC Dornsife College of Letters, Arts and Sciences, worked with colleagues Paolo Zanardi of USC Dornsife and first author Silvano Garnerone, formerly a postdoctoral researcher at USC and now at the University of Waterloo, to see whether quantum computing could be used to run the Google algorithm faster.
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 encode a one and a zero at the same time. This property, called superposition, some day will allow quantum computers to perform certain calculations much faster than traditional computers.
Currently, there is no quantum computer in the world anywhere near large enough to run 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 showed 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.
This research was funded by a number of sources, including the National Science Foundation, the NASA Ames Research Center, the Lockheed Martin Corporation’s University Research Initiative program and a Google faculty research award to Lidar.
Related News Items
- In Memoriam: Richard F. Thompson, 84 September 20, 2014
- Converging Science and Engineering September 18, 2014
- Welcome New Faculty September 16, 2014
- Close Look at Baldwin Hills September 16, 2014
- Heidelberg Steers the Ship September 15, 2014
- Chilton Wins Marine Award September 10, 2014
- Whale Mating: In the Hips September 10, 2014
- A Lexicon of the Brain September 2, 2014
- Discovery in Helium Droplets August 28, 2014
- Dutch Lessons on GeoDesign July 31, 2014
- Where Earth and Life Sciences Merge July 24, 2014
- Manahan Named Honorary Fellow July 22, 2014
- World’s Most Influential Scientists July 17, 2014
- Kay Lab Creates First Vast Library of Master Genetic Switches in Plants July 17, 2014
- Helping Us Breathe Easier July 14, 2014
- Bonahon Named Simons Fellow July 8, 2014
- Arctic Fox, Woolly Rhino and Three-toed Horse June 17, 2014
- Hats Off to Dr. Research June 12, 2014
- Knot a Problem May 27, 2014
- Early CAREER Award May 27, 2014