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.
This is the benefit of existing as a wave rather than a single deterministic point
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."
Complete graph. Image: Wiki
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.
Image: Paley Graph
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.