Finding the shortest path or the most optimised path is prevalent in biological systems. Ants don’t just fancy a random rendezvous in search for food. Many biological systems barring humans are quite efficient in the conservation of energy, in carrying out their routines. 

A close similarity can be found in the way computers work. The task can be as primitive as searching databases for telephone numbers or breaking cryptographic codes, the algorithms try to complete the task as quickly as possible. In fact, many algorithms, directly or indirectly, have taken inspiration from biological systems.

So, a task in the context of machines, is assessed for speed by counting the steps it takes to end. Computer scientists have always considered that a process takes around N steps because in the worst case, the last item on the list could be the one of interest.

However, Lov Grover, a physicist, showed in 1996, 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.

A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. 

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. 

In computational complexity theory, a problem is NP-complete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm.

More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time), such that the output for any input is “yes” if the solution set is non-empty and “no” if it is empty.

Amongst all quantum algorithms, the reasons to focus on the  Grover search are as follows:

• because of its remarkable generality, as it speeds up any brute force O(N) problem  into an O (√N) problem.  
• because  of its remarkable  robustness.

Imagine a phone directory containing N names arranged in a completely random order. In order to find someone’s phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names. 

Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. Grover in his paper proposes that by properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. 

As a result, the desired phone number can be obtained in only O(sqrt(N)) steps. Grover’s algorithm is within a small constant factor, was considered to be the fastest possible quantum mechanical algorithm back then.

A New Perspective On Grover’s Algorithm

Grover’s work was an important factor in preparing for the world of  quantum computing, which is still in its infancy.

The first quantum computer capable of implementing it appeared in 1998, but the first scalable version didn’t appear until 2017.

Today, a team of researchers from France say they have evidence that Grover’s search algorithm is a naturally occurring phenomenon. They claim to have observed this behaviour in electrons. 

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.

The team focused on simulating the way a Grover search works for electrons exploring triangular and square grids as shown above.

The objective of this study can be summarized as finding 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.

Implications Of These Findings

The researchers at Universit́e de Toulon based on their observations, say that free electrons naturally implement the Grover search algorithm when moving across the surface of certain crystals. This has immediate implications for quantum computing. For instance, this can be applied to solve correct the errors in a full-scale quantum computer.

The work also has implications for our thinking about the genetic code and the origin of life. Every living creature on Earth uses the same code, in which DNA stores information using four nucleotide bases. The sequences of nucleotides encode information for constructing proteins from an alphabet of 20 amino acids.

Back in 2000, Apoorva Patel of  IISc Bengaluru showed how Grover’s algorithm could explain the numbers 4 and 20. 

Patel showed that when there are four choices, a quantum search can distinguish between four alternatives in a single step. Indeed, four is optimal number.

However, biologists were dismissive of these results, saying that quantum processes couldn’t possibly be at work inside living things.

Now, these latest observations of the French researchers, can fortify two decades old observations of Patel and throw some light on how life itself finds a way.

A century ago, no would have believed that atoms can be manipulated to build computers and the algorithms designed to make these computers better  can be used to decode how life springs up. 

If this algorithm is really what the researchers say it is then we can safely assume that life is just an example of Grover’s algorithm at work !

Read the original paper here.