Synopsis: Ranking Web Sites Quantum Mechanically

Quantum computing could be used to efficiently rank internet sites, according to a theoretical proposal.
Synopsis figure
APS

Although quantum computing has only been demonstrated for small calculations so far, researchers are interested in finding problems where its potentially massive parallelism would pay off if scaled-up versions can be made. In Physical Review Letters, Silvano Garnerone of the Institute for Quantum Computing at the University of Waterloo, Canada, and colleagues simulate the speedup achieved by using a quantum approach to rank websites.

The PageRank method, implemented by Google, assigns each website a score based on how many other sites link to it and what their scores are. Starting with an enormous matrix that represents which sites link to which others, the algorithm evaluates the probability that a steady stream of surfers starting at random sites and following random links will be found at each site. This information helps determine which search results should be listed highest. The PageRank calculation currently requires a time that is roughly proportional to the number of sites. This slowdown with size is not as bad as for many complex problems, but it can still take many days to rank the entire worldwide web.

Garnerone and colleagues propose an approach to page ranking that uses an “adiabatic quantum algorithm,” in which a simple matrix with a known solution is gradually transformed into the real problem, producing the desired solution. They simulated many relatively small networks that had similar link topology to the worldwide web, and found that reconstructing and reading out the most relevant part of the PageRank required a time that grows more slowly than the best classical algorithms available. – Don Monroe


Announcements

More Announcements »

Subject Areas

Quantum Information

Previous Synopsis

Next Synopsis

Materials Science

An Army of Computing Power

Read More »

Related Articles

Synopsis: All-Around Single-Photon Source
Quantum Information

Synopsis: All-Around Single-Photon Source

A quantum dot embedded in a micropillar is an efficient source of pure and indistinguishable single photons. Read More »

Focus: Burglar Alarm Based on Quantum Mechanics
Quantum Information

Focus: Burglar Alarm Based on Quantum Mechanics

Researchers demonstrated a scheme that relies on quantum mechanics to prevent unauthorized access to restricted objects, such as nuclear materials. Read More »

Viewpoint: Closing the Door on Einstein and Bohr’s Quantum Debate
Optics

Viewpoint: Closing the Door on Einstein and Bohr’s Quantum Debate

By closing two loopholes at once, three experimental tests of Bell’s inequalities remove the last doubts that we should renounce local realism. They also open the door to new quantum information technologies. Read More »

More Articles