# Register size in factoring 15 using Shor's algorithm

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.

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.

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