Resource Requirements

Every practical question about quantum advantage comes down to resources: how many qubits does the algorithm need, and how many elementary gates must those qubits execute reliably? For Shor's algorithm, both answers are polynomial in $n = \lceil \log_2 N \rceil$ , the bit-length of the number $N$ to be factored. This lesson derives the estimates from first principles and puts them in the context of current hardware.

Qubit count

The period-finding circuit uses two registers.

Input register. We need $2n$ qubits so that the QFT window $Q = 2^{2n}$ satisfies $Q \geq N^2$ . This ensures the continued-fraction step succeeds with constant probability. Since $N \leq 2^n$ , we have $N^2 \leq 2^{2n} = Q$ , so $2n$ qubits are sufficient and necessary.

Work (ancilla) register. Storing the value $a^x \bmod N$ requires at most $n$ qubits, because $a^x \bmod N \in \{0, 1, \ldots, N-1\}$ and $N \leq 2^n$ .

Additional ancilla. The reversible circuits that implement modular multiplication need extra workspace to avoid overwriting inputs. Efficient implementations use $O(n)$ ancilla qubits; the exact constant depends on the chosen adder design.

Putting these together, the logical qubit count is

$Q_{\text{logical}} = 2n + n + O(n) = O(n).$

For the textbook target of cracking $2048$ -bit RSA ( $n = 2048$ ), this is roughly $6000$ to $10000$ logical qubits, depending on the circuit optimisation.

Gate count

The three algorithmic stages contribute the following gate counts.

Hadamard layer

Applying $H^{\otimes 2n}$ to initialise the input register costs exactly $2n$ single-qubit gates — negligible compared with the other stages.

Modular exponentiation

The modular-exponentiation oracle $|x\rangle|0\rangle \mapsto |x\rangle|a^x \bmod N\rangle$ is implemented as a sequence of $2n$ controlled modular multiplications: for each bit $x_k$ of the exponent, apply a modular multiplication by $a^{2^k} \bmod N$ controlled on qubit $k$ . Each such multiplication is built from modular additions, which in turn use $O(n)$ Toffoli gates and $O(n)$ ancilla qubits. The total gate count for modular exponentiation is therefore

$G_{U_f} = O(n) \times O(n) \times O(n) = O(n^3).$

This is the dominant term in the gate budget.

Inverse QFT

The $2n$ -qubit inverse QFT requires

$G_{\text{QFT}} = \frac{2n(2n-1)}{2} = O(n^2)$

rotation gates and Hadamards. This is a lower-order contribution compared with $O(n^3)$ from modular exponentiation, but it must be implemented to very high precision since the rotation angles scale as $2\pi / 2^k$ for $k$ up to $2n$ .

Total gate complexity

Combining the three stages,

$G_{\text{total}} = O(n^3).$

The exact leading coefficient depends on the modular arithmetic implementation; optimised circuits achieve roughly $100\,n^3$ Toffoli gates for practical implementations.

Concrete numbers for RSA-2048

For $N$ with $n = 2048$ bits, the estimates are:

| Resource | Order of magnitude | |---|---| | Logical qubits | $\approx 6000$ | | Toffoli gates | $\approx 10^{12}$ | | T-gates (fault-tolerant) | $\approx 10^{13}$ | | Physical qubits (surface code, low noise) | $\approx 10^6$ |

The T-gate count is an order of magnitude larger than the Toffoli count because each Toffoli decomposes into $7$ T-gates in the Clifford+T basis, and fault-tolerant T-gate injection adds further overhead.

Circuit depth

Beyond gate count, the circuit depth (the critical path when gates are parallelised) matters because shallow circuits are less exposed to decoherence. With full parallelisation, the depth of modular exponentiation can be reduced from $O(n^3)$ to $O(n^2 \log n)$ using carry-lookahead adders. The QFT depth reduces to $O(n)$ with nearest-neighbour architectures. In practice, the achievable depth depends heavily on the qubit connectivity graph of the hardware.

Why polynomial is not the same as easy

A gate count of $O(n^3)$ is polynomial and therefore asymptotically efficient, but the constants matter. At $n = 2048$ the raw Toffoli count exceeds $10^{12}$ operations, each of which must succeed with extremely high fidelity under fault-tolerant encoding. Current superconducting processors execute $O(10^3)$ two-qubit gates reliably before errors accumulate. The gap between today's devices and Shor-capable hardware is a central driver of post-quantum cryptography standardisation.

Comparing the two registers

The input register ( $2n$ qubits) is larger than strictly necessary to hold the exponent ( $n$ bits) because the QFT must operate over a window at least $N^2$ to give the continued-fraction algorithm enough resolution to distinguish nearby fractions $j/r$ . Specifically, if $Q = 2^{2n}$ and two valid approximations $j_1/r$ and $j_2/r$ differ by at least $1/(2N^2)$ , then their integer encodings $\lfloor j \cdot Q / r \rceil$ differ by at least $1$ , making them distinguishable after a single measurement. This is why $2n$ — not $n$ — qubits are the right size for the input register.

Summary

Shor's algorithm factors an $n$ -bit number using:

$O(n)$ logical qubits (roughly $3n$ in a careful count),
$O(n^3)$ elementary quantum gates (dominated by modular exponentiation),
$O(\log n)$ repetitions on average to extract $r$ from continued-fraction approximations.

All three quantities grow polynomially in $n$ , establishing a provably exponential advantage over the best known classical factoring algorithms. The remaining gap to practical deployment is engineering rather than algorithmic: building fault-tolerant logical qubits at scale.