Physicists Designed a Quantum Graph Search Technique That Matches Google

Google search relies on an algorithm known as PageRank. It's fairly easy to understand in principle, but implementing it is another matter. Figuring out how to search through all of the internet's pages is a hard problem, generally. Evaluating websites for the purposes of search means evaluating them within the context of graph data structures, where entities like webpages are represented by nodes, and the relationships between those webpages are represented by edges connecting them.

Some "naive" (read: crappy) graph exploration algorithms rise to the level of NP-hard, a class of computational complexity encompassing problems that are likely unsolvable by even the most powerful computers that exist or will exist. Given some arbitrary unexplored graph, it's just plain difficult to know the most efficient way to visit all of the nodes and links. As it turns out, we might as well explore the graph randomly, in the form of what's known as a "random walk."

The random walk method lets the search algorithm account for unusual geometric features of the graph, which might trip up a more directed search. Now, physicists have come up with a method that exploits quantum physics to improve on the class random walk strategy, as described in a recent paper published in the journal Physical Review A. By enlisting subatomic particles as the "searchers," the researchers made it possible to explore the graph in a way that is both properly random and that exploits interference effects between the particles. In other words, the searchers can be both random, and be aware of the larger search context.

Exploiting quantum effects in the interest of randomization is pretty obvious, since the quantum world is all about randomness. That is, it's all about uncertainty, or having incomplete information. It turns out there's a problem in using quantum effects for graph search, however. This is called unitarity, a principle that sets a limit on how quantum systems can evolve over time. Basically, this evolution needs to happen symmetrically, which limits the sorts of graphs that can be explored using quantum particles. If the links between nodes are bidirectional, we say that the graph is undirected; otherwise, it's a directed graph. Directed graphs are the problem.

The physicists behind the paper were able to come up with a clever fudge that allowed them to maintain this unitarity restriction by exploiting a different kind of symmetry having do with how the parity of a quantum system evolves over time. The upshot is that they could exploit quantum effects in the service of searching directed graphs. In experiments, they were able to match the performance of PageRank in evaluating the "centrality" of nodes in a graph, which can be thought of as a measure of how likely a random walker is to encounter those nodes as it explores the graph.

In some metrics, the quantum method was able to beat PageRank, such as in identifying equivalent sets of nodes within a graph. That said, there's more work to be done in even understanding how the quantum walker operates.