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

Comments
Add comment

Your name:
Sign in with:
or
Your comment:


Enter code:

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


Last news

 
Consumer group recommends iPhone 8 over anniversary model
 
LTE connections wherever you go and instant waking should come to regular PCs, too
 
That fiction is slowly becoming a reality
 
The Snapdragon 845 octa-core SoC includes the Snapdragon X20 LTE modem
 
Human moderators can help make YouTube a safer place for everyone
 
Google says Progressive Web Apps are the future of app-like webpages
 
All 2018 models to sport the 'notch'
 
The biggest exchange in South Korea, where the BTC/KRW pair is at $14,700 now
The Samsung Galaxy A5 (2017) Review
The evolution of the successful smartphone, now with a waterproof body and USB Type-C
February 7, 2017 /
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

 
 
SuMoTuWeThFrSa
     12
3456789
10111213141516
17181920212223
24252627282930
31      




Poll

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