Quantum Graph Search v. PageRank
In this article, the Google PageRank algorithm is discussed; in theory, it is simple to understand but in practice, it is a lot harder to implement. The article mentions some “crappy” graph explorations that end up being NP-hard, meaning that it is essentially unsolvable. However, physicists have discovered a method that involves quantum physics to improve on a strategy known as a random walk strategy, which means exploring the graph randomly. They use subatomic particles as “searchers” so that it is properly random and exploits interference effects between particles. However, they encountered a problem with unitarity, which sets a limit on how quantum systems can evolve over time. The evolution needs to happen symmetrically, which is a problem when examining directed graphs. Researchers instead work around it by exploiting a different kind of symmetry. They matched the performance of PageRank by evaluating the “centrality” of nodes in the graph, or how likely a random walker is to encounter the nodes in the graph. This resulted in the quantum walker being able to be faster than PageRank in some circumstances.
This post is interesting, because it discusses the PageRank of websites that we discussed in class. In class, we encountered a more simple definition and conceptual implementation of PageRank, so I can see how it would be much more difficult to apply it to the entire internet – there would be millions of pages that needed to be traversed and updated, all in the span of probably less than a second. While the article doesn’t touch much upon the specifics of how Google’s PageRank currently works, I like how the research steps towards a new method of trying to figure out how the pages are ranked. I would love to learn more about the details of the research, because I don’t understand how they take subatomic particles to find the page ranks, mainly because PageRank seems to be an algorithm and not something that can have a physical “subatomic walker” sent through. Additionally, the concept of unitarity is a topic I’d also like to know more about – how is the limit on quantum systems set, and what makes it so that there is a limit? I’d also like to understand more about how randomly walking can be faster than a PageRank algorithm; conceptually, it’s very different from walking through cycles and updating, as it’s mainly based on probability.