in Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer by Peter W. Shor (also in Algorithms for quantum computation: discrete logarithms and factoring). In equation (5.5) it says that the probability is

$$\left\vert \frac{1}{q} \sum_{a:x^a \equiv x^k} \exp(2\pi iac/q) \right\vert ^2 $$

but shouldn't the probability be

$$ \sum_{a:x^a \equiv x^k} \left\vert \frac{1}{q}\exp(2\pi iac/q) \right\vert ^2 $$

after all

$$ \sum_{a=0}^{q-1} \sum_{c=0}^{q-1} \left\vert \frac{1}{q}\exp(2\pi iac/q) \right\vert ^2 = 1$$

and the probability of ending in a particular state $\left| c \right>$ would be $$ \sum_{a=0}^{q-1} \left\vert \frac{1}{q}\exp(2\pi iac/q) \right\vert ^2 = \frac{1}{q}$$

Something similar happens with the demonstration for discrete logarithms.

  • 1
    $\begingroup$ This is a key point of interference: the probability amplitudes are summed before taking the modulus squared $\endgroup$ Commented Nov 22, 2022 at 0:52
  • $\begingroup$ It seems like both equations you described are the same! That's because $\left|\frac{1}{q}\sum_a f(a)\right|^2 =\left|\frac{1}{q}\right|^2\sum_a \left|f(a)\right|^2=\sum_a\frac{\left|f(a)\right|^2}{\left|q\right|^2}= \sum_a \left|\frac{1}{q}f(a)\right|^2$ if $q$ is real. Or maybe there's something that I'm missing? $\endgroup$ Commented Nov 22, 2022 at 2:26
  • 1
    $\begingroup$ @RajivKrishnakumar In the general case, your first equation does not hold. For instance, with $q=1$, $f(0)=1$ and $f(1)=2$, one has $\displaystyle\left|\frac1q\sum_af(a)\right|^2=(1+2)^2=9$, but $\displaystyle\left|\frac1q\right|^2\sum_a|f(a)|^2=1^2+2^2=5$. Unless I understood wrongly what you meant? $\endgroup$
    – Tristan Nemoz
    Commented Nov 22, 2022 at 10:07
  • $\begingroup$ Oh no you're absolutely right, I was the one getting confused about where the absolute value signs were. Thanks! $\endgroup$ Commented Nov 22, 2022 at 14:34
  • 1
    $\begingroup$ "Is X wrong" is a rather, well, bold title. I suggest choosing one which leaves the option that you have a misconception, there is a typo, or the like. $\endgroup$ Commented Nov 25, 2022 at 17:15

1 Answer 1


In Equation 5.4, the expression of the state is given, which is: $$\newcommand\ket[1]{\left|#1\right\rangle}\ket{\psi}=\frac1q\sum_{a=0}^{q-1}\sum_{c=0}^{q-1}\exp\left(\frac{2\mathrm{i}\pi ac}{q}\right)\ket{c}\ket{x^a\pmod n}$$ For a given state $\ket{c,x^k\pmod n}$, we want to compute the probability of measuring this particular outcome. Since the state we're considering is pure, the probability is: $$\mathbb{P}\left[\ket{c,x^k\pmod n}\right]=\left|\left\langle\psi\middle| c,x^k\pmod n\right\rangle\right|^2$$ Remember that both $\ket{\psi}$ and $\ket{x, x^k\pmod n}$ are in fact complex vectors. In particular, $\ket{\psi}$ is written using its decomposition in the computational basis, which is the canonical basis the Hilbert space we're working with, while $\ket{c, x^k\pmod n}$ is a vector from this basis. As such, it is possible to get the complex coefficient associated to $\ket{c,x^k\pmod n}$ in $\ket{\psi}$'s decomposition in the computational basis. The second equation tells you that the squared norm of this complex coefficient is the probability to measure $\ket{c, x^k\pmod n}$.

First of all, we need to compute this projection. In order to do so, we just want to keep the terms in the sum which are associated to $\ket{c, x^k\pmod n}$. For the second sum it's easy: each $c$ appears exactly once, so we can outright remove it. For the second sum however, there are multiple $a$ such that $x^a\pmod n=x^k\pmod n$. We need to take all these $a$ into account, which means that the complex coefficient is finally: $$\frac1q\sum_{a:x^a\equiv x^k\pmod n}\exp\left(\frac{2\mathrm{i}\pi ac}{q}\right)$$ Finally, we ought to take the squared norm of this coefficient in order to get the probability we want, which is: $$\left|\frac1q\sum_{a:x^a\equiv x^k\pmod n}\exp\left(\frac{2\mathrm{i}\pi ac}{q}\right)\right|^2$$ Which is the expression given in Shor's paper.


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.