ショアのアルゴリズムとは

正解：A. RSA暗号や楕円曲線暗号などの公開鍵暗号

RSA暗号の安全性は大きな数の素因数分解の難しさに、楕円曲線暗号は離散対数問題の難しさに基づいています。ショアのアルゴリズムは、量子フーリエ変換を使って周期を求めることで、これらの問題を多項式時間で解けます。古典のコンピュータでは現実的な時間で解けない長さの鍵でも、十分大きな誤り耐性量子コンピュータがあれば解読できるようになります。AES などの共通鍵暗号に対しては、グローバーのアルゴリズムによる2乗の高速化しかなく、鍵を長くすることで対応できます。

正解：C. 非常に多くのゲートを誤りなく実行する必要があり、誤り訂正で作った多数の論理量子ビットと、それを支える膨大な数の物理量子ビットが必要だから

RSA-2048 の解読には、千〜数千個程度の論理量子ビットで、数十億回規模のゲートを続けて実行する必要があります。そのため論理誤り率を極めて低くしなければならず、誤り訂正のために、1つの論理量子ビットあたり数百個以上の物理量子ビットが必要になります。2020年代の見積もりでは、誤り率0.1%程度の物理量子ビットが数十万〜数千万個程度必要とされており(前提によって大きく異なります)、現在の装置の規模とは桁違いの差があります。ただし、必要な規模の見積もりはアルゴリズムの改良で小さくなってきているので、暗号の移行の準備は早めに進める必要があります。