USC researchers Silvano Garnerone, Paolo Zanardi, and Daniel A. Lidar suggested a way that will allow quantum computers to speed up the ranking algorithm that is used now.
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.
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.