Reason for evaluating $a^x \bmod N$ from $x = 0$ to $N^2$

Question

As per Shor's algorithm, we need to evaluate $a^x \bmod N$ from $x = 0$ to $N^2$. What is the reason for this? Why can't we just evaluate for $N$, $2N$ or something like that?

Answer 1

Shor's algorithm relies on determining the period of $a^x\bmod N$. If you only evaluate up to $N$, then you are undersampling, in much the same way that you would classically be below the Nyquist criteria.

For example, if you measure the second register and get $y$, the first register collapses to all $x$ such that $a^x\bmod N =y$. These $x$ collide at $y$. If you only evaluate up to $N$, there is a chance that there will be no collisions for which you can properly measure the frequency in the first register.

Evaluating up to $N^2$ increases the number of such collisions, and hence decreases the odds that you undersampled.