Quantum Search

This post is a follow-on to the post on the reflection trick in quantum computing. The recipe that we will learn hands-on in this post is again a viral trick that is used all over the place in quantum algorithms that rely on the query model of Boolean functions. The method will also give an alternate way to implement the operator $R$ in $HRH$ in the reflection part of Grover’s algorithm.

This hands-on post aimed at senior undergraduate and graduate students in CS illustrates the amplification trick due to Grover that is central to Quantum Search. Basic familiarity with python and linear algebra (tensor multiplication) is helpful to appreciate the trick and the construction of the quantum circuit. An understanding of Quantum Mechanics is not needed to understand and use Grover’s algorithm. The following beliefs are sufficient to appreciate the power of Quantum i) $n$ particle system keeps track of $N=2^n$ states in its belly, and ii) state changes can be accomplished efficiently by manipulating few particles (local changes) at a time.