ハクソク

世界を動かす技術を、日本語で。

量子コンピュータはなぜまだ21を因数分解できないのか？

2025年8月31日原文(algassert.com)

概要

  • 2001年に量子コンピュータが15の素因数分解に成功
  • 2025年現在でも21の素因数分解は未達成
  • 21の分解が困難な本当の理由は回路コストの急増
  • 15と21の回路規模の違いは100倍以上
  • 素因数分解は量子コンピュータの進歩指標として不適切

15と21の量子素因数分解の回路コスト比較

  • 2001年、量子コンピュータは 15の素因数分解 に成功
  • 2025年 時点で 21の分解未達成、進歩がないとの誤解
  • 実際は 回路コスト の急増が主な障壁
    • 15の分解回路： エンタングルメントゲート21個
    • 21の分解回路： エンタングルメントゲート2405個
  • 15の分解回路 は Toffoliゲート2個 （各6エンタングルメントゲート）と CNOT/CPHASEゲート6個
  • 21の分解回路 は Toffoliゲート369個、 CNOTゲート191個
  • 回路規模は 100倍以上、コスト増加は予想以上

コスト増大の理由

  • Shor’s Algorithm では 条件付きモジュラー乗算 が支配的コスト
  • N=15 の場合
    • ほとんどの乗算が 1倍 （何もしないで済む）
    • 最初の乗算は 入力が1 で簡単
    • 残りの1回だけ CSWAP2回 で実装可能
    • 例：$g=2$の場合、[2, 4, 1, 1, 1, 1, 1, 1]（6回は1倍）
  • N=21 の場合
    • すべての乗算が 1以外 で全てコストがかかる
    • 例：$g=2$の場合、[2, 4, 16, 4, 16, 4, 16, 4, 16, 4]
    • 1倍の省略不可、4倍のコスト増
    • 最初の乗算の簡易性も低下、1.8倍コスト増
    • CSWAPで済まない複雑な乗算、20倍コスト増
  • これらの要因が合わさり 100倍のコスト増大

追加要因と現状

  • 2001年のNMR量子コンピュータ はスケーラビリティに問題
  • イオントラップ など他の実験もあるが、真の素因数分解は未達成
  • 量子誤り訂正 のオーバーヘッドも大きい（ゲート数・キュービット数ともに100倍以上）
  • 21の分解は15の1万倍のコスト になる可能性
  • 「21を分解した」とする論文もあるが、多くは 事前情報や不正な最適化 によるもの
    • 本質的な乗算を省略しており、実際の素因数分解とは異なる
    • 例：Smolinらの「Pretending to factor large numbers on a quantum computer」などで解説
  • 本物の量子素因数分解 は、未だに15以外で実現されていない

素因数分解を進歩指標にできない理由

  • 素因数分解の回路コストが急激に増加
  • 量子誤り訂正 や アーキテクチャのスケーリング問題 の解決が重要
  • 進歩を測るには、誤り訂正の信頼性向上や、コア技術のスケーリングに注目すべき
    • 例： surface code の信頼性向上
    • 例： neutral atom の損失補充技術

まとめ

  • 21の素因数分解が未達成 なのは、技術停滞ではなく 回路コストの急増 が原因
  • 量子コンピュータの進歩 を測るには、 素因数分解以外の指標 に注目する必要

Hackerたちの意見

じゃあ、どれくらいのゲートが必要なんだろう？「暗号的に有用な」数を因数分解するためには。今世紀中に量子コンピュータが役立つ道筋ってあるのかな？

└

さっきこれ見た： https://x.com/adamscochran/status/1962148452072124879?s=46 素人としては、複数の大規模な材料科学のブレークスルーの背後に道筋があるように思える。

└

ゲート数についてはよく分からないけど、必要な論理キュービットの数を見ると、伝統的なコンピュータがすでに因数分解した829ビットのRSA-250のような数を因数分解するには、まだまだ遠い感じだね。

└

現実的には、古典コンピュータがすでに数兆のトランジスタを持ってるから、数百万から数十億のキュービットが必要だよね。

└

