7
$\begingroup$

There are two related but distinct parts to my question and I'm happy to hear perspectives on either:

  1. Any historical details, testimonies, papers that shed insight into what Lov Grover was working on which led him to think up his algorithm.

  2. What sorts of ideas must be one be playing with from which the idea of Grover's algorithm somewhat naturally arises.

$\endgroup$
2

1 Answer 1

7
$\begingroup$

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.

System moves towards lowest potential

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.

$\endgroup$
2
  • 2
    $\begingroup$ i do believe it's convention to include a short summary of a link, where the link is intended to be the answer $\endgroup$
    – somebody
    Feb 6, 2022 at 14:39
  • $\begingroup$ will edit my answer soon thanks $\endgroup$
    – shashvat
    Feb 6, 2022 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.