Solution to problem 5.3 Book Quantum Computation and Quantum Information Nielsen Chuang regarding Kitaev's algorithm

Question

Problem 5.3: (Kitaev’s algorithm) Consider the quantum circuit

where |u> is an eigenstate of U with eigenvalue $e ^ {2 \pi i \phi} $. Show that the top qubit is measured to be 0 with probability $p = cos^{2}(\pi \phi)$. Since the state |u> is unaffected by the circuit it may be reused; if U can be replaced by $U ^{k}$, where k is an arbitrary integer under your control, show that by repeating this circuit and increasing k appropriately, you can efficiently obtain as many bits of p as desired, and thus, of $ \phi $. This is an alternative to the phase estimation algorithm.

Could you kindly show

1. How the top qubit is 0 with probability $p = cos^{2}(\pi \phi)$

2. The algorithm/procedure for replacing U by $U ^{k}$, where k is an arbitrary integer under your control , repeating this circuit and what are the appropriate values for k, and how to efficiently obtain as many bits of p as desired, and thus, of $ \phi $.

The purpose for asking this question is that I wish to arrive at a iterative Quantum Phase Estimation algorithm for computing each bit in the phase, bit by bit.

I am continuing the answers to @DaftWullie here since the system is warning me not to use comments.

To answer to your latest post, I can use $U^{2}$ operator to calculate whether $ \phi $ is 0 or $ \pi/4 $.

Thank you Dani007. Your post answers the first part of my question. It would be great if someone could answer the second question as well.

Answer 1

Whenever you have an ancilla qubit in a circuit, you can reduce the problem into a 2-dimensional problem by thinking of the circuit in terms of blocking encodings:

$$H \otimes I^n = \frac{1}{\sqrt{2}}\begin{bmatrix} I^n & I^n \\ I^n & -I^n \\ \end{bmatrix}$$

and the controlled operation on $U$ can be written as:

$$\begin{bmatrix} I^n & 0 \\ 0 & U \\ \end{bmatrix}$$

Then the circuit becomes:

$$\frac{1}{\sqrt{2}}\begin{bmatrix} I^n & I^n \\ I^n & -I^n \\ \end{bmatrix} \begin{bmatrix} I^n & 0 \\ 0 & U \\ \end{bmatrix}\frac{1}{\sqrt{2}}\begin{bmatrix} I^n & I^n \\ I^n & -I^n \\ \end{bmatrix} \\= \frac{1}{2}\begin{bmatrix} I^n + U & I^n - U \\ I^n - U & I^n + U \\ \end{bmatrix}$$

We can then represent the incoming state as:

$$\vert 0 \rangle\vert u \rangle = \begin{bmatrix} \vert u\rangle \\ 0 \\ \end{bmatrix}$$

Therefore, the state of the system before the measurement can be represented as:

$$\frac{1}{2}\begin{bmatrix} I^n + U & I^n - U \\ I^n - U & I^n + U \\ \end{bmatrix} \begin{bmatrix} \vert u\rangle \\ 0 \\ \end{bmatrix} = \frac{1}{2}\begin{bmatrix} (I^n + U)\vert u\rangle \\ (I^n - U)\vert u\rangle \\ \end{bmatrix}\\ = \frac{1}{2}\begin{bmatrix} (1 + e^{i2\pi\phi})\vert u\rangle\\ (1 - e^{i2\pi\phi})\vert u\rangle \\ \end{bmatrix}$$

Since $\vert u \rangle$ must have norm 1, then the probability of measuring the ancilla to be 0 is:

$$\frac{1}{4}\vert\vert 1 + e^{i2\pi\phi}\vert\vert^2 = \frac{1}{4}((1+ cos(2\pi\phi))^2 + sin(2\pi\phi)^2)\\ = \frac{1}{4}(1+ 2cos(2\pi\phi) + cos(2\pi\phi)^2 + sin(2\pi\phi)^2)\\ = \frac{1}{2}(1+ cos(2\pi\phi))$$

Now $cos(2\pi\phi) = cos(\pi\phi)^2 - sin(\pi\phi)^2$. So we get:

$$\frac{1}{2}(1+ cos(2\pi\phi)) = \frac{1}{2}(cos(\pi\phi)^2 + sin(\pi\phi)^2 + cos(\pi\phi)^2 - sin(\pi\phi)^2)\\ = cos(\pi\phi)^2$$

Now replacing $U$ with $U^k$ the same logic gives us $cos(k\pi\phi)^2$ which has a period of $\frac{1}{k}$ which doesn't divide $2\pi$ (period of $\phi$), it also has a peak at 1. So while $cos(\pi\phi)^2 = x$ and $cos(k\pi\phi)^2 = y$ each have a number of possible solutions, $\phi$ must be in the intersection of the 2 sets of solutions, so you can eliminate a whole lot of them by choosing $k$ cleverly.