Data structures influence speed of quantum search in unexpected ways

March 17, 2015, University of California - San Diego
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 .

"We turned an intuition on its head," Wong said. "Searching with a , 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."

Both intuition and previous work seem to indicate that quantum searches will slow in sparsely connected data structures, like the one illustrated by this graph, but a new analysis shows the search for the "correct" node, marked in red, will proceed at optimum speed. Mathematical description: a graph with 12 vertices constructed by joining two complete graphs of six vertices by a single edge. Credit: Tom Wong

Explore further: New analysis eliminates a potential speed bump in quantum computing

Related Stories

New scheme for quantum computing

June 25, 2013

(Phys.org) —Tom Wong, a graduate student in physics and David Meyer, professor of mathematics at the University of California, San Diego, have proposed a new algorithm for quantum computing, that will speed a particular ...

The road to quantum computing

May 15, 2014

Anticipating the advent of the quantum computer, related mathematical methods already provide insight into conventional computer science.

Physicists find a new form of quantum friction

February 26, 2015

Physicists at Yale University have observed a new form of quantum friction that could serve as a basis for robust information storage in quantum computers in the future. The researchers are building upon decades of research, ...

Efficient distributed quantum computing

February 21, 2013

(Phys.org)—A quantum computer doesn't need to be a single large device but could be built from a network of small parts, new research from the University of Bristol has demonstrated. As a result, building such a computer ...

Recommended for you

Researchers turn light upside down

February 23, 2018

Researchers from CIC nanoGUNE (San Sebastian, Spain) and collaborators have reported in Science the development of a so-called hyperbolic metasurface on which light propagates with completely reshaped wafefronts. This scientific ...

Walking crystals may lead to new field of crystal robotics

February 23, 2018

Researchers have demonstrated that tiny micrometer-sized crystals—just barely visible to the human eye—can "walk" inchworm-style across the slide of a microscope. Other crystals are capable of different modes of locomotion ...

Recurrences in an isolated quantum many-body system

February 23, 2018

It is one of the most astonishing results of physics—when a complex system is left alone, it will return to its initial state with almost perfect precision. Gas particles, for example, chaotically swirling around in a container, ...

Seeing nanoscale details in mammalian cells

February 23, 2018

In 2014, W. E. Moerner, the Harry S. Mosher Professor of Chemistry at Stanford University, won the Nobel Prize in chemistry for co-developing a way of imaging shapes inside cells at very high resolution, called super-resolution ...

Hauling antiprotons around in a van

February 22, 2018

A team of researchers working on the antiProton Unstable Matter Annihilation (PUMA) project near CERN's particle laboratory, according to a report in Nature, plans to capture a billion antiprotons, put them in a shipping ...

3 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

quantome
1 / 5 (1) Mar 18, 2015
"We turned an intuition on its head,"

...Wouldn't intuition dictate the opposite: that a network with fewer connections is faster to search as the options to connect (ie Reed Law) are lower? A network full of pathways, even ones which are shortcuts, would take longer to optimize. In fact isn't this the whole nature of Quantum computing, that they can check all possibilities at once? It seems like the system they are testing isn't actually operating in a quantum way.

Also I should note, I don't understand quantum mechanics. And I didn't read the paper.
anastasios andronidis
not rated yet Mar 18, 2015
Hello, is there any link to the actual paper?
derphys
not rated yet Apr 13, 2015
Connectivity is a Poor Indicator of Fast Quantum Search
http://arxiv.org/...76v2.pdf
I agree with quantone that quantum waves in a low connected network have quite less destructive interferences and are thus quite less lost.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.