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.

  • $\begingroup$ @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. $\endgroup$
    – hcl14
    Jun 21 '16 at 12:46
  • $\begingroup$ @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? $\endgroup$
    – hcl14
    Jun 21 '16 at 12:46
  • $\begingroup$ @DavidRicherby Ok, added the actual question after the emphasized statement. $\endgroup$
    – hcl14
    Jun 21 '16 at 20:48
  • $\begingroup$ 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! $\endgroup$
    – Raphael
    Jun 21 '16 at 20:53
  • $\begingroup$ Is this really a time-complexity question? Can anyone propose fitting tags? (cc @DavidRicherby) $\endgroup$
    – Raphael
    Jun 21 '16 at 20:54

Did you check if your oracle is unitary? All quantum operations, including the oracles used in Grover's algorithm, have to be unitary.

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.

Generally speaking, you need to be careful when adding together matrices to make quantum operations. If the matrices don't commute, weird things happen to the sum's eigendecomposition. If they do commute, you still might end up with eigenvalues that aren't on the complex unit circle. It's very easy to end up with a matrix that isn't unitary, and so doesn't correspond to a possible operation.

  • $\begingroup$ Thank you very much for your answer! I'm a beginner, so obviously I made a mistake using binomial decomposition for non-commuting matrices, and forgot to check whether the result is unitary. I'm still interested by the idea, so may be I can construct some specific working example in the future. $\endgroup$
    – hcl14
    Jun 21 '16 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.