Quantum Information Takes the Connectedness Out of Search

At the very deepest foundations of computer science, not very far above even basic computing architecture, are data structures. This is more than how information is stored, but how it's dealt with continually during the course of information processing. Crunching bits is one thing, but making that meaningful takes concepts like stacks, binary trees, maps, and on upwards to the internet's growing data representation of choice, JSON.

One might imagine that these structures would persist as computing advances from the world of classical physics to that of quantum physics. Take a basic network of nodes and connections. It would seem that regardless of whether the information medium is bits or qubits—which are the quantum version of bits, containing both 1s and 0s at the same time rather than one or the other—that the more connections such a web has between its branches and leaves, the easier it would be to find something in that tree.

Not so, according to researchers at the University of California, San Diego. In a new report to be published Thursday in the Physical Review Letters, the group, led by physicist and information scientist Tom Wong, found that in some quantum search operations the more connected a network is, the slower the search takes. Meanwhile, the less connected the structure was, the faster the search progressed.

Wong likens the problem to searching a city, where the more roads and sidewalks there are, the easier it is to get around the grid and the more territory can be covered faster. Makes sense. But in the quantum information world, it turns out to be quite wrong.

"We turned an intuition on its head," Wong offered in a statement. "Searching with a quantum particle, we showed the opposite, giving an example where searching in a city with low connectivity yields fast search, and an example where searching in a city with high connectivity yields slow search. Thus the quantum world is much richer than our classical intuitions might lead us to believe."

​​

In question are what are known as complete graphs. This is a form in graph theory in which every node (or vertex) within a given graph/structure is connected to every other node in the network by a single unique link. So, to get from one node to any other node is just one step. The usefulness of such an arrangement is obvious enough.

What Wong and his partner David A. Meyer found is that given a quantum particle traveling across a graph, it's enough for that graph to be a "strongly regular" graph instead, where rather than all pairs of points being connected, only some pairs are, as determined by a set of parameters. A Paley graph is one example of this, where whether or not a pair of points is connected is determined by a feature called "quadratic residue."

The main thing to understand is that the graph has a decent amount of connections, but it isn't complete. Starting at one node, we aren't guaranteed of a one-jump trip to some other node. If our city grid were a Paley graph, finding things should be slower.

If we were particles obeying the rules of quantum mechanics, however, we would have some extra talents. The main one is that we're not ever really in just a single location. If, as a particle, we were tasked with exploring some graph, we might start in a "superposition" of many different states, many different nodes, at one time. This is the benefit of existing as a wave rather than a single deterministic point.

This can be imagined in somewhat more reasonable terms—as being in many places at once isn't quite on—as a particle having the ability to jump from node to node randomly. In our city example, we could effortlessly tunnel through buildings.

The search can be then viewed as the evolution of the particle's wavefunction through time, where nodes are visited in a non-linear fashion, which just means that they aren't visited sequentially one by one. The upshot, Wong and Meyer write, is that, "completeness is not a requirement for fast nonlinear [quantum] search."

An open-access preprint version of the paper can be found at arXiv.