Why is the size of the top register for Shor's algorithm chosen as it is?

Question

Let $N$ be the number we're trying to factor. In Shor's algorithm, the top register then has $2 \lceil\log_2(N)\rceil+1$ qubits, while the bottom register (the ancilla qubits) has $\lceil\log_2(N)\rceil$ qubits.

This is stated in my lecture notes on slide 25.

I believe I have an approximate understanding of Shor's algorithm: the end result on the top register, $\left| x_{\text{final}} \right>$, is such that $\frac{x_{\text{final}}}{T} = \frac{s}{r}$ for some integer $s$. In the aforementioned equation, $T=2^{2 \lceil \log_2(N) \rceil + 1}$ and $r$ is the oracle's (modular exponentiation) period.

The end result of the bottom (ancillary) register is the result of the modular exponentiation: $\left| f(x) + y \right> = \left| f(x) \right> = \left| a^x \mod N \right>$. The largest result possible is $N-1$, for which you require $\lceil \log_2(N - 1) \rceil$ qubits, so it makes sense that the size of the bottom register is $\lceil\log_2(N)\rceil$.

I do not however understand the choice of the size of the top register.

Answer 1

In a nutshell, the number of qubits in the top register directly corresponds to the number of bits of precision to which $x/T$ approximates $s/r$, and we need enough precision to be able to determine $s$ and $r$ given $x/T$. For example, if $s=1$ and $r$ is large, then we cannot afford to confuse $1/r$ with $1/(r+1)$, say.

In more detail, think about any two fractions $a/b$ and $c/d$ with $a/b\not=c/d$, where $b$ and $d$ are both positive integers that are less than $N$. Because these are integers, and because $ad\not=bc$, we find that the difference between them satisfies the following inequality: $$ \Bigl| \frac{a}{b} - \frac{c}{d} \Bigr| = \frac{|ad-bc|}{bd} > \frac{1}{N^2}. $$ So, if $x/T$ is an approximation to $s/r$ that is good to $2\lceil\log(N)\rceil + 1$ bits of precision, the error of this approximation will be less than half of $1/N^2$, so the approximation has to be closer to $s/r$ than it is to any other fraction of a different value having a denominator smaller than $N$ (and of course the continued fraction algorithm will allow us to find $s$ and $r$ in this case, assuming they are relatively prime). It is not hard to see that we do in fact need this much precision in the worst case, as in the case of distinguishing $1/r$ from $1/(r+1)$ for $r$ close to $N$.