量子コンピュータで256ビット楕円曲線暗号は破れるか

Finally, we calculate the number of physical qubits required to break the 256-bit elliptic curve encryption of keys in the Bitcoin network within the small available time frame in which it would actually pose a threat to do so. It would require $317 \times 10^6$ physical qubits to break the encryption within one hour using the surface code, a code cycle time of $1\ {\mu}\mathrm{s}$, a reaction time of $10\ {\mu}\mathrm{s}$, and a physical gate error of $10^{−3}$. To instead break the encryption within one day, it would require $13 \times 10^6$ physical qubits.

例えば、量子コンピュータを用いて2048ビットRSA合成数の素因数分解を行う場合には、量子誤りが一切ないという理想的な環境下でも、4098量子ビットが必要であり、1012～1013回のゲート演算が必要であると見積もられています。また、量子誤りがあるという現実的な環境下では、2000万量子ビットが必要であるという見積もりもあります。

量子コンピュータの性能を測る上での指標（量子ビット数、量子誤りの大きさ、演算可能回数など）や、量子コンピュータの開発状況もあわせて考慮にいれると、近い将来に、2048ビットの素因数分解や256ビットの楕円曲線上の離散対数問題が解かれる可能性は低いと考えます。

論文¹ で使用されている量子コンピュータは53量子ビットであり、計算は合計1543回のゲート演算で構成されています。このとき、1回当たりの計算時間は、1マイクロ秒程度であると見積もられています。なお、ターゲットとする問題の性質上、量子誤り訂正は組み込まれていません。

---

1. Quantum supremacy using a programmable superconducting processor ↩︎