In Nielsen and Chuang's book: Quantum computation and quantum information (2016), there is an example in Box 5.4 which shows how to factor $15$ using Shor's algorithm. I am confused about a particular point in this example. They start with the state $|0\rangle|0\rangle$ and create the state $$ \frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}|k\rangle|0\rangle=\frac{1}{\sqrt{2^t}}\left[|0\rangle+|1\rangle+...+|2^t-1\rangle\right]. $$ The text says they are choosing $ t=11 $ to ensure an error probability $ \epsilon $ of at most 1/4. I have been trying to figure out where this comes from. Looking back to equation $(5.35)$ it says that $$ t=n+\Big{\lceil}\log\left(2+\frac{1}{2\epsilon}\right)\Big{\rceil}. $$ For 15, $ n=4 $, right? How does $ t=11 $ work out?

Update: Okay, I have been doing alot of searching through this book and on the internet. I have come to Box 5.2 in Nielsen and Chuang (2016) and I find an expression that gives $ t=1 $. Quoting the text: "We use $ t=2L+1+\lceil\log(2+1/(2\epsilon))\rceil=\mathcal{O}(L) $, so a total of $ t-1-\mathcal{O}(L) $ squaring operations is performed at a total cost of $ \mathcal{O}(L^3) $ for the first stage." So that is where the $ t=1 $ comes from. Going back to the expression for $ t $, this works if $ n\rightarrow 2L+1 $. According to page 227 of the text (Nielsen and Chuang, 2016), this gives and estimate for the phase accurate to $ 2L+1 $ bits. Still feeling a bit confused, but I think things are becoming clear.


1 Answer 1


TL;DR: We need enough bits of accuracy in the approximation $\tilde\varphi_s\approx\frac{s}{r}$ computed by Quantum Phase Estimation so that the classical continued fractions algorithm, which is subsequently applied to $\tilde\varphi_s$, can determine the denominator $r$. This can be guaranteed if we use $n=2L+1$ bits of accuracy.


A key part of factoring an $L$-bit composite integer $N$ using Shor's algorithm is the computation of the order $r$ modulo $N$ of an integer $x$ randomly selected from $\{2,3,\dots,N-1\}$. This part consists of two subroutines, one quantum and one classical. First, we apply Quantum Phase Estimation to a unitary with eigenvalues $\exp\left(\frac{2\pi i s}{r}\right)$ in order to compute an $n$-bit approximation $\tilde \varphi_s$ to the phase angle $\varphi_s=\frac{s}{r}$ for some $s=0,1,\dots,r-1$. Next, we use classical continued fractions algorithm to find $r$ from $\tilde\varphi_s$.

Register size

The number $t$ of qubits in the first register in Quantum Phase Estimation depends on two parameters: acceptable error probability $\varepsilon$ and the number $n$ of bits of accuracy in the desired approximation $\tilde\varphi_s$ to $\varphi_s$

$$ t=n+\left\lceil\log\left(2+\frac{1}{2\varepsilon}\right)\right\rceil. $$

We need $\tilde\varphi_s$ to be accurate enough so that the continued fractions algorithm is able to determine $r$ from $\tilde\varphi_s$. We can achieve this using theorem $5.1$ on page $229$ in Nielsen & Chuang which says that if the approximation $\tilde\varphi_s$ is close enough to the ideal phase angle $\varphi_s=\frac{s}{r}$ then continued fractions algorithm can find$^1$ $r$. More precisely, the theorem says that if

$$ \left|\frac{s}{r} - \tilde\varphi_s\right|\le\frac{1}{2r^2} $$

then $\frac{s}{r}$ can be found by applying continued fractions algorithm to $\tilde\varphi_s$. If we compute $\tilde\varphi_s$ to $n=2L+1$ bits of accuracy then

$$ \left|\frac{s}{r}-\tilde\varphi_s\right| \le \frac{1}{2^{2L+1}}\le\frac{1}{2N^2}\le\frac{1}{2r^2} $$

and by theorem $5.1$ we can find $r$.


In the example in Box $5.4$, we have $\varepsilon=\frac14$ and $L=4$. Therefore, $n=2L+1=9$ and $t=11$.

$^1$ There are additional caveats concerning the cases when $s=0$ and when $s$ is not coprime to $r$. See Nielsen & Chuang for details.

  • $\begingroup$ Thank you very much for your answer. It is now clear where these numbers in Box 5.4 come from. $\endgroup$
    – Anne
    Commented Nov 23, 2021 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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