I have a question about an inductive proof. First of all, let me explain the problem.
The algorithm starts in $|\psi\rangle$ and applies $O_x$ $k$-times, with some unitary operators. We now define:
$$O_x=I-2|x\rangle\langle x|$$ $$|\psi_k^x\rangle=U_kO_xU_{k-1}O_x...U_1O_x|\psi\rangle$$ $$|\psi_k\rangle=U_kU_{k-1}...U_1|\psi\rangle$$ $O_x$ is an oracle operator which gives a phase shift -1 to the solution $|x\rangle$
$D_k$ is defined as a deviation after $k$ steps:
$$D_{k}=\sum_x |||\psi_k^x\rangle-|\psi_k\rangle||^2$$
With a proof it should now be shown that $D_k$ is restricted and can not grow fatser than $O(k^2)$. Now we come to the actual problem.
I am interested in the proof of some points:
- Why does it have to be shown that $D_k$ is limited?
- Why must it be shown that $D_k$ does not grow faster than $O(k^2)$? What is the idea behind it?
- In the second proof it is to be assumed that $D_k\Omega(N)$ holds, why is that exactly important? Which statement is behind it?
If someone needs more information, I have a helpful PDF HERE. Otherwise, I can also give more information.
I hope the question is understandable. It would be very nice if someone could explain to me what the ideas behind it are.