Why I’m Obsessed with Grover’s Algorithm
During the past months I’ve been obsessed with studying what some people call Quantum Computing Textbook Algorithms. These are a set of algorithms that often appear in introductory books to Quantum Computing. They are used in order to introduce some of the unique properties of the computational model and often start with Deutsch-Jozsa‘s Algorithm and go all the way down to explaining Shor’s factoring algorithm. They are all really interesting but there is one in particular that caught my attention right from the beginning: Grover’s Algorithm. What’s mysterious about this algorithm is that it is really tricky to reverse-engineer without going abstract. And so my obsession begins!
How does the Algorithm Work?
Grover’s algorithm is a great example of wave interference and phase manipulation and how can they lead to some interesting speed-ups.
I won’t go through a formal analysis around the implementation. Just a few bullet points.
- Prepare a superposition.
- Figure out a way to phase the elements you want to amplify in your solution.
- You can also do this with partial phase flips.
- Apply a layer of Hadamards to trigger interference.
- Adjust the interference pattern so that you get a set of phases that exactly encodes the states you want to apmlify
- This can be done by phasing the seed of the superpositon in step 1.
- Apply a final layer of Hadamards to trigger interference a second time and get the amplified states.
The whole tactic here is to take an interference pattern and tweak it so it gives us the output we want. That’s all there is. Any other geometrical and mathematical interpretation seems unnecessary.
Would it have been Possible for you to Discover it?
Was it first the math or the algorithm? This is a question we will never be able to answer: The mental process here is something really unique and personal to the author.
I truly believe you could’ve come up with it by yourself. You just need the right mindset and put the math aside for a moment. What are we coding with here? We are coding with interference and so we are designing patterns. A phase-flip here and a Hadamard there and you are good to go! The math is there to help you make sure the thing is solid.
