# 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? 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>$. 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? 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. 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? 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. Jun 21, 2022 at 15:52