Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:


New analysis eliminates a potential speed bump in quantum computing


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!

Further reports about: Defense Entanglement Physical Technology classical structures symmetric technique

More articles from Physics and Astronomy:

nachricht Stellar desk in wave-like motion
08.10.2015 | Max Planck Institute for Astronomy, Heidelberg

nachricht Mysterious ripples found racing through planet-forming disk
08.10.2015 | NASA/Goddard Space Flight Center

All articles from Physics and Astronomy >>>

The most recent press releases about innovation >>>

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

Im Focus: Reliable in-line inspections of high-strength automotive body parts within seconds

Nondestructive material testing (NDT) is a fast and effective way to analyze the quality of a product during the manufacturing process. Because defective materials can lead to malfunctioning finished products, NDT is an essential quality assurance measure, especially in the manufacture of safety-critical components such as automotive B-pillars. NDT examines the quality without damaging the component or modifying the surface of the material. At this year's Blechexpo trade fair in Stuttgart, Fraunhofer IZFP will have an exhibit that demonstrates the nondestructive testing of high-strength automotive body parts using 3MA. The measurement results are available in a matter of seconds.

To minimize vehicle weight and fuel consumption while providing the highest level of crash safety, automotive bodies are reinforced with elements made from...

Im Focus: Kick-off for a new era of precision astronomy

The MICADO camera, a first light instrument for the European Extremely Large Telescope (E-ELT), has entered a new phase in the project: by agreeing to a Memorandum of Understanding, the partners in Germany, France, the Netherlands, Austria, and Italy, have all confirmed their participation. Following this milestone, the project's transition into its preliminary design phase was approved at a kick-off meeting held in Vienna. Two weeks earlier, on September 18, the consortium and the European Southern Observatory (ESO), which is building the telescope, have signed the corresponding collaboration agreement.

As the first dedicated camera for the E-ELT, MICADO will equip the giant telescope with a capability for diffraction-limited imaging at near-infrared...

Im Focus: Locusts at the wheel: University of Graz investigates collision detector inspired by insect eyes

Self-driving cars will be on our streets in the foreseeable future. In Graz, research is currently dedicated to an innovative driver assistance system that takes over control if there is a danger of collision. It was nature that inspired Dr Manfred Hartbauer from the Institute of Zoology at the University of Graz: in dangerous traffic situations, migratory locusts react around ten times faster than humans. Working together with an interdisciplinary team, Hartbauer is investigating an affordable collision detector that is equipped with artificial locust eyes and can recognise potential crashes in time, during both day and night.

Inspired by insects

Im Focus: Physicists shrink particle accelerator

Prototype demonstrates feasibility of building terahertz accelerators

An interdisciplinary team of researchers has built the first prototype of a miniature particle accelerator that uses terahertz radiation instead of radio...

Im Focus: Simple detection of magnetic skyrmions

New physical effect: researchers discover a change of electrical resistance in magnetic whirls

At present, tiny magnetic whirls – so called skyrmions – are discussed as promising candidates for bits in future robust and compact data storage devices. At...

All Focus news of the innovation-report >>>



Event News

EHFG 2015: Securing healthcare and sustainably strengthening healthcare systems

01.10.2015 | Event News

Conference in Brussels: Tracking and Tracing the Smallest Marine Life Forms

30.09.2015 | Event News

World Alzheimer`s Day – Professor Willnow: Clearer Insights into the Development of the Disease

17.09.2015 | Event News

Latest News

Using optical fiber to generate a two-micron laser

09.10.2015 | Process Engineering

Sea turtles face plastic pollution peril

09.10.2015 | Ecology, The Environment and Conservation

Antioxidants cause malignant melanoma to metastasize faster

09.10.2015 | Health and Medicine

More VideoLinks >>>