# Why is the number of qubits used in Shor's factoring algorithm so high?

When preparing the initial state of the algorithm to factor $n$ he computes $q = 2^l$ such that $n^2 \leq q < 2n^2$.

The first register then contains $l$ qubits. Why does this need to be so high. If we take $q=2^m$ such that $n \leq q < 2n$ we have $m$ qubits which is enoug to be able to represent all integers up to $n$.

Why does he take $l$ qubits is about half of that ($m$ qubits) would be enough?

## 1 Answer

There is a superposition of states initially, and there must be enough qubits in the circuit so that after the iterations the correct period of the function $f(x)=a^x\bmod N$ where $a$ is random and $N=pq$ can be found, i.e., the convergence should take place without wraparound effects, since we are working in a cyclic group and wraparound can introduce false alarms via accumulation.

Quoting Wikipedia:

Shor's algorithm consists of two parts:

1. A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.

2. A quantum algorithm to solve the order-finding problem.

[…]

The quantum circuits used for this algorithm are custom designed for each choice of $N$ and each choice of the random $a$ used in $f(x) = a^x \bmod N.$ Given $N,$ find $Q = 2q$ such that $$N^{2}\leq Q<2N^{2},$$ which implies $Q/r>N.$ The input and output qubit registers need to hold superpositions of values from $0$ to $Q − 1$ and so have $q$ qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least $N$ different $x$ which produce the same $f(x),$ even as the period $r$ approaches $N/2.$