じゃあ、「暗号的に有用」な数を因数分解するのに、どれくらいのゲートが必要なんだろう？これは二つの理由で難しい質問だよ。まず、「暗号的に有用」の明確な線引きがないこと。次に、そういう計算ができる量子コンピュータの正確な設計がまだ分からないこと。1985年に「意味的に有用」なニューラルネットワークを構築するのにどれくらいの従来のゲートが必要かを推定するのと似てる。でも、答えはほぼ確実に数百万だと思う。 [UPDATE] 予測が難しい第三の理由は、量子誤り訂正において、原始キュービットの誤り率と信頼性のある誤り訂正された仮想キュービットを構築するのに必要なゲート数のトレードオフがあること。原始キュービットの誤り率が低いほど、必要なゲート数は少なくなる。今のところ、どのくらいの原始誤り率が達成できるかは分からない。 > 量子コンピュータが今世紀に役立つ道筋ってあるのかな？今世紀はあと75年残ってるけど、それってテクノロジーの時間では永遠だよね。75年前の古典コンピュータの最先端は（ちょっと甘く見て）ユニバックだった。現代のコンピュータと比べてどれだけパワーが劣っていたかを考えるのは面白いよ、特にops/wattの観点でやると。計算はしてないけど、桁違いに多いと思う。もし量子コンピュータでも同じ進歩が達成できれば、2100年までには前量子暗号は確実に終わりだね。古典コンピュータの改善にはトランジスタという一つのブレークスルーが必要だったけど、量子コンピュータにはそれに相当するものがまだない。いつそれが起こるかは分からないけど、誰かが初めて解決するまでは全てが不可能に思えるんだ。

└

RSA 4096には、10^7のキュービットと10^-4の誤り率が必要だよ（桁の大きさね）。数百のキュービットでその低い誤り率を持って、すでに有用で価値のある量子化学計算ができるし、ポスト量子アルゴリズムが日々一般的になってきて、暗号解読用の量子コンピュータを作るインセンティブが減ってきてると思う。量子コンピュータは、暗号に使うのが難しい方向で最も早く進展すると思う。

└

最新の数字は、約1e6キュービットでエラー率が1e-4だって。 https://arxiv.org/abs/2505.15917。OPが言ってるゲートの意味では、エラー訂正された文脈での量を定量化するのは難しいんだ。自分のコードにネイティブな操作にコンパイルしたらね。1MHzの「クロック」（コードサイクル時間、専門家向け）を仮定すると、計算時間は約1週間くらいになる。ある意味、これはキュービットの数よりも達成が難しい指標かもしれない。量子エラー訂正の魔法（エラー率の指数的改善）は両方に作用するから、もしキュービットの忠実度がさらに9上がれば、キュービットの数もかなり改善されるよ。一方で、計算をいくつかのシステムに分ける必要があると、状況はかなり悪化する。

└

じゃあ、いくつのゲートがあれば「暗号的に有用な」数を因数分解できるの？ [1]の表5では、2048ビットのRSA整数を因数分解するのに70億のトフォリゲートが必要だと推定してる。 > 量子コンピュータが今世紀に役立つ道筋はあるの？ 数十億のゲートを実現するための道筋は量子エラー訂正だよ。[1]では、物理的な仮定に基づいて、25のサーフェスコードがその70億のゲートに十分だと推定してる。これで、1400の論理キュービットから100万の物理的なノイズのあるキュービットに増えるんだ。サミュエル・ジャックは今年のPQCryptoでかなり良い講演をしていて、そこでタイムラインについて推測してるよ [2]。（このブログ記事と[1]の著者です。） [1]: https://arxiv.org/pdf/2505.15917 [2]: https://www.youtube.com/watch?v=nJxENYdsB6c

それって、例えばRSA1024みたいな「暗号的に興味深い」数を因数分解するために必要な回路のサイズ（そして実現可能性）について、どういう意味になるの？

└

「（ちょっと余談だけど、この因数分解-21回路にかけられた最適化の量は、大きな数を因数分解する際に可能なものとは多分かけ離れてると思う。もっと現実的な最適化の量だと、因数分解-15回路の500倍のコストの回路ができるだろうけど… 100倍のオーバーヘッドでも十分に私のポイントを伝えられる。ともあれ、この回路で使われている条件付き4での乗算サブルーチンを見つけるために高額なコンピュータ検索を行ってくれたノア・シャッティに特別な感謝を。）」

└

ちょっと話が逸れるけど、暗号学者たちは新しいギガワットデータセンターでRSA1024を因数分解するのは不可能だと確信してるの？最速の既知のアルゴリズムでも、合理的な時間内に因数分解するにはまだ遅すぎるみたいだけど。近い将来にこれらのアルゴリズムに改善がないという合意があるの？

└

RSA1024のコストの推定は、4ビットのケースから外挿するんじゃなくて、ターゲットサイズでの明示的な回路構造を使ってるんだ。だから、投稿で指摘されている不連続性も暗黙的に考慮されてる。だから、この投稿はそのコストには影響しないよ。

Hacker Newsで議論の続きを見る