Sign In

Communications of the ACM

ACM TechNews

Data Structures Influence Speed of Quantum Search in Unexpected Ways

View as: Print Mobile App Share:
graph of data structure

Quantum search slows unexpectedly on the highly connected data structure represented by this graph.

Credit: UCSD

Although intuition says searching for data in a network would be fastest in a highly connected database, this logic does not hold for quantum computing, according to research by Tom Wong, who recently earned a Ph.D. in physics from the University of California, San Diego (UCSD) and is now at the University of Latvia, and UCSD professor David Meyer. The researchers used the example of searching for a particular cafe in a city. How quickly the cafe can be found depends on the layout of the city and the location of the cafe within the city.

Conventional logic says the more connected the city is, the easier it is to move around, and the easier it is to find the cafe. "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," Wong says. "The quantum world is much richer than our classical intuitions might lead us to believe."

From UC San Diego
View Full Article


Abstracts Copyright © 2015 Information Inc., Bethesda, Maryland, USA


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account