6

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.

Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112
Leander Behr
  • 133
  • 4

1 Answers1

5

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. $$

DaftWullie
  • 62,671
  • 4
  • 55
  • 140