Google and NASA team up for Quantum Computing
Researchers have found that global symmetry is not required to speed up quantum searches Mashable

Researchers have proved that global symmetry is not required in order for a quantum particle to search quickly for an item in a database.

Grover's quantum search algorithm can be formulated as quantum particles having the ability to search for items in an unsorted database by jumping from one node to another, making quantum computing work much faster than traditional computers can.

However, the assertion has always assumed that quantum particles can only hop directly from one item to another, meaning that a quantum computer's ability to search for items depends on what items the particle hops onto.

Researchers from the KTH Royal Institute of Technology in Sweden and the University of California San Diego have used a physics technique known as the "degenerate perturbation theory" to prove that searches can still be sped up without the use of global symmetry.

If you were to represent the database that needs to be searched as a graph, then in globally symmetric graphs, nodes can be swapped with each other such that the connections between each node are preserved.

Graphs that Describe Database Architectures
Tom Wong, UC San Diego

In a complete graph (above left), every node is connected to every other, yet, in other well studied graphs such as the Paley graph in the centre and the Latin square graph on the right, this is not true.

A quantum particle could hop directly to the target position, in red, only from connected nodes, marked in blue.

However, "strongly regular graphs" do not share this property.

"Using degenerate perturbation theory, we show that quantum random walk search on known families of strongly regular graphs nevertheless achieves the full quantum speedup of Θ(N−−√), disproving the intuition that fast quantum search requires global symmetry," the authors Jonatan Janmark, David A. Meyer, Thomas G. Wong explain in their paper.

The researchers' findings extend the use of the degenerate perturbation theory to the field of quantum information science, expanding the kind of data structures on which quantum computing is able to outperform classical computing.

The study entitled, "Global Symmetry is Unnecessary for Fast Quantum Search" has been accepted for publication in the journal Physical Review Letters.