Question regarding Quantum Phase Estimation (Nielsen and Chuang exercise 5.8)

Question

I was working through Nielsen and Chuang's book on quantum computing and they state the following result regarding the performance of the Quantum Phase Estimation algorithm, "... given the input $|0\rangle\left(\sum_uc_u|u\rangle\right)$ the circuit outputs the state $\sum_u c_u |\tilde{\varphi}_u\rangle$.Show that if $t$ is chosen according to equation (5.35), then the probability for measuring $\varphi_u$ accurately to $n$ bits at the conclusion of the phase estimation algorithm is at least $|c_n|^2(1-\epsilon)$.

The equation mentioned here is $$t = n + \bigg\lceil\log_2\left(2+\frac{1}{2\epsilon}\right)\bigg\rceil$$

I tried deriving this in a method parallel to the derivation given in the case where the input for the bottom register is just a pure eigenstate done in the textbook, which determines the coefficient of the state $|(b+j) (\textrm{mod } 2^t)\rangle$ where $b$ is the largest integer such that $\frac{b}{2^t}$ is less than $\varphi$, then takes the square of these coefficients and sums over values of $j$ which are at least some error threshold away from $b$.

Mirroring this approach, let $|\varphi_v\rangle$ be the specific phase in consideration and $b_v$ be the largest integer such that $\frac{b_v}{2^t}\leq \varphi_v$ and for arbitrary $u$, $\delta_u=\varphi_u-\frac{b_v}{2^t}$. Then the final state after the inverse quantum fourier transform is

$$\sum_u\frac{c_u}{2^{t}}\sum_{k=0}^{2^{t}-1}\sum_{j=0}^{2^{t}-1}e^{2\pi ik\left(\varphi_u-j/N\right)}|j\rangle$$

So the coefficient of $|(j+b_v)(\textrm{mod }2^t)\rangle$ is

$$\beta_{j}=\sum_{u}^{ }\frac{c_{u}}{2^{t}}\sum_{k=0}^{2^{t}-1}e^{2\pi ik\left(\delta_{u}-j/2^{t}\right)}$$ $$\left|\beta_{j}\right|=\left|\sum_{u}^{ }\frac{c_{u}}{2^{t}}\left(\frac{e^{2\pi ik\left(2^{t}\delta_{u}-j\right)}-1}{e^{2\pi ik\left(\delta_{u}-j/2^{t}\right)}-1}\right)\right|\le\sum_{u}^{ }\left|c_{u}\right|\left|\frac{1}{2^{t+1}\left(\delta_{u}-j/2^{t}\right)}\right|$$ Before continuing to follow the approach used in the book, I think that I have to bound this sum with a single term, but I don't know how to bound it above with a singular term in a way which produces the desired result. Is there something that I'm missing?

Thanks for the help.

Answer 1

Since all the registers are (regarded as) measured at the end, we can imagine the second register is measured earlier -- before the controlled $U^j$ gates. In this case, the second register becomes $|u\rangle$ with a probability of $|c_u|^2$. Then, the problem becomes the same as the usual case, whose success rate is at least $1-\epsilon$.

I am not sure whether this is the correct method of solving this problem. Nevertheless, I have seen this technique used in similar contexts. This technique is related to the "deferred measurement" principle introduced in Section 4.4.