Grover’s Algorithm a Property of Nature?
An important quantum algorithm may actually be a property of nature
In brief…
+ 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.
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 results are eye-opening. The question they ask is how quickly an electron can find the hole in a grid. And the team’s big breakthrough is to show that these simulations reproduce the way real electrons behave in real materials.
+ In other words, this is evidence that free electrons naturally implement the Grover search algorithm when moving across the surface of certain crystals. That has immediate implications for quantum computing. “[This work] may be the path to a serious technological leap, whereby experimentalist would bypass the need for a full-fledged scalable and error-correcting Quantum Computer, and take the shortcut of looking for ‘natural occurrences’ of the Grover search instead,” say the team.
Content may have been edited for style and clarity.
