12
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.