Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:


Data structures influence speed of quantum search in unexpected ways


Highly connected structures don't always support fastest quantum computing

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.

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

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."


This work was partially supported by the Defense Advanced Research Projects Agency's Quantum Entanglement Science and Technology program, the Air Force Office of Scientific Research's Transformational Computing in Aerospace Science and Engineering Initiative, and the Achievement Awards for College Scientists Foundation.

Media Contact

Susan Brown


Susan Brown | EurekAlert!

All articles from Information Technology >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: New 3-D wiring technique brings scalable quantum computers closer to reality

Researchers from the Institute for Quantum Computing (IQC) at the University of Waterloo led the development of a new extensible wiring technique capable of controlling superconducting quantum bits, representing a significant step towards to the realization of a scalable quantum computer.

"The quantum socket is a wiring method that uses three-dimensional wires based on spring-loaded pins to address individual qubits," said Jeremy Béjanin, a PhD...

Im Focus: Scientists develop a semiconductor nanocomposite material that moves in response to light

In a paper in Scientific Reports, a research team at Worcester Polytechnic Institute describes a novel light-activated phenomenon that could become the basis for applications as diverse as microscopic robotic grippers and more efficient solar cells.

A research team at Worcester Polytechnic Institute (WPI) has developed a revolutionary, light-activated semiconductor nanocomposite material that can be used...

Im Focus: Diamonds aren't forever: Sandia, Harvard team create first quantum computer bridge

By forcefully embedding two silicon atoms in a diamond matrix, Sandia researchers have demonstrated for the first time on a single chip all the components needed to create a quantum bridge to link quantum computers together.

"People have already built small quantum computers," says Sandia researcher Ryan Camacho. "Maybe the first useful one won't be a single giant quantum computer...

Im Focus: New Products - Highlights of COMPAMED 2016

COMPAMED has become the leading international marketplace for suppliers of medical manufacturing. The trade fair, which takes place every November and is co-located to MEDICA in Dusseldorf, has been steadily growing over the past years and shows that medical technology remains a rapidly growing market.

In 2016, the joint pavilion by the IVAM Microtechnology Network, the Product Market “High-tech for Medical Devices”, will be located in Hall 8a again and will...

Im Focus: Ultra-thin ferroelectric material for next-generation electronics

'Ferroelectric' materials can switch between different states of electrical polarization in response to an external electric field. This flexibility means they show promise for many applications, for example in electronic devices and computer memory. Current ferroelectric materials are highly valued for their thermal and chemical stability and rapid electro-mechanical responses, but creating a material that is scalable down to the tiny sizes needed for technologies like silicon-based semiconductors (Si-based CMOS) has proven challenging.

Now, Hiroshi Funakubo and co-workers at the Tokyo Institute of Technology, in collaboration with researchers across Japan, have conducted experiments to...

All Focus news of the innovation-report >>>



Event News

#IC2S2: When Social Science meets Computer Science - GESIS will host the IC2S2 conference 2017

14.10.2016 | Event News

Agricultural Trade Developments and Potentials in Central Asia and the South Caucasus

14.10.2016 | Event News

World Health Summit – Day Three: A Call to Action

12.10.2016 | Event News

Latest News

Resolving the mystery of preeclampsia

21.10.2016 | Health and Medicine

Stanford researchers create new special-purpose computer that may someday save us billions

21.10.2016 | Information Technology

From ancient fossils to future cars

21.10.2016 | Materials Sciences

More VideoLinks >>>