Chapter 6

Recall that the phase shift operator in Grover's algorithm does the following to the standard basis states:

$$|x⟩\mapsto \{\begin{array}{ll}|0⟩& \text{if }x=0\\ -|x⟩& \text{otherwise.}\end{array}$$

Since $⟨0|x⟩={\delta }_{x,0}$ this is the same as what $2|0⟩⟨0|-I$ does. QED.

First of all we note that

$$|\psi ⟩⟨\psi |=\frac{1}{N}\sum _{ij}|i⟩⟨j|.$$

Hence

QED.

Recall that $M$ is the number of solutions of $f(x)=1$ and that

$$|\alpha ⟩=\frac{1}{\sqrt{N-M}}\sum _{f(x)=0}|x⟩,\text{and}|\beta ⟩=\frac{1}{\sqrt{M}}\sum _{f(x)=1}|x⟩.$$

Moreover

$$|\psi ⟩=H^{\otimes n}|0⟩=\underset{=:\cos (\theta /2)}{\underbrace{\sqrt{\frac{N-M}{N}}}}|\alpha ⟩+\underset{=:\sin (\theta /2)}{\underbrace{\sqrt{\frac{M}{N}}}}|\beta ⟩.$$

This is consistent with the formula for $\theta$ from the exercise statement, which can be seen by the trigonometric identity $\sin (2x)=2\sin (x)\cos (x)$. The Grover iteration $G$ is the product of the inversion about $\psi$, and the oracle $\mathrm{Orac}$ (inversion about $\alpha$). We ignore the workspace here.

$$G=\mathrm{inv}(\psi )\cdot \mathrm{Orac}$$

By definition of $\alpha$ and $\beta$ we have

$$\mathrm{Orac}=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right].$$

Note that this is the Pauli-Z matrix. Let

$$U(\theta )=\left[\begin{array}{cc}\cos (\theta )& -\sin (\theta )\\ \sin (\theta )& \cos (\theta )\end{array}\right].$$

Note that $U(\theta /2)=R_y(\theta )$ (Pauli-Y rotation) and that $U(\theta /2)(1,0)$ is the coordinate representation of $|\psi ⟩$. Hence

$$\mathrm{inv}(\psi )=U(\theta /2)\cdot \left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]\cdot U(-\theta /2).$$

To show the claim only a short calculation is left. Let us do it with the help of sympy:

Inv_psi = sp.simplify(Ry * Z * Ry.H)  # Ry = Ry(theta)
Orac = Z

assert Ry.subs(theta, 2*theta) == Inv_psi * Orac
"PASSED"

PASSED

Another way to see this (without much calculation) is to note that $ZU(-\varphi )Z=U(\varphi )$. QED.

The difference to the special case $M=1$ is essentially the number of repetitions of the Grover iteration. Also note that $M$ has an influence on the success probability.

We assume that $N=2^n$, $f:\{0,1{\}}^n\to \{0,1\}$, and that $M$ is the number of solutions of $f(x)=1$, as in the book. Moreover let (recall that we assume $M\le N/2$)

$$\theta =\arcsin \left(\frac{2\sqrt{M(N-M)}}{N}\right)$$

This formula comes from exercise 6.3. In the solution of that exercise we showed that

$$|\psi ⟩:=H^{\otimes n}|0⟩=\cos (\theta /2)|\alpha ⟩+\sin (\theta /2)|\beta ⟩.$$

Here $\alpha$ and $\beta$ are as in the solution of exercise 6.3. Let us write

$$|\phi ⟩:=\cos (\phi )|\alpha ⟩+\sin (\phi )|\beta ⟩.$$

Hence $|\psi ⟩=|\theta /2⟩$, $\beta =|\pi /2⟩$ and $G$ acts as $|\phi ⟩\mapsto |\phi +\theta ⟩$. In particular, since we aim to rotate $|\psi ⟩$ to $|\beta ⟩$ (approximately), the number of repetitions for the Grover algorithm is:

$$R=\mathrm{round}(\frac{\pi }{2\theta }-\frac{1}{2})=O\left(\sqrt{\frac{N}{M}}\right),$$

(for $M\le N/2$).

Algorithm (Quantum Search (Grover) for $0<M\le N/2$)

