### Explore Technology

# An important quantum algorithm may actually be a property of nature

[ad_1]

Back in 1996, a quantum physicist at Bell Labs in New Jersey published a new recipe for searching through a database of *N* entries. Computer scientists have long known that this process takes around *N* steps because in the worst case, the last item on the list could be the one of interest.

However, this physicist, Lov Grover, showed how the strange rules of quantum mechanics allowed the search to be done in a number of steps equal to the square root of *N*.

That was a big deal. Searching databases is a foundational task in computer science, used for everything from finding telephone numbers to breaking cryptographic codes. So any speed-up is a significant advance.

Quantum mechanics provided an additional twist. At the time, Grover’s recipe was only the second quantum algorithm that had been proved faster than its classical counterpart. (The first was Peter Shor’s algorithm for factoring numbers, which he discovered in 1994.) Grover’s work was an important factor in preparing the way for the quantum computing revolution that is still ongoing today.

But despite the interest, implementing Grover’s algorithm has taken time because of the significant technical challenges involved. The first quantum computer capable of implementing it appeared in 1998, but the first scalable version didn’t appear until 2017, and even then it worked with only three qubits. So new ways to implement the algorithm are desperately needed.

Today Stéphane Guillet and colleagues at the University of Toulon in France say this may be easier than anybody expected. They say they have evidence that Grover’s search algorithm is a naturally occurring phenomenon. “We provide the first evidence that under certain conditions, electrons may naturally behave like a Grover search, looking for defects in a material,” they say.

That has obvious implications for quantum computing, but its real import may be much more profound. For some time, theorists have debated whether quantum search could explain one of the greatest mysteries about the origin of life. The idea that Grover searches occur in nature could finally solve the conundrum.

First some background. Because it is so fundamental, Grover’s search algorithm can be reformulated in a variety of ways. One of these is as a quantum walk across a surface—the way a quantum particle would move randomly from one point to another.

##### What is quantum communication?

Clearly, this process is a kind of search of two-dimensional space. But because a quantum particle can explore many paths at the same time, it is much faster than a classical search.

The nature of the surface has an important influence on the search. For example, one type of surface consists of a square grid where the quantum particle has four possible moves at each vertex.

But there are many other possible grids; a triangular one, for example, where the quantum particle has three choices at each vertex. “The triangular grid is of particular interest because of its resemblance to several naturally occurring crystal-like materials,” say Guillet and co.

The team focused on simulating the way a Grover search works for electrons exploring triangular and square grids, but they also included other physically realistic effects, such as defects in the grid in the form of holes, and quantum properties such as interference effects.