It is stated in the Phase Estimation algorithm in Page 222, Quantum Computation and Quantum Information by Nielsen and Chuang that




It seems to say that taking the inverse Quantum Fourier transform of the state gives $$ |\phi_1\cdots\phi_t\rangle $$

That means the state $\frac{1}{2^{t/2}}(|0\rangle+e^{2\pi i0.\phi_t}|1\rangle)(|0\rangle+e^{2\pi i0.\phi_{t-1}\phi_t}|1\rangle)\cdots (|0\rangle+e^{2\pi i0.\phi_{1}\cdots\phi_t}|1\rangle)$ is the Quantum Fourier transform of the state $|\phi_1\cdots\phi_t\rangle$.

But in the section of the derivation of the QFT it is given


As per Eq. 5.5 to 5.10 $$\frac{(|0\rangle+e^{2\pi i0.\phi_t}|1\rangle)(|0\rangle+e^{2\pi i0.\phi_{t-1}\phi_t}|1\rangle)\cdots (|0\rangle+e^{2\pi i0.\phi_{1}\cdots\phi_t}|1\rangle)}{2^{t/2}}=\frac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}e^{2\pi i\phi k/\color{red}{2^t}}|k\rangle$$ But equations 5.20-5.21-5.22 seem to consider it is equal to $\frac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}e^{2\pi i\phi k}|k\rangle$. How do I make sense of this ?

  • $\begingroup$ I think in your last comment, it is $\sum_{k=0}^{2^t-1} e^{2 \pi i \phi k / 2^n} |k \rangle$ ( with the normalization constant ofcourse ). I'm not sure if I understand your question because what you have asked is exactly explained in the image above. Could you elaborate a bit more? $\endgroup$ Nov 20, 2021 at 7:47

1 Answer 1


Your misconception is that you assume that the QFT is exactly the same as the first part of the quantum phase estimation (QPE). This is not the case as they start with different assumptions.

The QFT has by definition $2^t$ in the denominator, as is shown in 5.5. You can actually see that even earlier in the chapter with equation 5.2, which $N$ in the denominator. $N$ is the length of the vector, and they state that they take $N=2^n$, as the length of the vector will be proportional to the number of qbits in your system.

QPE on the other hand starts with different assumptions, the important one being that your unitary rotation has an eigenvalue of $e^{2\pi i\phi}$. This means you have a gate that applies the following: $U|0⟩=e^{2\pi i\phi}|0⟩$. This gate is then applied $2^{t-1}$ times which gives you equation 5.20.

So, as you have noted, the two equations are different and this actually has an impact on the way you process the output of the QPE: we apply a normal IQFT, but, as you have mentioned, this is missing a denominator or $2^t$. That means that the output of your QPE is not $\phi$ but $2^t\phi$: to get your final phase estimation you need to divide your output by $2^t$. You can see how this is done on a practical example with qiskit here, at the end of part 2.

So to summarize, the two equations are different because they tackle different problems (one is for the QFT, the other for QPE).


Your Answer

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