According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according to a paper from 2008, it is shown that it requires $6n$ qubits to solve the discrete logarithm problem as it applies to elliptic curves. What I want to know is whether or not this is the theoretical lowest number of qubits required, and whether or not this information is still up to date. For Shor's algorithm specifically, there are three questions I have. Are these statements up to date and correct?
- RSA 2048 requires, at minimum, 4099 qubits ($2048 \times 2 + 3$)
- DHE 2048 requires, at minimum, 4099 qubits ($2048 \times 2 + 3$)
- ECDHE 256 requires, at minimum, 1536 qubits ($256 \times 6$)
I know there are several similar answers on this site, but many of them are contradictory or only reference the original 2002 paper, and none of them answer whether or not this is the known theoretical lowest number of qubits required, or just the current state-of-the-art.
Another paper claims to have reduced it for integer factorization to $n+2$ "clean" qubits and $n-1$ "dirty" qubits, which is an improvement over a previous $1.5n+O(1)$ qubits, but the paper is behind a paywall and Sci-Hub doesn't seem have it at the moment.
