5
$\begingroup$

I've been working through Grovers algorithm. I've read many times that $*^1H^{\otimes n}(2|0\rangle \langle0| - \mathcal{I})H^{\otimes n}$ is equivalent to $*^22|\psi\rangle \langle\psi| - \mathcal{I}$. I did verify that $*^2$ turns $\sum_x \alpha_x |x\rangle$ into $\sum_x(-\alpha_x+2\bar\alpha)$ but could not do the step before that of getting from $*^1$ to $*^2$ and I haven't seen that explained anywhere where this operation is discussed. I'd be grateful for a hint on how to do that.

I have tried to calculate $(H^{\otimes n}(2|0\rangle \langle0| - \mathcal{I})H^{\otimes n})(\sum_x \alpha_x |x\rangle)$ but only got to $\sum_x \alpha_x (\frac{1}{N} \sum_y \sum_z (-1)^{x\cdot y+y\cdot z+\delta_{y0}})|x\rangle$ and didn't come up with any simplifications for that expression.

$\endgroup$
4
$\begingroup$

If you just multiply out your first equation, you get $$ 2H^{\otimes n}|0\rangle\langle 0|H^{\otimes n}-H^{\otimes n}IH^{\otimes n}. $$ If we write $|\psi\rangle=H^{\otimes n}|0\rangle$, then this is $$ 2|\psi\rangle\langle \psi|-H^{\otimes n}IH^{\otimes n}. $$ Since $IH^{\otimes n}=H^{\otimes n}$, and $H^{\otimes n}H^{\otimes n}=I$, this just returns your second equation, $$ 2|\psi\rangle\langle \psi|-I. $$

| improve this answer | |
$\endgroup$

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.