I know about the answer of a similar question here: Reason for evaluating $a^x \bmod N$ from $x = 0$ to $N^2$.
But the answer there seems to explain the reason in terms of real qubits (chance of them collapsing to some state or not) plus the undersampling criteria (Nyquist Theorem). My question here is about purely logical qubits.
$f_{a,N}(x) = a^x \bmod N$. The period that we want to find is $r$ such that $f_{a,N}(x+r) = f_{a,N}(x)$. Since for all $a$ and $N$, $f(0)=1$ and we are assuming that the function is periodic, we need to find another $f(x)=1$. This $x$ will be our estimate for $r$.
Having found $r, r \neq 0$ such that $f(r)=1$, if we want to confirm our result we could go to $f(2r)$ and get again $f(2r)=1$.
The biggest value that $f(x)$ can have is $N$. The function is discrete. Therefore in at least $N$ trials we would find an $x=r, r \neq 0$ such that $f(x)=1$. To satisfy Nyquist criteria we would need to go at most to $2N$ trials. In $2N$ trials of $x$ we will find two instances of $f(x)=1$ and our period would be found and confirmed.
Therefore why in theory it is said that we need $N^2$ trials and not $2N$ trials?
