Grover's Search Algorithm

We are given some

Define

In fact, instead of using , use a related

We want to find quickly. Also let

Setup

Start with

where Consider acting on it by Grover iteration operator

Some facts to be proven

In the plane spanned by and causes a rotation through an angle where

In the space normal to this one,

So hopefully by rotating enough, we will get a state that’s close to For large , the starting angle between and will be also so we need to rotate approximately Thus queries suffice.