4
$\begingroup$

I have seen that it is possible to represent the Grover iterator as a rotation matrix $G$. My question is, how can you do that exactly? So we say that $|\psi\rangle$ is a superposition of the states of searched and not searched elements, that can be represented like this: $$|\psi\rangle=\sqrt{\frac{N-1}{N}}|\alpha\rangle+\sqrt{\frac{1}{N}}|\beta\rangle$$ Now you can rewrite that so you get this expression: $$|\psi\rangle=\cos(\theta/2)|\alpha\rangle+\cos(\theta/2)|\beta\rangle$$ I have seen that an application of the Grover iteration can be represented as a rotation matrix, e.g. in this form: $$G=\begin{pmatrix}\cos(\theta)&-\sin(\theta)\\\sin(\theta)&\cos(\theta)\end{pmatrix}$$ But how do you get to the shape, what are the necessary steps and calculations?

I hope that the question is expressed as understandably and clearly.

$\endgroup$
  • $\begingroup$ I suggest not mixing conventions in the same question. If you are going to use $\theta$ or $\frac{\theta}{2}$, but just be consistent within the same question. Helps say which form of $G$ goes with which parameterization. $\endgroup$ – AHusain Jan 29 at 9:34
  • $\begingroup$ Your suggestion sounds good. I've adjusted the question so I'm referring to $\theta $ instead of $\theta/2$. $\endgroup$ – QuantaMag Jan 29 at 9:44
4
$\begingroup$

This is essentially the same calculation I outlined in this other answer (though it might not be immediately obvious).$\newcommand{\ket}[1]{\lvert#1\rangle}\newcommand{\ketbra}[2]{\lvert#1\rangle\!\langle#2\rvert}$

Let us denote with $\Pi_Y$ and $\Pi_N=I-\Pi_Y$ the projectors onto the "yes space" and the "no space". Given an initial state $\ket\psi$, the goal is getting as close to a state in $\Pi_Y$ as possible, as fast as possible.

Because $\{\Pi_Y,\Pi_N\}$ define a separation of the full space, any state can be decomposed using these operators. In particular, we can write $$\ket\psi=\cos\theta\ket\alpha+\sin\theta\ket\beta,$$ where $\theta$ is defined via $\cos\theta\equiv\|\Pi_Y\ket\psi\|$, while $\ket\alpha\equiv\Pi_Y\ket\psi/\cos\theta$ and $\ket\beta\equiv\Pi_N\ket\psi/\sin\theta$ (I'm using a slightly different notation with the $\theta$ than the one in the OP, sorry about that).

The Grover iterator is defined as $G=-S_\psi S_Y$, where $S_Y$ and $S_\psi$ are reflections in state space, that is, operators which leave untouched some subspace and change the sign on everything else. More specifically $S_Y$ flips the "yes space", while $S_\psi$ flips the direction corresponding to the initial state $\ket\psi$ (that is, it leaves the direction of the initial state untouched and flips everything else). Mathematically, these reflections can be written as $$S_Y\equiv I - 2\Pi_Y, \qquad S_\psi\equiv I - 2\ket\psi\!\langle\psi\rvert.$$ It follows that the Grover operator reads $$G=(I-2\ket\psi\!\langle\psi\rvert)(2\Pi_Y-I).$$ Expanding this product we get $$G=2\Pi_Y-I-4 \lvert\psi\rangle\!\langle\psi\rvert\Pi_Y + 2\ket\psi\!\langle\psi\rvert.$$ Expanding $\ket\psi$ in terms of $\ket\alpha$ and $\ket\beta$, and remembering the property of $\ket\alpha$ that $\Pi_Y\ket\alpha=\ket\alpha$, you can readily verify that this expression becomes, after a bit of algebra, the following (let me use here the shorthand notation $c\equiv\cos\theta$ and $s\equiv\sin\theta$):

$$G=2\Pi_Y-I+2s^2\ketbra\beta\beta-2c^2 \ketbra\alpha\alpha +2cs (\ketbra\alpha\beta-\ketbra\beta\alpha).$$

Now this represents a rotation in state space of some angle with respect to some axis, but because we are only interested in the action of $G$ on states spanned by the $\ket\alpha$ and $\ket\beta$ states, we need only analyse how $G$ acts on these two states. We then readily get: \begin{align} G\ket\alpha&=-\cos(2\theta)\ket\alpha-\sin(2\theta)\ket\beta, \\ G\ket\beta&=\phantom{-}\sin(2\theta)\ket\alpha-\cos(2\theta)\ket\beta. \\ \end{align} Collecting the corresponding amplitudes in a matrix, we conclude that the action of $G$ in the space spanned by $\ket\alpha$ and $\ket\beta$ can be represented as $$G\doteq\begin{pmatrix}-\cos(2\theta) &\sin(2\theta)\\-\sin(2\theta) & -\cos(2\theta)\end{pmatrix}.$$

Note that this shows that the result holds in a more general scenario that the one often used when first explaining Grover's algorithm. You can however easily reduce to the standard situation (which you also use in your post) by having $\ket\psi$ be a balanced superposition of all basis states, and $\Pi_Y$ a trace-1 projector (that is, a projector over a one-dimensional subspace).

$\endgroup$
  • $\begingroup$ Thank you for your answer! Now you can see different forms of superposition. Once with the angle $\theta$ and once with the angle $\theta/2$, you have in your example called the angle as $\theta$. My question is, what difference does that make if I call the angle $\delta$ or $\theta/2$? Is it only a factor in the rotation matrix? $\endgroup$ – QuantaMag Jan 30 at 9:31
  • $\begingroup$ @QuantaMag yea no difference at all, the only important thing is that the angle in $G$ is double the one in $\lvert\psi\rangle$. I'm simply more used to this one, which I believe is also a bit more standard $\endgroup$ – glS Jan 30 at 9:45

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .