I'm using Mermin's Quantum Computer Science book to understand Shor's algorithm, but I can't figure out why one of the phase factors drops out of the probability for measuring a certain y.

This is the application of the QFT on the superposition of the first register in Shor's algorithm ($x_0$ is the offset and $r$ is the period): \begin{align*}U_{FT}\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\left|{x_0+kr} \right>_n&=\frac{1}{2^{n/2}}\sum^{2^n-1}_{y=0}\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}e^{2\pi i(x_0+kr)/2^n}\left |{y} \right>_n \\ &=\sum^{2^n-1}_{y=0}e^{2\pi i x_0 y/2^n}\frac{1}{2^n\sqrt{m}}\left(\sum_{k=0}^{m-1}e^{2\pi ikry/2^n}\right)\left |{y} \right>_n\end{align*}

According to Mermin, the probability of getting the result $y$ is $p(y) = \frac{1}{2^nm}\big |\sum_{k=0}^{m-1}e^{2\pi ikry/2^n}\big |^2$. Why can we just ignore $e^{2\pi i x_0 y/2^n}$?

  • 2
    $\begingroup$ It’s a global phase that disappears when you take the mod-square. $\endgroup$
    – DaftWullie
    Jan 27 '19 at 13:14
  • $\begingroup$ what is the mod-square? $\endgroup$
    – jvdh
    Jan 27 '19 at 13:38
  • 1
    $\begingroup$ The absolute value that you’re using to evaluate the probability. $\endgroup$
    – DaftWullie
    Jan 27 '19 at 14:33

If you have a quantum state like $$|\Psi\rangle_n = a_0|0\rangle_n+a_1|1\rangle_n+...+a_n|2^n-1\rangle_n$$ and you measure it in the $\{|0\rangle_n,...,|2^{n-1}\rangle_n\}$ basis, then the probability $p(y)$ of getting the state $|y\rangle_n$ is $|a_y|^2$ where $a_y \in \Bbb C$ (i.e it's a complex number).

In your example, $$a_y = e^{2\pi i x_0 y/2^n} \frac{1}{2^n\sqrt{m}} \sum_{k=0}^{m-1}e^{2\pi ikry/2^n}.$$

Remind yourself that for a complex number $re^{i\theta}$, the modulus is $$|re^{i\theta}| = |r||e^{i\theta}|=|r| \cdot 1=|r|$$ (since $e^{i\theta}$ has a modulus of $1$) and the square of the modulus is $|r|^2.$ Note that I've not specified $r$ is real; it could still be a complex number itself.

In your case, the $e^{i\theta}$ is $e^{2\pi i x_0 y/2^n}$ and so you don't see it in $p(y)$, as $p(y)$ is essentially $|a_y|^2$. This $e^{i\theta}$ has a special name — it's a global phase for $a_y|y\rangle_n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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