# Number of qubits required in Shor's algorithm

People say that the number of qubits required in Shor's algorithm for factorizing $$N$$ should be $$2\log N$$ for control register and $$\log N$$ for target register.

What is the reason why these numbers of qubits are required?

• Do you believe it can be done with fewer? Commented Sep 3, 2021 at 4:27
• you might find a few related posts at quantumcomputing.stackexchange.com/…
– glS
Commented Sep 3, 2021 at 11:50

## TL;DR

The size $$c$$ of the control register determines the success probability and approximation quality in Quantum Phase Estimation. It is chosen so that the approximation is good enough to enable the use of the (classical) continued fractions algorithm as the next step in Shor's algorithm. The size $$t$$ of the target register is simply chosen to be large enough to support arithmetic modulo $$N$$.

## Background

The only part of Shor's algorithm which uses a quantum computer is the order finding subroutine. Given an integer $$x=1,\dots,N-1$$ it computes the order $$r$$ of $$x$$ modulo $$N$$, i.e. the smallest positive integer $$r$$ such that $$x^r =1 \pmod N$$. The subroutine relies on Quantum Phase Estimation algorithm which uses two quantum registers one with $$c$$ qubits and one with $$t$$ qubits and a $$t$$-qubit unitary operator $$U$$ with eigenvalues $$\exp(2\pi i \varphi_s)$$ to compute a $$c$$-bit approximation $$\tilde\varphi_s$$ of $$\varphi_s$$ for some index $$s$$. In Shor's algorithm, $$U$$ is a unitary designed so that its eigenvalues are $$\exp\left(\frac{2\pi is}{r}\right)$$ for $$s=0,1,\dots,r-1$$. Hence, $$\varphi_s=\frac{s}{r}$$. This enables us to find $$r$$ which is subsequently used by a classical computer to try to find a non-trivial factor of $$N$$. See chapter $$5$$ in Nielsen & Chuang or Shor's paper for more details.

## Target register

The unitary $$U$$ executed on the target register is used to perform arithmetic modulo $$N$$, so $$t$$ must be large enough to hold binary representation of all integers in $$0, 1, \dots, N-1$$. Thus, the target register must be at least $$t=\lfloor \log N\rfloor+1$$ qubits long.

## Control register

The control register stores the computed estimate $$\tilde\varphi$$ of the fraction $$\frac{s}{r}$$ associated with an eigenvalue $$\exp\left(\frac{2\pi is}{r}\right)$$ of $$U$$. To find the fraction $$\frac{s}{r}$$ from the estimate $$\tilde\varphi$$ we use the (classical) continued fractions algorithm. However, the algorithm requires that $$\frac{s}{r}$$ be a convergent of the continued fraction for $$\tilde\varphi$$. This will be the case if

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

see theorem $$5.1$$ on page $$229$$ in Nielsen & Chuang or equation $$(5.13)$$ on page $$18$$ in Shor's paper. Therefore, we desire an approximation $$\tilde\varphi$$ with at least $$2\lceil\log N\rceil+1$$ qubits since then we have

$$\left|\frac{s}{r}-\tilde\varphi\right| \le \frac{1}{2^{2\lceil\log N\rceil+1}} = \frac{1}{2\left(2^{\lceil\log N\rceil}\right)^2}\le\frac{1}{2N^2}\le\frac{1}{2r^2}\tag2$$

and so $$(1)$$ is satisfied.

## Constant space overhead

Note that there is an additional constant (i.e. independent of $$N$$) overhead associated with the probability of success of the algorithm. Specifically, in order to ensure that Quantum Phase Estimation succeeds with probability at least $$1-\epsilon$$ the target register needs to consist of

$$c= 2\lceil\log N\rceil + 1 + \left\lceil\log\left(2+\frac{1}{2\epsilon}\right)\right\rceil\tag3$$

qubits, c.f. equation $$(5.35)$$ on page $$224$$ in Nielsen & Chuang.

For example, my implementation of Shor's algorithm in cirq uses $$3\lceil\log N\rceil + 3$$ qubits overall to ensure that Quantum Phase Estimation succeeds with probability $$\frac34$$.