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.