How to factor 2048 bit RSA integers with less than a million noisy qubits
Abstract
Recently, Chevignard et al proposed a way to factor $n$ bit RSA integers using only $(0.5 + \epsilon)n$ logical qubits.
In this paper, I streamline Chevignard's algorithm and estimate its physical cost accounting for the overhead of error correction.
I reduce its Toffoli count by more than 100x, and show that this implies a 2048 bit RSA integer could be factored in less than a week using less than one million noisy qubits (compared to 20 million in Gidney+Eker{\aa} 2019).
I make the same assumptions as in Gidney+Eker{\aa} 2019: a square grid of qubits with nearest neighbor connections, a gate error rate of $0.1\%$, a surface code cycle time of 1 microsecond, and a control system reaction time of $10$ microseconds.
In this paper, I streamline Chevignard's algorithm and estimate its physical cost accounting for the overhead of error correction.
I reduce its Toffoli count by more than 100x, and show that this implies a 2048 bit RSA integer could be factored in less than a week using less than one million noisy qubits (compared to 20 million in Gidney+Eker{\aa} 2019).
I make the same assumptions as in Gidney+Eker{\aa} 2019: a square grid of qubits with nearest neighbor connections, a gate error rate of $0.1\%$, a surface code cycle time of 1 microsecond, and a control system reaction time of $10$ microseconds.