Inputs

• An $n$ bit register and a one bit register.
• A black box oracle $U_f$ which performs the transformation $U_f|x,q⟩=|x,q\oplus f(x)⟩$.

Outputs

A solution $x_0$ of $f(x_0)=1$ with probability at least $1-\sin (\theta /2{)}^2=1-M/N\ge 1/2$ (since the Grover iterations miss $\pi /2$ by at most $\theta /2$). Every solution has the same chance to get "chosen".

Runtime

$R=O(\sqrt{N/M})$ calls to the oracle and to $(2|\psi ⟩⟨\psi |-I)$, and $O(n)$ gates/operations for other things.

Procedure

1. Initialize registers to $|0⟩|0⟩$.

2. Apply $H^{\otimes n}\otimes HX$:

   $$\to \frac{1}{2^{n/2}}\sum _{x=0}^{2^n-1}|x⟩|-⟩=|\psi ⟩|-⟩=|\theta /2⟩|-⟩$$

3. Apply $R$ repetitions of $(2|\psi ⟩⟨\psi |-I)U_f$:

   $$\to |(2R+1)\theta /2⟩|-⟩\approx |\beta ⟩|-⟩$$

4. Measure the first register to obtain some $x_0$. Return $x_0$.

According to the book we have to implement $U_f^{\prime }$ as a controlled (by $q$) version of $U_f$ which acts like this:

$$|q,x,y⟩\mapsto |q,x,y\oplus \bar{q}f(x)⟩.$$

Recall that the techniques of chapter 4 require to decompose $U_f$ into elementary gates and recursively add controls. We do not do this for the following reasons:

• $U_f$ is a black box. So we are not supposed to assume anything about its internal workings. In particular it might not be implemented by the "usual" elementary gates.
• Even if it was (and we get access to the circuit during execution of the algorithm) the generic standard recursive procedure produces a relatively complicated circuit (in general).
• There is a simple way to get $U_f^{\prime }$ using $U_f$ as a black box!

The key to see this is the fact that the oracle $U_f$ leaves $|x⟩|+⟩$ fixed. Let us introduce a fourth (auxiliary) register holding one qubit, initialized to $|+⟩$. We want to implement $U_f^{\prime }$ as:

$$|q,x,y,+⟩\mapsto |q,x,y\oplus \bar{q}f(x),+⟩.$$

It is not hard to see that

$$U_f^{\prime }=\mathrm{CSWAP}(1,3,4)\cdot U_f\cdot \mathrm{CSWAP}(1,3,4)$$

accomplishes exactly that. Here $\mathrm{CSWAP}(1,3,4)$ is the controlled swap gate exchanging registers three and four conditioned on register one. QED.

In the framework of (classical) reversible computation as sketched in chapter 3.2.5 in the book we need at least two applications of the oracle.

Before we prove this let us first show a classical reversible algorithm which uses two applications of the oracle:

The second application of the oracle is needed to uncompute the garbage from the auxiliary register. An intuitive way to see the necessity of the second application is to look at the information present in the registers. In case of $q=1$ the final state does not contain a single bit of information about $f$. On the other hand, if we apply the oracle just once it leaves one bit of information about $f$ (the value of $f$ at some input, but not necessarily at $x$). So the computation after the application of the oracle would have to erase the information which is not possible with reversible computation (without using the oracle, and hence some information about $f$, again).

Let us give a (hopefully) more rigorous proof. Assume to the contrary that it was possible with just one application of the oracle and an additional $m$ qubit auxiliary register (initialized to $0$). The circuit (which is just a sequence of reversible gates) can be divided into three parts. The part $A$ before the oracle, the application of the oracle $U_f$, and the part $B$ after the oracle:

In the second step the $p$ "signifies" our choice to what $n+1$ qubits to apply the oracle. Let us merge the $a_i$ into a single vector $z$ (just for notational simplicity). Same for $z^{\prime }$ vs the $a_i$.

After the oracle step for a certain $j_0$ we have $z_{j_0}^{\prime }=z_{j_0}\oplus f(\tilde{x})$. Here the $\tilde{x}=\tilde{x}(q,x,A,p)$ only depends on $q$, $x$, the first part $A$, and the places $p$ to which the oracle is applied. Note that for $q=0$ clearly $\tilde{x}=x$ (otherwise, there is no way to obtain $f(x)$), but for $q=1$ (the interesting case) we cannot conclude this.

