Quantum Search
This week brought us extraordinary news confirming that Nature appears to utilize a special kind of quantum search algorithm. The Grover's search algorithm, when utilized by quantum computing systems, has the ability to almost immediately find what it is looking for. It is able to do so because it undergoes coherent evolution, such that it elegantly and efficiently hones in exactly on the answer (or answers) being sought.
Physicist Lov Kumar Grover was employed as a quantum physicist at Bell Labs in New Jersey in 1996, when he noticed an algorithm that could utilize special properties of quantum physics to more quickly find a target solution in the fewest possible search steps.
David Deutsch provides wonderfully informative descriptions of key elements of quantum computation a series of lectures at Clarendon Laboratory at the University of Oxford, including a detailed description of Grover's Search Algorithm. David describes how there exists a ‘marking operation' that marks the target (answer) term in the quantum superposition state by changing its sign (described at 12:31 in the video). Deutsch describes how the Grover's algorithm when utilized by quantum systems can search through a million possibilities in only about a thousand iterations, or search through one trillion possibilities in just a million iterations. And most spectacularly, the Grover's search only exactly hits the sought-after target state only when N equals four, so that a single Oracle call of the Grover's search algorithm is enough to do the whole search (21:57). The Oracle version of the Grover's algorithm searching task has proven itself to be optimal–to be the fastest algorithmic search possible when compared with all other possible classical and quantum search algorithms.
Quickly finding Holes in the Grid
Stephane Guillet and colleagues at the University of Toulon in France have found evidence for the Grover search as a naturally occurring phenomenon, and provide the first evidence that electrons may naturally behave like a Grover search, seeking out defects in a material. Grover's search algorithm can be reformulated as a kind of quantum walk across a given surface, conducting a search across a two-dimensional plane, and doing so much more quickly than a classical search. Guillet's team simulated Grover's searches for electrons that were exploring triangular and square grids. With square grids, electrons could choose between four different directions, and within triangular grids, electrons select between three different options. Guillet's team also included defects in these grids, in the form of holes, and also quantum interference effects, all the while testing to see how quickly an electron could find a hole in the grid.
One giant breakthrough in Guillet's team's work is that they might just have found the process used by electrons in real life, moving across crystals in the real world. If free electrons implement something like the Grover search algorithm, scientists can bypass the need for developing fully error-correcting quantum computers, and follow the shortcut of finding places in Nature where the Grover search naturally occurs.
Searching the Genetic Code
Amazingly, the genetic DNA code utilized by every creature on our family tree of plants and animals is based on four nucleotide bases. These nucleotides (G, C, A, and T) encode information for constructing proteins from 20 amino acids. Researcher Apoorva Patel at the Indian Institute of Science in Bangalore described how Grover's algorithm could explain the significance of four nucleotide bases and 20 amino acids in the paper, Quantum Algorithms and the Genetic Code. Patel showed that four is the optimal number for Nature to work with, such that the difference between four alternatives can be determined in a single step, utilizing Grover's algorithm in a quantum process. And choosing which amino acid is best from 20 possibilities can be quickly determined in a three-step quantum search. It turns out that four nucleotide bases and 20 amino acids are the optimal numbers in order to ensure optimal efficiency in assembling DNA and proteins, provided the search operations are quantum–and not classical.
Quantum Processes are Nature's Way
With an ever-increasing body of evidence, we are starting to see that not only can quantum processes occur in warm, wet, noisy natural settings such as biological systems, they likely play pivotal, dominant roles. We are at a juncture at the dawning of this new Quantum Age where we are privileged to see how quantum logic and quantum processes provide optimal solutions. And on some very deep level, we are already intuitively attuned to recognizing and appreciating such things as quantum search.
I invite you to watch the companion video to this blog post at:
___________________________