Photo By Suzanne William For Unsplash
Finding the shortest path or the most optimised path is prevalent in biological systems. Ants dont 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:
Imagine a phone directory containing N names arranged in a completely random order. In order to find someones 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. Grovers algorithm is within a small constant factor, was considered to be the fastest possible quantum mechanical algorithm back then.
Grovers 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 didnt appear until 2017.
Today, a team of researchers from France say they have evidence that Grovers search algorithm is a naturally occurring phenomenon. They claim to have observed this behaviour in electrons.
Grovers search algorithm can be reformulated in a variety of ways. One of these is as a quantum walk across a surfacethe 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 teams big breakthrough is to show that these simulations reproduce the way real electrons behave in real materials.
The researchers at Universite 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 Grovers 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 couldnt 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 Grovers algorithm at work !
Read the original paper here.
comments
Original post:
A New Perspective On Grover's Search Algorithm -- Quantum Physics & DNA - Analytics India Magazine