Science News
from research organizations

Data structures influence speed of quantum search in unexpected ways

Date:
March 17, 2015
Source:
University of California - San Diego
Summary:
Quantum computers will be able to find target items within large piles of data far faster than conventional computers though the speed of the search will likely depend on the structure of the data. Intuition says that the search would be fastest in a highly connected database, but a new analysis found counterexamples of slowed search on a highly connected structure and fast search on a sparsely connected one.
Share:
FULL STORY

Quantum search slows unexpectedly on the highly connected data structure represented by this graph. Mathematical description: a 5-simplex with each vertex replaced with a complete graph of 5 vertices.
Credit: Tom Wong

Using the quantum property of superposition, quantum computers will be able to find target items within large piles of data far faster than conventional computers ever could. But the speed of the search will likely depend on the structure of the data.

Such a search would proceed as a quantum particle jumps from one node of a connected set of data to another. Intuition says that the search would be fastest in a highly connected database.

"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," said 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 by Physical Review Letters on March 20, David Meyer, a professor of mathematics at the University of California, San Diego, and 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," Wong said. "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."


Story Source:

Materials provided by University of California - San Diego. Original written by Susan Brown. Note: Content may be edited for style and length.


Journal Reference:

  1. David A. Meyer, Thomas G. Wong. Connectivity is a Poor Indicator of Fast Quantum Search. Physical Review Letters, 2015; 114 (11) DOI: 10.1103/PhysRevLett.114.110503

Cite This Page:

University of California - San Diego. "Data structures influence speed of quantum search in unexpected ways." ScienceDaily. ScienceDaily, 17 March 2015. <www.sciencedaily.com/releases/2015/03/150317152446.htm>.
University of California - San Diego. (2015, March 17). Data structures influence speed of quantum search in unexpected ways. ScienceDaily. Retrieved May 23, 2017 from www.sciencedaily.com/releases/2015/03/150317152446.htm
University of California - San Diego. "Data structures influence speed of quantum search in unexpected ways." ScienceDaily. www.sciencedaily.com/releases/2015/03/150317152446.htm (accessed May 23, 2017).

RELATED STORIES