I'm new to quantum computing, so while studying Grover's algorithm I (and, I think a lot of other people too) could not help but notice that exactly the same operator is applied $\sqrt{N}$ times:
$$U = [2 \left| \psi \right> \left<\psi \right| - I ]\mathcal{O} $$
Of course, it depends on the oracle $\mathcal{O}$ and, as far as I understood from David Roberts' comment in this discussion on mathoverflow
More specifically, $U$ depends on $\left| \psi \right>$ (and $N$, but that's a bit different) which is not always in the same relation to $\left| E \right>$ in different concrete instances of the problem. Also, complexity is roughly an asymptotic measure, taken at worst case.
which (I think) means that in real tasks $\left| \psi \right>$ can be not equal superposition of states.
However, I don't see any prohibition here about $U^k$ ($k \in \mathbb{N}$, for example $k = [\sqrt{N}]+1$) be constructed previously for some specific range of tasks.
So, my question is whether it is theoretically possible to obtain the short form for $U^k$ and apply a single operator instead of applying $U$ up to $\sqrt{N}$ times? May be it is impossible in general because of just analytic difficulties, but we can construct the operator $U^k$ for some specific example that allows simplification?
To illustrate my point of view, I theorized about the following problem: Suppose I want to compute my function $f(x)$ on some grid with $N_1$ points and find whether $f(x)=a$ somewhere, if not - I will try bigger grid $N_2>N_1$. Suppose I can efficiently construct an oracle $\mathcal{O}$ for this for any $N$.
My $\left| \psi \right>$ is an equal superposition of states:
$$ \left| \psi \right> = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\left| x \right>$$
I'll switch to the pure linear algebra, limiting to $4\times 4$ for simplicity:
$$\frac{1}{N}A := \left| \psi \right> \left<\psi \right| = \frac{1}{N}\begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix} $$
I will define $\tilde{I}$ - matrix representation of some arbitrary realization of oracle, e.g.
$$\tilde{I} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$
Let also denote
$$\tilde{A} = A\tilde{I} = \begin{bmatrix} 1 & -1 & 1 & 1\\ 1 & -1 & 1 & 1 \\ 1 & -1 & 1 & 1 \\ 1 & -1 & 1 & 1 \end{bmatrix} $$
and notice that for $N=4$: $ \ \tilde{A}^k = 2^{k-1}\tilde{A} $ (for $N=5$ we have $3^{k-1}$).
Now we can compute:
$$U^k = ((\frac{2}{N}A - I)\tilde{I})^k = (\frac{2}{N}\tilde{A} - \tilde{I})^k = /\text{binomial theorem} / =$$ $$= \frac{2^k}{N^k}\tilde{A}^k+...+\begin{pmatrix}k \\ i\end{pmatrix}\frac{2^i}{N^i}\tilde{A}^i(-1)^{k-i}\tilde{I}^{k-i}+...+(-1)^k\tilde{I}^k=/\text{power of $\tilde{A}$}/=$$ $$=\frac{2^k}{N^k}2^{k-1}\tilde{A}+...+\begin{pmatrix}k \\ i\end{pmatrix}\frac{2^i}{N^i}2^{i-1}\tilde{A}(-1)^{k-i}\tilde{I}^{k-i}+...+(-1)^k\tilde{I}^k=/\text{$\tilde{A}=A\tilde{I}$}/= $$ $$=A\big(\frac{2^k}{N^k}2^{k-1}\tilde{I}+...+\begin{pmatrix}k \\ i\end{pmatrix}\frac{2^i2^{i-1}}{N^i}(-1)^{k-i}\tilde{I}^{k-i+1}+...+\begin{pmatrix}k \\ 1\end{pmatrix}(-1)^{k-1}2\tilde{I}^k\big)+(-1)^k\tilde{I}^k=$$ $$=\frac{1}{2}A\big(\frac{4}{N}I - \tilde{I}\big)^k\tilde{I} -A(-1)^k\tilde{I}^{k+1}+(-1)^k\tilde{I}^k =\frac{1}{2}A\big(\frac{4}{N}I - \tilde{I}\big)^k\tilde{I}+(-1)^k(I-A\tilde{I})\tilde{I}^k.$$
The matrices raised to power $k$ are just diagonal matrices based on the oracle and I think it is possible to implement them if we can implement the oracle itself. Since $\tilde{I}$ is arbitrary realization of the oracle, we can switch back to the "quantum" formula:
$$U^k =\frac{N}{2}\left| \psi \right> \left<\psi \right|\big(\frac{4}{N}I - \mathcal{O}\big)^k\mathcal{O}+(-1)^k(I-N\left| \psi \right> \left<\psi \right|\mathcal{O})\mathcal{O}^k = $$ $$=\frac{N}{2}\left| \psi \right> \left<\psi \right|\mathcal{O}'\mathcal{O}+(-1)^k(I-N\left| \psi \right> \left<\psi \right|\mathcal{O})\mathcal{O}'' $$
Thus we have much lesser structure to implement that will give us result in a few steps, not $\sqrt{N}$ in this specific task. Even if I made a mistake in calculations, the simplification approach is clear.
