# A question on the power of the operator in Grover's quantum algoritm

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.

• @DavidRicherby The question was about the possibility to use the precomputed power of the operator, I have marked the actual statement with the bold font. I thought this is not the first time this question appears, so I expected it to be well familiar to the community members. I have also provided my attempt to construct the working example (thanks to CraigGidney's I understand now why it is erroneous, however the question whether such example can be constructed is still open for me). I'm sorry if something looks unclear in my question, I'll try to be more precise next time. Jun 21, 2016 at 12:46
• @DavidRicherby P.S. I suppose it is normal to post here a question asking to check the correctness of the approach or constructed quantum algorithm? Jun 21, 2016 at 12:46
• @DavidRicherby Ok, added the actual question after the emphasized statement. Jun 21, 2016 at 20:48
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Jun 21, 2016 at 20:53
• Is this really a time-complexity question? Can anyone propose fitting tags? (cc @DavidRicherby)
– Raphael
Jun 21, 2016 at 20:54

For example, every row should be perpendicular to every other row. When I compute the dot product of two rows from your $U^k$ I don't get 0, so I don't think the rows are mutually perpendicular like they need to be.