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.
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.
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.
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.
But why these numbers—four and 20—and not some others? Back in 2000, just a few years after Grover published his work, Apoorva Patel at the Indian Institute of Science in Bangalore showed how Grover’s algorithm could explain these numbers.
Patel’s idea is related to the way DNA is assembled inside cells. In this situation, the molecular machinery inside a cell must search through the molecular soup of nucleotide bases to find the right one. If there are four choices, a classical search takes four steps on average. So the machinery would have to try four different bases during each assembly step.
But a quantum search using Grover’s algorithm is much quicker: 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.
This thinking also explains why there are 20 amino acids. In DNA, each set of three nucleotides defines a single amino acid. So the sequence of triplets in DNA defines the sequence of amino acids in a protein.
But during protein assembly, each amino acid must be chosen from a soup of 20 different options. Grover’s algorithm explains these numbers: a three-step quantum search can find an object in a database containing up to 20 kinds of entry. Again, 20 is the optimal number.
In other words, if the search processes involved in assembling DNA and proteins is to be as efficient as possible, the number of bases should be four and the number of amino acids should to be 20—exactly as is found. The only caveat is that the searches must be quantum in nature.
When Patel published his idea, quantum physicists immediately pooh-poohed it. At the time, they were bogged down in their own attempts to control quantum processes, which they could do only by isolating quantum particles in extreme environments such as at temperatures close to absolute zero.
The obvious problem, they said, was that living things operate in a warm, messy environment in which quantum states would be immediately destroyed.
Biologists were equally dismissive, saying that quantum processes couldn’t possibly be at work inside living things.
Since then, an increasing body of evidence has emerged that quantum processes play an important role in a number of biological mechanisms. Photosynthesis, for example, is now thought to be an essentially quantum process.
The work of Guillet and co throws a new perspective on all this. It suggests that Grover’s algorithm is not only possible in certain materials; it seems to be a property of nature. And if that’s true, then the objections to Patel’s ideas start to crumble.
It may be that life is just an example of Grover’s quantum search at work, and that this algorithm is itself a fundamental property of nature. That’s a Big Idea if ever there was one.
This article was first published in MIT Technology Review
