Register size in factoring 15 using Shor's algorithm

Question

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.

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.

Background

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

Example

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