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$$ enter image description here

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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.