Cost of Modular Exponentiation in Shor's algorithm

Question

In the Shor's algorithm, we need to compute the sequence of controlled $U^{2^j}$ operations used by the phase estimation procedure, where $U$ is defined as $$ U|y\rangle=|xy\;(\mod N)\rangle\text{ for } 0\leq y\leq N-1\\ U|y\rangle=|y\rangle\text{ for } N\leq y\leq 2^L-1 $$ That means, we need the transformation $$ |z\rangle|y\rangle\to |z\rangle U^{z_t2^{t-1}}\cdots U^{z_12^0} |y(\mod N)\rangle\\ =|z\rangle|x^{z_t2^{t-1}}\times\cdots\times ^{z_12^{0}}y(\mod N)\rangle=|z\rangle|x^zy(\mod N)\rangle $$

This is done by reversibly computing the function $xz (\mod N )$ of $z$ in a third register, and then by reversibly multiplying the contents of the second register by $xz (\mod N )$, using the trick of uncomputation to erase the contents of the third register upon completion.

We use modular multiplication to compute $x^2 (\mod N )$, by squaring $x$ modulo $N$, then computes $x^4 (\mod N )$ by squaring $x^2 (mod N )$, and continues in this way, computing $x^{2^j}(\mod N )$ for all $j$ up to $t − 1$.

Then it is stated that, we use $\color{red}{t=2L+1+\log(2+1/(2\epsilon))=O(L)}$, so a total of $t−1=O(L)$ squaring operations is performed at a cost of $O(L^2)$ each (this cost assumes the circuit used to do the squaring implements the familiar algorithm we all learn as children for multiplication), for a total cost of $O(L^3)$ for the first stage.

My Understanding

In the phase estimation procedure, the probability of obtaining $m$ such that $|m-b|<e$, where $b$ is the best $t$ bit approximation of the phase $\phi$, is $P(|m-b|<e)\leq 1-\frac{1}{2(e-1)}$.

Suppose we want to approximate the phase $\phi$ to an accuracy $2^{-n}$ then $|m-b|=2^t(\phi'-\phi)< 2^t\times 2^{-n}=2^{t-n}\implies e=2^t(2^{-n}-2^{-t})=2^{t-n}-1$. Therefore, $$ P(|m-b|<e)=P(|m-b|<2^{t-n}-1)\leq 1-\frac{1}{2(e-1)}1-\frac{1}{2(2^{t-n}-2)}=1-\epsilon\\ \epsilon=\frac{1}{2(2^{t-n}-2)}\implies 2^{t-n}-2=\frac{1}{2\epsilon}\implies \boxed{t=n+\log_2\big(2+\frac{1}{2\epsilon}\big)} $$ which is the number of qubits used in the first register to obtain the phase $\phi$ accurate to $n$ bits with probability of success at least $1-\epsilon$.

With this in mind, if I approach the Shor's algorithm how does $2L+1$ comes in $t=2L+1+\log(2+1/(2\epsilon))$ ?

My understanding is that, $L$ is the number of bits needed to specify $N$, ie., second register has $L$ qubits, such that the unitary operator $U$ is $2^L-1\times 2^L-1$.

Please refer to Pages 226,228, Quantum Computation and Quantum Information by Nielsen and Chuang

Answer 1

$L$ is the number of bits of $N$, while $n$ is the number of bits of precision we want in the estimation of the phase. So your question is: why do we need $2L+1$ bits of precision?

If you check page 229 of Neilsen and Chuang, they discuss the continued fraction expansion. The idea is that we get some phase $\varphi$ which we hope will closely approximate a fraction $\frac{s}{r}$ for the secret period $r$. So the question is: how do you generate a fraction from an arbitrary real number? The answer is that you use continued fractions. These will give a progression of increasingly accurate fractions that approximate $\varphi$.

The problem is that if $\varphi$ is not close enough to $\frac{s}{r}$, then the fractions you get from the continued fraction expansion will be too far from $\frac{s}{r}$ as well, and won't give you information about $r$. Hence, they use theorem 5.1, which states that the continued fraction expansion will reach the fraction $\frac{s}{r}$ as long as

$$ \left\vert \frac{s}{r} - \varphi\right\vert \leq \frac{1}{2r^2}$$

The problem here is that the bound is $r^2$ (not just $r$). We're not exactly sure how large $r$ is, so assume $r\approx N$, and we need precision of $2r^2\approx 2N^2\approx 2(2^L)^2 = 2^{2L+1}$. Hence, $2L+1$ bits of precision.

I'm not rigorous in the last part of the derivation: to do it properly we should bound $r$ with the totient function and consider more precisely the inequalities with $N$ and $L$. But hopefully this gives you the intuition.