Now let us simulate the above circuit on a larger circuit with four zones. A zone is just a group of registers. The first zone is a read-only zone containing $q,x,y$ all the time. The second and third zone contains the same four registers (each) as the above circuit. The last zone contains only a one-qubit circuit.

Let us denote by $\mathrm{Sim}(A,i)$ for $i\in \{2,3\}$ the circuit which executes $A$ at zone $i$. The simulations of $U_f$ and $B$ are defined similarly.

Consider the circuit which acts as follows:

1. Start $$|q,x,y;0;0;0⟩$$
2. Copy $q,x,y$ to zone $2$: $$\to |q,x,y;q,x,y,0;0;0⟩$$
3. Apply $\mathrm{Sim}(A,2)$: $$\to |q,x,y;z;0;0⟩$$
4. Apply $\mathrm{Sim}(U_f(p),2)$: $$\to |q,x,y;z^{\prime };0;0⟩$$
5. Apply $\mathrm{Sim}(B,2)$: $$\to |q,x,y;q,x,y\oplus \bar{q}f(x),0;0;0⟩$$

Now let us see how we can extract $f(\tilde{x})$ from the final state (without using the oracle). The possibility of being able to do this is a contradiction since clearly no traces of $f$ are left in the final state for $q=1$.

6. Uncompute $\mathrm{Sim}(B,2)$: $$\to |q,x,y;z^{\prime };0;0⟩$$
7. Copy $q,x,y$ to zone $3$: $$\to |q,x,y;z^{\prime };q,x,y,0;0⟩$$
8. Apply $\mathrm{Sim}(A,3)$: $$\to |q,x,y;z^{\prime };z;0⟩$$

9. Add zone three to zone two (using bit-wise addition):

   $$\to |q,x,y;z^{″};z;0⟩$$

   Note that $z^{″}$ contains just one non-trivial bit $z_{j_0}^{″}=f(\tilde{x})$ (the others are trivially zero).

10. Copy $z_{j_0}^{″}=f(\tilde{x})$ to the fourth zone and erase it from zone two (by a CNOT controlled by the fourth zone): $$\to |q,x,y;0;z;f(\tilde{x})⟩$$
11. Uncompute $\mathrm{Sim}(A,3)$ (not important, just for reasons of feng shui): $$\to |q,x,y;0;0;f(\tilde{x})⟩$$

We have managed to extract a bit of information about $f$ no matter the value of $q$. This is a contradiction as already explained above. QED.

The circuit in the dotted region implements the following operator

$$X\otimes X\cdot \underset{C(Z)}{\underbrace{I\otimes H\cdot C(X)\cdot I\otimes H}}\cdot X\otimes X$$

Recall that the controlled Z-gate acts as follows on the standard basis:

