"Say we are searching for a particular cafe in a city. How quickly we find it can depend on the layout of the city and the location of the cafe within the city. We might imagine that the more connected the city is, the easier it is to move around, and the easier it is to find the cafe", stated Tom Wong, one of the authors of a new analysis of the speed of such a search on databases with different structures and degrees of connectivity.
In a paper published byPhysical Review Letterson March 20, David Meyer, a professor of mathematics at the University of California, San Diego, and Tom Wong, who recently earned a Ph.D. in physics from UC San Diego and is now at the University of Latvia, showed that this logic doesn't hold for quantum computing.
"We turned an intuition on its head", Tom Wong stated. "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."
This work was partially supported by the Defense Advanced Research Projects Agency's Quantum Entanglement Science and Technology programme, the Air Force Office of Scientific Research's Transformational Computing in Aerospace Science and Engineering Initiative, and the Achievement Awards for College Scientists Foundation.