Is Shor demonstration wrong?

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.

• This is a key point of interference: the probability amplitudes are summed before taking the modulus squared Commented Nov 22, 2022 at 0:52
• 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? Commented Nov 22, 2022 at 2:26
• @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? Commented Nov 22, 2022 at 10:07
• Oh no you're absolutely right, I was the one getting confused about where the absolute value signs were. Thanks! Commented Nov 22, 2022 at 14:34
• "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. Commented Nov 25, 2022 at 17:15

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.