「量子コンピュータが実用化されると、今の暗号は破られる」。ニュースでよく見かける一文ですが、なぜ破られるのかまで説明されることはほとんどありません。
鍵を握るのは、1994年に数学者ピーター・ショアが発表したShorのアルゴリズムです。これは「十分な性能の量子コンピュータがあれば、素因数分解を現実的な時間で解ける」ことを示した計算手順で、素因数分解の困難さに安全を預けてきたRSA暗号にとっての死刑判決に相当します。この記事では、その考え方を数式なしで解説し、「で、いつ備えるべきなのか」まで踏み込みます。
量子コンピュータは「全部試す」機械ではない
よくある誤解から片づけましょう。「量子コンピュータは無数の候補を同時に全部試せるから速い」——これは半分だけ正しく、半分は間違いです。
量子ビットは、0と1の状態を重ね合わせて保持できます。n個の量子ビットなら2のn乗通りの候補を一度に「抱える」ことはできる。ここまでは本当です。問題は、答えを読み出す瞬間にどれか一つの候補しか取り出せないことです。全部試して全部読めるなら苦労はありません。
量子コンピュータが本当に得意なのは、抱えた膨大な候補たちを干渉させて、欲しい答えだけが浮かび上がるように仕向けることです。波が重なると、山と山は強め合い、山と谷は打ち消し合いますね。あれと同じことを計算の中で起こし、間違った答えを打ち消し合わせ、正しい答えを強め合わせる。この「仕向け方」を設計できた問題だけが、量子コンピュータで劇的に速くなります。
Shorの発見——素因数分解は「周期探し」に化ける
ショアの天才性は、素因数分解という問題が、数学的な変形を通じて周期探し——ある計算を繰り返したとき、結果が何回ごとに同じパターンに戻るかを見つける問題——に置き換えられることに目をつけた点です。
そして周期探しは、まさに量子コンピュータの干渉が輝く問題でした。膨大な候補に周期的なパターンが隠れているとき、干渉を使うとその周期だけを効率よく浮かび上がらせることができるのです。周期が分かれば、あとは普通のコンピュータでの計算で素因数にたどり着けます。
結果として、古典コンピュータでは桁数が増えると爆発的に時間がかかる素因数分解が、量子コンピュータでは現実的な時間で解ける見込みになりました。しかも同じ枠組みで、TLSなどで広く使われる楕円曲線暗号も破れます。現在のインターネットの鍵交換と電子署名の主力が、まとめて射程に入ってしまったのです。
「まだ先の話」と言い切れない理由——HNDL
では現在の量子コンピュータで暗号は破れるのか。答えはノーです。RSA 2048ビットを破るには、誤りを訂正しながら安定して動く大規模な量子コンピュータが必要で、現在の機体は規模も誤り率もまだ遠く及びません。実現時期の見積もりは専門家の間でも「2030年代」から「もっと先」まで幅があります。
それでも各国政府や金融機関が今動いているのには、明確な理由があります。HNDL（Harvest Now, Decrypt Later：今収穫して、後で解読する）と呼ばれるリスクです。
- 攻撃者は今のうちに暗号化された通信やデータを大量に保存しておく
- 量子コンピュータが実用化された時点で、まとめて復号する
つまり、10年後も秘密であってほしい情報——個人情報、医療情報、設計図、外交・防衛情報、長期契約——は、将来ではなく今この瞬間から危険にさらされていることになります。「量子コンピュータはまだ先」は暗号が破られる時期の話であって、備えを始める時期の話ではありません。各国が耐量子暗号への移行を前倒しで進めているのは、この時間差の論理によるものです。
