Google's PageRank could get a boost from quantum computing

Google logoPractical quantum computers don't exist yet, but if they did, could they solve the problem of searching the Web? A particularly challenging problem in finding content is ranking the results: determining which page out of the plethora is most relevant to the search terms, and which sources are most likely to be reliable. One familiar algorithm for this is Google's PageRank, which is (obviously) computationally expensive; it is impossible with current technology to extend it to the whole Web.

In a recent paper in Physical Review Letters, Silvano Garnerone, Paolo Zanardi, and Daniel A. Lidar proposed a quantum algorithm encoding the same information as PageRank. Quantum computing is based on the principle of entanglement: the possible binary states (quantum bits, or qubits) are simultaneously encoded. The authors caution that even their algorithm—or any quantum algorithm—will probably offer no speedup over current classical algorithms if the entire Web is simulated. However, in the case of specific network connection topologies, the quantum algorithm offers a potentially significant improvement over current search strategies.

The particular connection topologies the authors considered in this paper were the sparse and small-world networks; the latter is the basis for the "Six Degrees of Separation" (or Kevin Bacon) game. Using their quantum algorithm, the researchers found a significant (polynomial) speed up when the number of connections each node possesses was small, compared to the classical PageRank algorithm.

While they don't provide a proof of this assertion, they believe it is the topologies that allowed the speed-up to happen. Small-world or sparse networks do correspond to the Web as it is—not every page connects to every other, and there are a few islands of nodes that connect only to each other—so arguably there are other advantages to the quantum PageRank algorithm, beyond being quantum. And maybe in the future Wikipedia won't be the first hit for quantum computing information.

Source: Ars Technica

Tags: Google, search, technologies

Add comment

Your name:
Sign in with:
Your comment:

Enter code:

E-mail (not required)
E-mail will not be disclosed to the third party

Last news

A mobile hotspot in Australia will be capable of hitting gigabit speeds on the go
A new game could be in the works as Blizzard appears to have been hiring for a Diablo-related project
Nokia CEO Rajeev Suri will speak at MWC 2017
However what if you could go way, way back?
The Helio P15 packs an octa-core Cortex-A53 processor clocked at 2.2GHz
Samsung claims up to 27-percent higher performance or 40-percent lower power
Preliminary data for October shows another Windows 10 boom
Samsung Galaxy TabPro S - a tablet with the Windows-keyboard
The first Windows-tablet with the 12-inch display Super AMOLED
June 7, 2016 /
Keyboards for iOS
Ten iOS keyboards review
July 18, 2015 /
Samsung E1200 Mobile Phone Review
A cheap phone with a good screen
March 8, 2015 / 4
Creative Sound Blaster Z sound card review
Good sound for those who are not satisfied with the onboard solution
September 25, 2014 / 2
Samsung Galaxy Gear: Smartwatch at High Price
The first smartwatch from Samsung - almost a smartphone with a small body
December 19, 2013 /
HP Slate 7 is a 7-inch Android 4 Tablet PC with good sound
A cost-effective, 7-inch tablet PC from a renowned manufacturer
October 25, 2013 / 4

News Archive



Do you use microSD card with your phone?
or leave your own version in comments