3
$\begingroup$

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}$?

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

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

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .