# Cost of Modular Exponentiation in Shor's algorithm

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|, where $$b$$ is the best $$t$$ bit approximation of the phase $$\phi$$, is $$P(|m-b|.

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| 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$$.

$$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.