Why does Shor suggest to take $q$ such that $n^2 \leq q < 2n^2$? Isn't that a bit too much?

Question

We would like to find the order of $x \bmod{n}$. Shor --- on page 318 of his 1999 paper --- instructs:

First, we find $q$, the power of 2 with $n^2 \leq q < 2n^2$. [...] Next, we put the first register in the uniform superposition of states representing numbers $a$ (mod $q$). This leaves our machine in the state

$$\frac{1}{q^{1/2}} \sum_{a=0}^{q - 1} |a\rangle |x^a \bmod{n}\rangle$$

What's the maximum length of this state? It must be at most $2n^2$ because that is at most $q$ --- by construction. But I can't see this.

How large can $a$ be? It can be as large as $n - 1$ because no element $x$ can have order greater than $n - 1$. So $|a\rangle$ takes as many q-bits as $n$ --- say $m$ q-bits. How many q-bits do we need for $|x^a \bmod{n}\rangle$? It cannot take more than $m$ q-bits. Hence, the state above cannot take more than $2m$ q-bits. So why is $n^2$ even involved here? What am I missing?

Answer 1

Suppose $n=1000000$. You run Shor's algorithm with $q=2^{20}=1048576$. You get a result of 12345 (out of 1048576). Your goal is to find the best value of $b$ that allows a fraction $a/b$ to closely approximate $12345/1048576$, where $b$ must be less than 1000000.

Here's the problem. Given this data, the best possible answer is $8686/737783$. But there are also other nearby answers, for example $3659/310793$ is also a great approximation. Although these two values use wildly different values of $b$, the fractions they represent differ by $1/229297791919 \approx 2^{-38}$. The observable difference between wildly different candidate answers is finer than the resolution you have used. You cannot tell apart the key piece of information you have to collect! In fact, there are an absolutely enormous number of candidate answers that are great approximations, for almost every value of $b$! You are going to have to check them all! You are screwed.

To make sure that every possible fraction of the form $a/b$ with $b<1000000$ is easily distinguishable, you need $q \geq b^2$. That's why.