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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.