@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 journalPhysical 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.
No comments:
Post a Comment