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

Galaxy Note10 really is built around a 6.7-inch display
You may still be able to download your content
Facebook, Messenger and Instagram are all going away
Minimize apps to a floating, always-on-top bubble
Japan Display has been providing LCDs for the iPhone XR, the only LCD model in Apple’s 2018 line-up
The 2001 operating system has reached its lowest share level
The entire TSMC 5nm design infrastructure is available now from TSMC
The smartphone uses a Snapdragon 660 processor running Android 9 Pie
The Samsung Galaxy A5 (2017) Review
The evolution of the successful smartphone, now with a waterproof body and USB Type-C
February 7, 2017 / 2
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 /

News Archive



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