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

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.

• What have you tried? Specifically, have you tried to find the output of the circuit and, if so, what did you get? Commented Jun 21, 2022 at 10:07
• I calculated the answer to the first question. The first step is the Hadamard operator on the state |0> with output (|0> + |1>)/sqrt(2). The next step is Controlled-U which after substituting the phase-kickback $e^{2 \pi \phi}$ becomes $1/ \sqrt{(2)} (|0> + e^{2 \pi \phi}|1>)|u>$ and finally applying Hadamard transform becomes (1/ 2) ((|0> + |1>) + e^{2 \pi \phi}(|0> - |1>))|u>$which on simplifying becomes (1/ 2) ((|0>(1 + e^{2 \pi \phi}) + |1>) (1 - e^{2 \pi \phi}|u>$. Commented Jun 21, 2022 at 11:13
• You're missing some factors of $i$ from the exponents. But yes, this is the answer. This is the same as $(\cos(\pi\phi)|0\rangle+i\sin(\pi\phi)|1\rangle)|u\rangle$ (up toa global phase). So, what's the probability of getting answer 0 if you measure the first qubit? Commented Jun 21, 2022 at 11:21
• the probability is $cos ^2 {(\Pi \Phi)}$. Thank you. But I don't know the answer to the second question. Commented Jun 21, 2022 at 11:25
• Yup, so that's what you were after for question 1. Question 2: $|u\rangle$ is an eigenstate of $U^k$ with what eigenvalue? Commented Jun 21, 2022 at 11:26

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.

• 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. Commented Jun 21, 2022 at 15:52