Number of qubits required for Shor's algorithm to factor a number < 2^n

[tomdodd4598]

Hey there,

There are plenty of proposed implementations of Shor's algorithm which require different numbers of qubits, $q$, to be able to factor a number $N$ of size $<2^n$, i.e. a number of length at most $n$ bits. Most of these require $q$ linear in $n$; for example, this implementation requires $q=5n+1$, while this one requires $q=2n+3$.

However, I've mainly been looking at the 'naive' circuit, which I'm pretty sure the wiki article and this paper (in a special case, reduced form) uses. Am I right in thinking this circuit requires $3n$ qubits in general ($n$ for $N$ and $2n$ for the values of $x$ in the period-finding subroutine), or is there something I'm missing?

 

[.Scott]

Based on the diagram in the wiki article, it should be 3n qubits.
The QFT will only require 2n and those U functions require n.
I've read through carefully (especially those U functions) and cannot find any "intermediate" bits.
Of course, in practice there could always be more - for example, for error correction.

 

[Strilanc]

If you have arbitrarily good qubits, then the current best qubit count to run Shor's factoring algorithm is 2n+1 (https://arxiv.org/abs/1706.07884 "Factoring with n+2 clean qubits and n-1 dirty qubits"). n of the qubits are for an accumulator register storing the state of the ongoing modular exponentiation, n are for a workspace register needed during modular multiplications, and the last 1 is for holding the state of the semi-classical quantum Fourier transform (done using qubit recycling). It's possible that there might be some way to do a modular multiplication without the workspace register, but no one has found a way yet. It seems very unlikely that the accumulator register can ever be removed.

All that being said, I should caution you to not focus on this qubit count. In practice, you don't have arbitrarily good qubits and you don't just care about space but also runtime. The time sacrifices made in the contortions needed to go from ~3n qubits to ~2n qubits are enormous. And when you consider the overhead of error correction needed to protect noisy qubits, more time means more computation to protect means bigger code distance means more physical qubits per logical qubit.

When accounting for the overhead of error correction, the most efficient construction so far uses 3n + O(log n) logical qubits ( https://arxiv.org/abs/1905.09749 "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" slides https://docs.google.com/presentatio...NRsEoOZojIrq8NfGsRYbvmWr8hBhdinihhlZpRHQq/pub ) to such good effect that the final physical qubit count is lower than you get when using the 2n+3 logical qubit construction you mentioned.