# Prove that the operator of the Grover's algorithm 'inverts about the mean'

I'm trying to solve the following problems that I have found in the book An Introduction to Quantum Computing by Phillip Kaye, but I don't know exactly where should I start. I would appreciate any help or extra hint.

Firstly, let me introduce you the notation used in the book. The operator that is the heart of the Grover's algorithm is $$G = HU_{0^\perp}HU_f$$, where $$U_f$$ is the operator that includes the function $$f$$ we are testing in the algorithm, but this is not relevant for the question. Let $$U_{0^\perp}$$ be defined as

$$U_{0^\perp}:\left\{\begin{array}{l} \lvert x \rangle \mapsto -\lvert x \rangle , \quad x\ne 00...0\\ \lvert 00...0 \rangle \mapsto \lvert 00...0 \rangle \end{array}\right.$$

so if $$V_0$$ is the vector space spanned by $$\lvert 00...0 \rangle$$, $$U_{0^\perp}$$ applies a $$-1$$ phase shift to the vectors of the orthogonal vector space $$V_{0^\perp}$$.

Now, let

$$\lvert\psi\rangle = H \lvert 00...0 \rangle ,$$

therefore,

$$HU_{0^\perp}H:\lvert\psi\rangle\mapsto\lvert\psi\rangle .$$

Let $$V_{\psi^\perp}$$ be the orthogonal vector space orthogonal to the one spanned by $$\lvert\psi\rangle$$, and then it is spanned from $$H\lvert x \rangle$$ for $$x\ne00...0$$. For such states, we have that

$$HU_{0^\perp}H: H \lvert x \rangle \mapsto - H \lvert x \rangle ,$$

and we can say that the operator $$HU_{0^\perp}H$$ applies a phase shift of $$-1$$ to vectors in $$V_{\psi^\perp}$$. If we define $$U_{\psi^\perp} = HU_{0^\perp}H$$, the Grover's algorithm is governed by $$G = U_{\psi^\perp}U_f$$.

Now that notation has been introduced, let's write the two problems I'm trying to solve:

1. Problem 1

Let $$\lvert \psi \rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N - 1}{\lvert x \rangle}$$. Show that the operator $$HU_{0^\perp}H$$ can be written as $$(2\lvert\psi\rangle\langle\psi\rvert - I)$$.

1. Problem 2

Prove that $$U_{\psi^\perp}$$ 'inverts about the mean'. More precisely, consider any superposition

$$\lvert \phi \rangle = \sum_{x}{\alpha_x \lvert x \rangle}$$

where

$$\mu = \dfrac{1}{N} \sum_{x}{\alpha_x}$$

is the mean of the amplitudes. Show that $$U_{\psi^\perp}\lvert\phi\rangle = \sum_{x}{(\mu-\alpha_x)\lvert x \rangle}$$.

Hint given in the book: Decompose $$\lvert\phi\rangle = \alpha\lvert\psi\rangle + \beta\lvert\overline{\psi}\rangle$$ where $$\lvert\overline{\psi}\rangle$$ is orthogonal to $$\lvert\psi\rangle$$.

• related on quantumcomputing.SE: quantumcomputing.stackexchange.com/q/5905/55 – glS Apr 14 at 15:38
• @glS Actually I posted that question too... Although the problem 1 is the same, the problem 2 is not asked there and I wanted to get that answer from a deeper mathematical perspective, that's why I moved to this forum. – Jaime_mc2 Apr 14 at 15:42
• yea I noticed, hence my not saying "cross-posted" but "related" =). Still, I would point out that the first question was already answered elsewhere, unless you are not satisfied with the answer, in which case you should point out why exactly that is the case. Otherwise, removing the first problem from this question will make it more likely to get an answer (generally speaking, asking multiple questions per topic is discouraged on SE) – glS Apr 14 at 16:52