7
$\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$
2
  • $\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, 2019 at 9:34
  • $\begingroup$ Your suggestion sounds good. I've adjusted the question so I'm referring to $\theta $ instead of $\theta/2$. $\endgroup$
    – user4961
    Jan 29, 2019 at 9:44

1 Answer 1

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

Find a convenient representation of the states — 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=\arccos(\|\Pi_Y\ket\psi\|)$, $\ket\alpha\equiv\Pi_Y\ket\psi/\cos\theta$ and $\ket\beta\equiv\Pi_N\ket\psi/\sin\theta$. Intuitively, I'm writing $|\psi\rangle$ as a superposition of its projections onto "yes" and "no" spaces, defining $|\alpha\rangle,|\beta\rangle$ in such a way to absorb phase terms that might arise (this isn't essential, but simplifies the formalism).

Find an explicit expression for the Grover operator — 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 = \Pi_N-\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).$$

Realise the Grover operator is a rotation matrix — The Grover iterator $G$ is clearly unitary (it's a product of reflections, which are unitary). Furthermore, in any basis containing $|\alpha\rangle,|\beta\rangle$, its components are all real. This means that $G\in\mathbf{O}(N)$, that is, $G$ is an orthogonal matrix, thus representing a rotation around some axis.

It is also straightforward, from the expression above for $G$, to see that $G$ acts trivially outside of the space spanned by $\{|\alpha\rangle,|\beta\rangle\}$. We can therefore restrict our attention to the action of $G$ on this subspace. We then find \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$
2
  • $\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$
    – user4961
    Jan 30, 2019 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, 2019 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.