Suppose there is a single marked state in a data base of $N=2^2$ elements. The grover iteration finds the state with some probabaility. First it adds a negative phase to the single (assumption) marked state say $11$, and then it rotates the state towards the desired solution. So here is what I understand. $H|0\rangle^{\otimes~2}=\dfrac{1}{\sqrt{4}}\sum_{x=0}^{4-1}|x\rangle= \dfrac{1}{\sqrt{4}}\left(|11\rangle+\dfrac{1}{\sqrt{4-1}}\sum_{x\neq 11}^{4-1}|x\rangle\right)$. This operation marks the state and adds a negative phase. So the state becomes $$ \dfrac{1}{4}\left( |00\rangle+ |01\rangle +|10\rangle -|11\rangle\right)$$. Now we do a reflection about the mean. We do this by the operation $HUH|s\rangle$. Where $|s\rangle$ the superposition station. So that $H|s\rangle=|0\rangle$. My question is that if we apply this reflection operator just after the oracle, how do we get the $|0\rangle$ since the state $|s\rangle$ has a marked state with minus infront of the state $|11\rangle$. It is the qiskit implementation.
1 Answer
In a two-qubit system, our special element $x'$ and its corresponding outer product shall be: $$ |x'\rangle = |11\rangle = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \quad\text{and}\quad |x'\rangle\langle x'| = \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ \end{bmatrix} $$
The phase inversion operator $U_f$:
$$ U_f = I - 2| x'\rangle\langle x'| = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & -1 \end{bmatrix} $$
The superposition state $|s\rangle$ is: $$ |s\rangle = H^{\otimes 2}|00\rangle = |++\rangle = \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\1 \\1 \end{bmatrix} $$
Then: $$ U_f|s\rangle = \frac{1}{2} \begin{bmatrix} 1 \\ 1 \\ 1 \\ -1 \end{bmatrix} $$
Inversion about the mean operator: $$ U_{m} = 2(|+\rangle\langle +|)^{\otimes 2} - I^{\otimes 2} \\ = 2|s\rangle\langle s| - I^{\otimes 2} \\ = \frac{1}{2} \begin{bmatrix} -1 & 1 & 1 & 1\\ 1 & -1 & 1 & 1\\ 1 & 1 & -1 & 1\\ 1 & 1 & 1 & -1 \end{bmatrix} $$
And to multiply this out (for 2 qubits, 1 iteration is sufficient): $$ U_m U_f |s\rangle = |11\rangle. $$
Numerically (using my own infra):
>>> x = state.bitstring(1, 1)
>>> x
State([0.+0.j 0.+0.j 0.+0.j 1.+0.j])
>>> s = ops.Hadamard(2)(state.bitstring(0, 0))
>>> s
State([0.49999997+0.j 0.49999997+0.j 0.49999997+0.j 0.49999997+0.j])
>>> Uf = ops.Operator(ops.Identity(2) - 2 * x.density())
>>> Uf
Operator([[ 1.+0.j 0.+0.j 0.+0.j 0.+0.j]
[ 0.+0.j 1.+0.j 0.+0.j 0.+0.j]
[ 0.+0.j 0.+0.j 1.+0.j 0.+0.j]
[ 0.+0.j 0.+0.j 0.+0.j -1.+0.j]])
>>> Ub = ops.Operator(2 * s.density() - ops.Identity(2))
>>> Ub
Operator([[-0.50000006+0.j 0.49999994+0.j 0.49999994+0.j 0.49999994+0.j]
[ 0.49999994+0.j -0.50000006+0.j 0.49999994+0.j 0.49999994+0.j]
[ 0.49999994+0.j 0.49999994+0.j -0.50000006+0.j 0.49999994+0.j]
[ 0.49999994+0.j 0.49999994+0.j 0.49999994+0.j -0.50000006+0.j]])
>>> (Ub @ Uf)(s).dump()
|11> (|3>): ampl: +1.00+0.00j prob: 1.00 Phase: 0.0
```
