The Future of Web Search Is Quantum Computing
On September of this year, scientists of the University of Western Australia and of the Nanjing University were able to match and even beat Google’s PageRank algorithm. These physicists used the random walk method to explore graphs by exploiting quantum effects. The way they did it was that subatomic particles worked as the “searchers”. Therefore, the searchers had the ability to be random and to be aware of the larger search context, which improves on Google’s PageRank algorithm. However, the scientists encountered problems along the way. The unitary principle sets a limit on how quantum systems can evolve over time, which means that the can only evolve symmetrically. With undirected graphs this presents no issue, but directed graphs are another thing. They had to come up with a way to maintain the unitary principle that also let them search directed graphs. In the end, they managed to use a different kind of symmetry, one that used how the parity of quantum systems evolves over time. By doing this, the random walk was able to measure the “centrality” of nodes in a graph (how likely searchers are to encounter a specific node in a graph), which is similar to how PageRank counts the number of nodes that link to another node. In the end, this quantum method was able to match PageRank in many experiments, and, in some, it even beat it.
This experiment is really interesting to me since it combines the world of quantum physics with the world of computer science in order to try to improve an algorithm that we saw in class. As we know, all the webpages in the Internet constitute a network that can be represented as a directed graph. But it is not easy to analyze a graph as big as the web since it contains billions of different nodes. Google’s PageRank might be very useful in examples such as the ones that we studied during class, but it can fail in networks as big as the entire Internet. Users trust Google to give them the best webpages related to what they are looking for, but this is not what always happens. Sometimes, Google gives them a page that paid to be one of the “best results”, and other times Google fails to give them the page that was the true “best result”. It is amazing to think that sometime in the future PageRank might be replaced by a better way to search the web. But it is especially fascinating to think that this new way of searching the web might involve quantum computing.