Quantum algorithm

Question

Let's suppose that we have a quantum superposition state, and for a basis vector $|\Psi\rangle\in \mathcal{H}$,

$$|\psi\rangle = \frac{\sqrt{N-1}}{\sqrt{N}}|\Psi_c\rangle + \frac{1}{\sqrt{N}}|\Psi\rangle$$

Where $|\Psi_c\rangle$ is orthogonal quantum state to $|\Psi\rangle$.

And our unitary operators are:

$$U_{\Psi} = I-2|\Psi\rangle \langle\Psi|$$

$$U_{\psi} = -I+2|\psi\rangle\langle \psi|$$

Could we compute the explicit action of $(U_{\psi}U_{\Psi})(\psi) = U_{\psi}(U_{\Psi}(\psi))$ as follows?

$$\begin{align}U_{\Psi}\biggr(\frac{\sqrt{N-1}}{\sqrt{N}}|\Psi_c\rangle + \frac{1}{\sqrt{N}}|\Psi\rangle\biggr) = \biggr(I-2|\Psi\rangle \langle\Psi|\biggr)\biggr(\frac{\sqrt{N-1}}{\sqrt{N}}|\Psi_c\rangle + \frac{1}{\sqrt{N}}|\Psi\rangle\biggr) = |\psi\rangle -\frac{2||\Psi||^2}{\sqrt{N}}|\Psi\rangle\end{align}$$

$$U_{\psi}\biggr(|\psi\rangle -\frac{2||\Psi||^2}{\sqrt{N}}|\Psi\rangle\biggr) = \biggr(-I + 2|\psi\rangle\langle \psi|\biggr)\biggr(|\psi\rangle -\frac{2||\Psi||^2}{\sqrt{N}}|\Psi\rangle\biggr) = |\psi\rangle + \frac{2||\Psi||^2}{\sqrt{N}}|\Psi\rangle$$

Answer 1

I think the idea is correct, but there may be a sign error in your second operator, which may make it wrong. Edit: the question has since been corrected, so I have nothing to disagree with. I'll still leave my answer for completeness.

The point of Grover's algorithm is to increase the probability of finding your state $|\psi\rangle$ in a given desired state $|\Psi\rangle$ that you want, once you do measurements. And the way you do that is by consecutively applying unitary operators, so that they do not change the norm of the states they act on (and hence, preserve probabilities).

Now, your first operator is unitary, but the second ($U_\psi = -2|\psi\rangle\langle\psi|$ - I) isn't (you can check that $U_\psi U_\psi^\dagger \ne I$. Instead, I'm pretty sure it should be $U_\psi = 2|\psi\rangle\langle\psi| - I$. Let me explain:

---

So our goal is to increase the probability of finding the state $|\psi\rangle$ in $|\Psi\rangle$, by applying unitary operators at each step. Our first step is gonna be to "single out the $|\Psi\rangle$ component", and our second step is gonna be to "amplify it".

• first, single out the state $|\Psi\rangle$ by applying the operator $U_\Psi = I - 2|\Psi\rangle\langle\Psi|$, which will "single" out the "$|\Psi\rangle$"-components by making them negative. In your case, you are right:

$\begin{align}U_{\Psi}\biggr(\frac{\sqrt{N-1}}{\sqrt{N}}|\Psi_c\rangle + \frac{1}{\sqrt{N}}|\Psi\rangle\biggr) = \biggr(I-2|\Psi\rangle \langle\Psi|\biggr)\biggr(\frac{\sqrt{N-1}}{\sqrt{N}}|\Psi_c\rangle + \frac{1}{\sqrt{N}}|\Psi\rangle\biggr) = |\psi\rangle -\frac{2||\Psi||^2}{\sqrt{N}}|\Psi\rangle\end{align}$

• then, what you usually do, is that you apply an operator of the form $V_s= 2|s\rangle\langle s| - I$, where $|s\rangle$ is the symmetric superposition of all basis states (I'm using $V$ instead of $U$ so that we don't get confused with two many $U$'s). Now, as it happens, $|s\rangle$ is also the state $|\psi\rangle$ which you are applying Grover's algorithm on. So, applying this operator to our newfound expression:

$V_\psi(U_\Psi|\psi\rangle) = (2|\psi\rangle\langle\psi| - I)(|\psi\rangle -\frac{2||\Psi||^2}{\sqrt{N}}|\Psi\rangle) = 2|\psi\rangle - \dfrac{4||\Psi||^2\langle\psi|\Psi\rangle}{\sqrt{N}}|\psi\rangle - |\psi\rangle + \dfrac{2||\Psi||^2}{\sqrt{N}}|\Psi\rangle$

Now, computing $\langle\psi|\Psi\rangle = 1/\sqrt{N}$, we get:

$V_\psi(U_\Psi|\psi\rangle) = (1 - \dfrac{4||\Psi||^2}{N})|\psi\rangle + \dfrac{2||\Psi||^2}{\sqrt{N}}|\Psi\rangle$

Let's express that back in the original $|\Psi_c\rangle, |\Psi\rangle$ (assuming that this basis is orthonormal so that $||\Psi|| = 1$).

Then we get:

$V_\psi(U_\Psi|\psi\rangle) = \left(1-\dfrac{4}{N}\right)\left(\sqrt{\dfrac{N-1}{N}}\right) |\Psi_c\rangle + \left(\dfrac{N-4}{N\sqrt{N}} + \dfrac{2}{\sqrt{N}}\right)|\Psi\rangle$

You can check that this new state still has norm $1$, which is thanks to the fact that we were using unitary operators. And in particular, the probability of finding it in $|\Psi\rangle$ when measuring has increased (it's bigger than our original $1/N$), while the probability of finding the it in $|\Psi_c\rangle$ has decreased.

Now, you can apply that algorithm repeatedly to keep increasing the probability at your will.