Let be a set of inputs to some function . Out of these inputs, inputs are solutions. We define if is a solution, and otherwise. Assume we have an oracle that applies this function
If we take , then . Abstractly, we can say .
Prepare the initial state into the -fold superposition . A Grover iteration is given by
Mean Inversion Operator
Info
Applying to produces , where .
Analysis
Let be the solutions to the search problem, and be non-solutions. Additionally, write the following states
Here, we can view the oracle as a reflection in the space spanned by , . The superposition can be rewritten , thus the mean inversion operator is a reflection about in this space. Let where . Thus , and in general .
The angle between and is , while applying a Grover iteration rotates the state radians. Thus rotating by takes us within of , so . If , then , giving a nice bound . If this is not the case, we are better of simply guessing randomly. If we don’t know which case is true ahead of time, there is a solution counting algorithm (TODO)
