Global symmetry not required for fast quantum search
A quantum particle can search for an item in an unsorted "database" by jumping from one item to another in superposition, and it does so faster than a classical computer ever could.
In a complete graph (left) every node is connected to every other. For other well studied graphs, the Paley graph in the center and the Latin square graph on the right, that is not true. A quantum particle could hop directly to the target position, in red, only from connected nodes, marked in blue.
Credit: Tom Wong, UC San Diego
This assertion assumes, however, that the particle can directly hop from any item to any other. Any restriction on which items the particle can directly hop to could slow down the search.
"Intuition says that a symmetric database allows the particle to hop freely enough to retain the quantum speedup, but our research has shown this intuition to be false," says Tom Wong, a physicist at the University of California, San Diego.
In a paper accepted for publication by Physical Review Letters, the researchers used a technique familiar to physicists called "degenerate perturbation theory" in a novel way to prove that global symmetry is not required for a sped up search.
Information scientists represent the database to be searched as a graph. In globally symmetric graphs, the nodes can be swapped with each other such that the connections between them are preserved. "Strongly regular graphs" don't share this property, but this analysis shows they also support a fast search through local symmetries.
Their finding extends the use of this theory to the field of quantum information science and expands the kinds of data structures on which quantum computing outperforms classical computing.
Jonatan Janmark, KTH Royal Institute of Technology in Stockholm, Sweden and UC San Diego's Department of Mathematics and David Meyer, professor of mathematics at UC San Diego co-authored the work.
The Defense Advanced Research Projects Agency partially supported this work as part of its Quantum Entanglement Science and Technology program. Additional funding came from the Air Force Office of Scientific Research as part of the Transformational Computing in Aerospace Science and Engineering Initiative, and the Achievement Awards for College Scientists Foundation.
Tom Wong | Eurek Alert!
Theory of the strong interaction verified
27.03.2015 | Forschungszentrum Juelich
Dark matter even darker than once thought
27.03.2015 | ESA/Hubble Information Centre
In an experiment at the Department of Energy's SLAC National Accelerator Laboratory, scientists precisely measured the temperature and structure of aluminum as...
The IPH presents a solution at HANNOVER MESSE 2015 to make ship traffic more reliable while decreasing the maintenance costs at the same time. In cooperation with project partners, the research institute from Hannover, Germany, has developed a sensor system which continuously monitors the condition of the marine gearbox, thus preventing breakdowns. Special feature: the monitoring system works wirelessly and energy-autonomously. The required electrical power is generated where it is needed – directly at the sensor.
As well as cars need to be certified regularly (in Germany by the TÜV – Technical Inspection Association), ships need to be inspected – if the powertrain stops...
When an earthquake hits, the faster first responders can get to an impacted area, the more likely infrastructure--and lives--can be saved.
The Atlantic overturning is one of Earth’s most important heat transport systems, pumping warm water northwards and cold water southwards. Also known as the Gulf Stream system, it is responsible for the mild climate in northwestern Europe.
Scientists now found evidence for a slowdown of the overturning – multiple lines of observation suggest that in recent decades, the current system has been...
Because they are regularly subjected to heavy vehicle traffic, emissions, moisture and salt, above- and underground parking garages, as well as bridges, frequently experience large areas of corrosion. Most inspection systems to date have only been capable of inspecting smaller surface areas.
From April 13 to April 17 at the Hannover Messe (hall 2, exhibit booth C16), engineers from the Fraunhofer Institute for Nondestructive Testing IZFP will be...
25.03.2015 | Event News
19.03.2015 | Event News
17.03.2015 | Event News
27.03.2015 | Agricultural and Forestry Science
27.03.2015 | Materials Sciences
27.03.2015 | Ecology, The Environment and Conservation