There are two related but distinct parts to my question and I'm happy to hear perspectives on either:
Any historical details, testimonies, papers that shed insight into what Lov Grover was working on which led him to think up his algorithm.
What sorts of ideas must be one be playing with from which the idea of Grover's algorithm somewhat naturally arises.
Lov Grover actually wrote a paper on how he came up with his search algorithm: https://arxiv.org/abs/quant-ph/0109116
There are three main sources of inspiration:
Firstly, he talks about how quantum systems just like classical ones "move" towards points with low potential. Such a system let to evolve "finds"/"searches" for the point with the lowest potential because after some time left for the system to evolve, that state accumulates more probability amplitude.
Second, he uses Schrodinger's equation but considers evolution for one infinitesimal amount of time and he also considers a quantum state over a finite set of points. He derives matrices whose effect is to evolve this quantum system for an infinitesimal amount of time where all of the finite set of points have the same potential, except one marked point with lower potential. He mentions Trotterisation, which is delightful because on reflection Grover's algorithm does indeed have that alternation of two unitary operators like a Trotter approximation.
Thirdly, he tries to find Unitary versions of his discretised evolution matrices. For a while in the explanation he goes "off road" to just think about the "diffusion" of amplitude towards the marked state in terms of matrices which are Markovian but not unitary. He later tries to find unitary approximations to these so that they can be implemented on a quantum computer.
I was motivated to read this paper to understand how we might discover new quantum algorithms. These might all be great techniques to find new quantum algorithms: 1) Physical inspiration, 2) Discretisation and 3) Unitarification.
