Practical 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.
Read more | Comments
No comments:
Post a Comment