As per the 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?


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.

| improve this answer | |

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.