$$C(Z)|x⟩=\{\begin{array}{ll}-|11⟩& \text{for }x=11\\ |x⟩& \text{otherwise.}\end{array}$$

The X-gate just exchanges the roles of $0$ and $1$:

$$X\otimes X\cdot C(Z)\cdot X\otimes X\cdot |x⟩=\{\begin{array}{ll}-|00⟩& \text{for }x=00\\ |x⟩& \text{otherwise.}\end{array}$$

Up to a factor of $-1$ (the global phase factor) this is precisely what $2|00⟩⟨00|-I$ does. QED.

Since $|x⟩⟨x|$ is a projection (that is, an operator for which $P^2=P$) the series expansion of the exponential function implies

$$e^{-\mathrm{i}|x⟩⟨x|\mathrm{\Delta }t}=e^{-\mathrm{i}\mathrm{\Delta }t}|x⟩⟨x|+(I-|x⟩⟨x|)$$

Hence

$$e^{-\mathrm{i}|x⟩⟨x|\mathrm{\Delta }t}|y⟩=\{\begin{array}{ll}|y⟩& \text{if }y\ne x\\ e^{-\mathrm{i}\mathrm{\Delta }t}|x⟩& \text{if }y=x\end{array}=e^{-\mathrm{i}\mathrm{\Delta }tf(y)}|y⟩.$$

On the other hand this is exactly what the circuit ($U_f\mathrm{diag}(1,\exp (-\mathrm{i}\mathrm{\Delta }t))U_f$) does.

QED.

In the same way as in the first part we see that

$$e^{-\mathrm{i}|\psi ⟩⟨\psi |\mathrm{\Delta }t}|\phi ⟩=\{\begin{array}{ll}|\phi ⟩& \text{if }|\phi ⟩\perp |\psi ⟩\\ e^{-\mathrm{i}\mathrm{\Delta }t}|\psi ⟩& \text{if }|\phi ⟩=|\psi ⟩\end{array}$$

Again this is exactly what the circuit does. Let us first consider the case $|\phi ⟩=|\psi ⟩$:

For the case $|\phi ⟩\perp |\psi ⟩$ we only have to note that $H^{\otimes n}|\phi ⟩$ is orthogonal to $|0⟩$ and hence the controlled $X$ gate does nothing. QED.

From equation (6.23) we know that the simulation time is $t=\pi /2\alpha =O(\sqrt{N})$. Hence the number of steps is $t/\mathrm{\Delta }t=O(\mathrm{\Delta }{t}^{-1}\sqrt{N})$. Since the error of a product of unitary operators scales linearly we see that the overall error is

$$O(\mathrm{\Delta }{t}^{r-1}\sqrt{N})$$

This must be $O(1)$ and hence we must choose $\mathrm{\Delta }t=O(N^{-1/2(r-1)})$. To minimize the number of steps we set $\mathrm{\Delta }t\approx N^{-1/2(r-1)}$ and obtain the claim. QED.

Let $\hat{z}=(0,0,1)$ and $\overrightarrow{\psi }=(2\alpha \beta ,0,{\alpha }^2-{\beta }^2)$. From the paragraph above equation (6.25) we deduce

$$U(\mathrm{\Delta }t)=e^{-\mathrm{i}|\psi ⟩⟨\psi |\mathrm{\Delta }t}\cdot e^{-\mathrm{i}|x⟩⟨x|\mathrm{\Delta }t}=e^{-\mathrm{i}\mathrm{\Delta }t}\cdot e^{-\mathrm{i}\overrightarrow{\psi }\cdot \overrightarrow{\sigma }\mathrm{\Delta }t/2}\cdot e^{-\mathrm{i}\hat{z}\cdot \overrightarrow{\sigma }\mathrm{\Delta }t/2}.$$

The first of the three terms is the unimportant global phase. The second and the third are rotations around $\overrightarrow{\psi }$ and $\hat{z}$ and angle $\mathrm{\Delta }t$ (both). Hence we are indeed in the setting of exercise 4.15. From that exercise we deduce that $U(\mathrm{\Delta }t)$ is a rotation around an axis $\overrightarrow{n}$ by an angle $\theta$

$$U(\mathrm{\Delta }t)=e^{-\mathrm{i}\mathrm{\Delta }t}(\cos (\theta /2)I+\sin (\theta /2)\overrightarrow{n}\cdot \overrightarrow{\sigma })$$

such that:

$$\cos (\theta /2)=c^2-s^2\overrightarrow{\psi }\cdot \hat{z}$$

and

$$\sin (\theta /2)\overrightarrow{n}=sc(\overrightarrow{\psi }+\hat{z})+s^2\overrightarrow{\psi }\times \hat{z}.$$

QED.

To not obscure the proof by too much technicalities I only prove the result for large enough $N$. Let $c=\cos (\mathrm{\Delta }t/2)$ and $s=\sin (\mathrm{\Delta }t/2)$.

From the proof of exercise 6.9 we know that $U(\mathrm{\Delta }t)$ is a rotation of angle $\theta$ about $\overrightarrow{r}$ where:

$$\cos (\theta /2)=c^2-s^2\overrightarrow{\psi }\cdot \hat{z}$$

and

$$\sin (\theta /2)\overrightarrow{r}=sc(\overrightarrow{\psi }+\hat{z})+s^2\overrightarrow{\psi }\times \hat{z}.$$

Also recall that $\hat{z}=(0,0,1)$ and $\overrightarrow{\psi }=(2\alpha \beta ,0,{\alpha }^2-{\beta }^2)$ where $\alpha =1/\sqrt{N}$ and $\beta =\sqrt{(N-1)/N}$. Let us further elaborate on $\theta$. Using one of the above formulas we get

$$\cos (\theta /2)=1-\frac{2s}{N}.$$

From the Taylor expansion $\cos (x)=1-x^2/2+O(x^4)$ of the cosine function we obtain

$$\theta =4\sqrt{\frac{s}{N}}+O(s{N}^{-1}).$$

Now consider the axis of rotation. Below with $\sim$ we mean that the LHS is equal to the RHS up to a real factor. Using the axis-formula a short calculation yields

$$\overrightarrow{r}\sim (\beta c,-\beta s,\alpha c).$$

The squared norm of the RHS is $1-{\alpha }^2{s}^2$. Hence

$$\overrightarrow{r}=(\beta c,-\beta s,\alpha c)/\sqrt{1-{\alpha }^2{s}^2}=(\beta c,-\beta s,\alpha c)+O(s^2{N}^{-1}).$$

From the original formula for $\overrightarrow{r}$ we see that $\overrightarrow{r}\cdot \hat{z}=\overrightarrow{r}\cdot \overrightarrow{\psi }\approx \alpha c=O(N^{-1/2})$. This implies that $\hat{z}$ indeed lies on the same orbit as $\psi$. Let $\omega$ be the angle of the rotation about $\overrightarrow{r}$ which is needed to rotate $\overrightarrow{\psi }$ into $\hat{z}$. Let

$${\hat{z}}^{\prime }=\hat{z}-(\hat{z}\cdot \overrightarrow{r})\overrightarrow{r}=\hat{z}-\frac{\alpha c}{\sqrt{1-{\alpha }^2{c}^2}}\overrightarrow{r}=\hat{z}+O(N^{-1/2})\overrightarrow{r}$$

and

$${\overrightarrow{\psi }}^{\prime }=\overrightarrow{\psi }-(\overrightarrow{\psi }\cdot \overrightarrow{r})\overrightarrow{r}=\overrightarrow{\psi }-\frac{\alpha c}{\sqrt{1-{\alpha }^2{c}^2}}\overrightarrow{r}=\overrightarrow{\psi }+O(N^{-1/2})\overrightarrow{r}.$$

Hence

$$\cos (\omega )={\overrightarrow{\psi }}^{\prime }\cdot {\hat{z}}^{\prime }=\overrightarrow{\psi }\cdot \hat{z}+O(N^{-1})={\alpha }^2-{\beta }^2+O(N^{-1})=-1+O(N^{-1}),$$

and therefore $\omega =\pi +O(N^{-1/2})$. Using this and the formula for $\theta$ we see that the number of required $\theta$ rotations is

$$\frac{\omega }{\theta }=\frac{\pi }{4\sqrt{s}}\sqrt{N}+O(1).$$

To enable a 100% probability this number must be an integer. The standard case with $\mathrm{\Delta }t=\pi$ means $s=1$. By the intermediate value theorem (the expression is continuous) there is an $s\in [1-c{N}^{-1/2},1]$ (for some constant $c>0$ depending on the constant in the $O(1)$ above) such that this is true. Clearly $\omega /\theta =O(\sqrt{N})$ for such $s$. QED.

Let us use sympy to do the boring calculations. First let us define $\hat{z}$ and $\overrightarrow{\psi }$ in a 3D cartesian coordinate system. Moreover we set up our slightly scaled version r1 of $\overrightarrow{r}$.

N = CoordSys3D('N')

z = N.k
psi = 2*a*b*N.i + (a**2 - b**2)*N.k

r_formula_rhs = s*c*(psi + z) + s**2 * psi.cross(z)
r1 = b*c*N.i - b*s*N.j + a*c*N.k

Here we check that our formula for $\overrightarrow{r}$ is valid:

norm2_r1 = r1.dot(r1).subs(b**2, 1 - a**2).subs(c**2, 1 - s**2)

assert r_formula_rhs.subs(b**2, 1 - a**2) == 2*a*s * r1
assert sp.simplify(norm2_r1) == 1 - a**2 * s**2
"PASSED"

PASSED

My Ansatz looks as follows

$$H=|\chi ⟩⟨\chi |+|\psi ⟩⟨\psi |,$$

where

$$\chi =\frac{1}{\sqrt{M}}\sum _{f(x)=1}|x⟩$$

and we let $|\psi ⟩$ unspecified at first (as always we take $|\psi ⟩=H^{\otimes n}|0⟩$ in the end). It turns out that section 6.2 essentially works out analogously with this Hamiltonian if one replaces $x$ with $\chi$.

In particular we arrive at the same formula for the Hamiltonian and formula (6.23) which states that the corresponding unitary group rotates (the still arbitrary) $|\psi ⟩$ into $|\chi ⟩$:

$$\cos (\alpha t)|\psi ⟩-i\sin (\alpha t)|\chi ⟩.$$

Thus after time $t=\pi /2\alpha$ the system is rotated in a state which when measured produces a solution of $f(x)=1$ (equal probability for each possibility). So what is the difference? Something must be different, right? I am glad you asked! Actually so far nothing is different!

Essentially the only thing which differs is the value of $\alpha$ once we fix $|\psi ⟩$. As in chapter 6.2 we have to choose $|\psi ⟩$ in a way which allows us to determine $\alpha$ without knowing $|\chi ⟩$. This is where we fix $|\psi ⟩=H^{\otimes n}|0⟩$. This in turn leads to

$$\alpha =\sqrt{M/N}.$$

Let us finally investigate the implications for the performance of an approximation similar to the one in the book. It is easiest to just follow the proof of exercise 6.10. For simplicity we restrict our short analysis to the case $M=o(N)$.

The angle $\theta$ of rotation is determined by (c.f. the case for $M=1$)

$$\cos (\theta /2)=1-\frac{2Ms}{N}.$$

Hence

$$\theta =4\sqrt{\frac{sM}{N}}+O(sM{N}^{-1}).$$

The same reasoning as in exercise 6.10 allows us to estimate the angle $\omega$ between $\overrightarrow{\psi }$ and $\hat{z}$:

$$\cos (\omega )=-1+O(M{N}^{-1}).$$

Hence $\omega \approx \pi$. We conclude that the number of iterations is $\omega /\theta =\mathrm{\Theta }(\sqrt{N/M})$ (if we choose $\mathrm{\Delta }t=\pi$ and thus $s=1$). But keep in mind that we used $M=o(N)$ in this analysis!

Let $|\psi ⟩=\alpha |x⟩+\beta |y⟩$. In the basis $(|x⟩,|y⟩)$

$$H=\alpha I+\beta X+\alpha Z.$$

Note that the term involving the identity $I$ is not important since it only corresponds to a global phase in $e^{-\mathrm{i}Ht}$. Recall from the book that the Hamiltonian $H_0=|x⟩⟨x|+|\psi ⟩⟨\psi |$ is equal to $I+\alpha (\beta X+\alpha Z)$. Hence

$$e^{-\mathrm{i}Ht}\sim e^{-\mathrm{i}{H}_0{\alpha }^{-1}t}$$

where $\sim$ means up to a global phase. We already know from equation (6.23) that $H_0$ rotates $|\psi ⟩$ into $|x⟩$ after time $t=\pi /2\alpha$. Hence $H$ does the same after time $t=\pi /2=O(1)$. QED.

First of all note that the two summands of $H$ (I mean $|x⟩⟨\psi |$ and $|\psi ⟩⟨x|$) are not self adjoint. Hence their exponentials (e.g. $e^{-\mathrm{i}|x⟩⟨\psi |}$) are not unitary. So we cannot simulate the summands by a circuit.

On the other hand from the first part we already know that the exponential of $H$ is essentially a time-scaled version of the exponential of $H_0$. So if we can simulate the latter this yields a simulation of the former. The resource requirements are the same of course. Not sure if this is the intended meaning of the exercise though.

The exercise is a little bit vague in my opinion - but that is OK. If we speak about probabilities there must be a probability distribution somewhere. The exercise doesn't explicitly define one. Sometimes the distribution is given implicitly. In this case I think there are at least two options:

• Postulate a probability distribution on the inputs.
• Assume that the oracle calls are at randomly selected arguments.

I solved the exercise for both interpretations.