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

• 2001年に量子コンピュータで15を素因数分解して以降、進展がないように見える現象の説明
• 21を素因数分解する回路には、15を素因数分解するときより100倍多いエンタングリングゲートが必要
• この差は、条件付きモジュラー乗算の複雑さと、15にだけ適用できる特別な最適化によるもの
• 量子誤り訂正とハードウェアの限界も、21の素因数分解までの障壁をさらに高くしている
• これまでに報告された21の素因数分解の多くは、真の意味での乗算を実行せずにトリックを使ったもの

---

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

15の素因数分解の後に21の素因数分解が登場していない理由

• 2001年に量子コンピュータで15を素因数分解した実験があった
• 2025年になっても、まだ21の素因数分解の成功例はない
• この点を根拠に、量子コンピュータにはまったく進展がないという認識が広がっている
• しかし実際には、15と21の素因数分解回路を比べると、はるかに驚くべき理由がある

15の素因数分解回路と21の素因数分解回路の構造的な違い

• 15の素因数分解回路は、**量子ゲート21個（エンタングリングゲート21個）**だけで実装できる
  • 6個の2量子ビットエンタングリングゲート（CNOTおよびCPHASEゲート）と
  • 2個のToffoliゲート（それぞれ6個のエンタングリングゲートに分解）、合計21個のエンタングリングゲートで構成される
• 21の素因数分解回路には、191個のCNOT、369個のToffoli、合計2405個のエンタングリングゲートが必要
  • 15を素因数分解するときより115倍多いエンタングリングゲートの負担が発生
  • 回路規模は単に25%や2倍増えるのではなく、100倍以上高コストになる
• 回路最適化の水準を考慮しても、500倍の差が現実的にあり得るように見える

なぜこれほど大きな差が生じるのか

• 量子素因数分解回路（Shorのアルゴリズム）では、支配的なコストは条件付きモジュラー乗算にある
  • nビットの数Nに対して、複数回にわたり条件付きでアキュムレータにモジュラー乗算を実行する必要がある
  • このとき15の場合、8回の条件付き乗算のうち6回は、**1の乗算（何もしない）**として処理できる
    • 最初の乗算は入力が1なので、ほぼ無料で実装できる
    • 2回目（残る1回）も、2回のCSWAPで安価に処理できる
    • その結果、実際にコストを払う必要があるのは2回だけ
    • この構造は15にだけ当てはまる特殊な性質で、1に近い乗算が多数あるため負担が著しく小さい
• しかし21の場合は乗算がどれも1ではなく値も多様なので、すべての乗算にコストがかかる
  • 8回の乗算すべてにコストが発生し、単純に4〜5倍ではなく20〜100倍に増える
  • 4倍や16倍のような乗算は、CSWAP（条件付きスワップ）で実装できる構造ではない
  • 乗算の複雑さはそれぞれ異なり、最適化も容易ではない

ハードウェアおよび誤り訂正の現実的な限界

• 過去（2001年）の15の素因数分解は、NMR量子コンピュータで実装され、スケール拡張に多くの限界があった
• さらに、量子誤り訂正の必要性も大きくなる
  • ゲート数が100倍増えるなら、エラー率は100倍低くなければならない
  • 実際にはqubit数も100倍増やす必要がある可能性があり、全体コストは10,000倍まで上昇し得る

素因数分解の試みをめぐる論争と誤った結果

• 最近のいくつかの論文では、量子コンピュータで21の素因数分解に成功したと主張しているが
  • 実際にはアルゴリズムの乗算実行を省略したり、結果をあらかじめ知ったうえで回路を単純化したケースが多い
  • 本物の乗算演算を行っていない以上、それを素因数分解と見なすことはできない
  • 単なる「周期探索」と素因数分解の本質的な違いを無視した結果である
• 一部の論文は露骨にトリックを使っており、その研究を風刺する論文まで出ている
  • 素因数分解チャンピオン記録の再現実験など、複数の風刺論文が存在する
  • Variational factoring など、スケール拡張の根拠がないベンチマークばかりが繰り返し登場している

量子コンピュータの正しい進展指標は何か

• 現時点では、素因数分解は量子コンピュータ進展の主要ベンチマークではない
  • 15を超えるとコストが急増し、実用的な検証が難しくなる
• むしろ、**量子誤り訂正の導入（例: surface codeの改善）**や
  • **スケーリング問題を解決するハードウェアアーキテクチャの変化（例: 中性原子の継続的な入れ替えなど）**が
  • 実質的な進展を示す、より重要な観測点である

[GN⁺]

Hacker Newsの意見

• これまで実際には、これより小さい数を因数分解したことすらなかったことに起因している。もしプログラムのコンパイル過程がすでに答えを知っていなければ動かない形なら、それは本当の因数分解ではなく、単に「3を出力」しているだけだと思う

• 実際に暗号学的に意味のある数を因数分解するには、どれだけの quantum gate が必要なのか気になる。今世紀中に実用的な量子コンピュータが出てくる現実的な道筋があるのかも知りたい

  • 2048ビットRSAの因数分解には、およそ70億個の Toffoli gate が必要だという論文の Table 5 の推定値を例として挙げられる(論文リンク)。数十億回の演算を達成する方法は、まさに量子誤り訂正であり、論文では distance 25 surface code で十分だとしている。この場合、論理キュービット1,400個から、実際のノイズのあるキュービット約100万個へと拡張される。PQCrypto での Samuel Jacques の講演も参考になる(YouTube)。私はこのブログと関連論文の著者である
  • この質問が難しい理由は2つある。第一に、「暗号学的に有意」という境界を引けないこと。第二に、実際にこの演算を行える QC のアーキテクチャがまだ明確に分かっていないこと。1985年にニューラルネットワークを作るのに必要な従来型論理ゲート数を見積もるのに少し似ている。それでも、数百万個以上のゲートが必要なのは確かそうだ。第三に、量子誤り訂正では、より低い物理キュービットの誤り率と、信頼できる誤り訂正済み仮想キュービットを構築するのに必要な gate 数の間にトレードオフがある。今後、物理キュービットの誤り率がどこまで下がるのかはまだ分からない。過去75年間のコンピュータの発展に似た進歩が量子コンピュータにも起きるなら、2100年ごろには既存の暗号は完全に無力化されるだろうと推測する。トランジスタのような一度きりの革新が現れるまでは予測が難しい。技術の進歩はいつも不可能に見えるが、誰かが最初の方法を見つければ状況は変わる。(UNIVAC I の説明)
  • 最近の関連ツイートも参考になる(ツイートリンク)。一般人の立場から見ると、その道筋は巨大な材料科学上の革新が何度も必要で、見えにくくなっているように思える
  • RSA 4096 の場合、10^7 キュービットに誤差率 10^-4 が大まかに必要になる。すでに100個前後のキュービットだけで有用な量子化学計算が可能であり、ポスト量子アルゴリズムの普及が進むにつれて、暗号解読用量子コンピュータを開発する動機は弱まっている。量子コンピューティングは暗号とは無関係な方向でより速く発展していくと思う
  • 最新の数字では、誤差率 1e-4 で約100万キュービットが必要とされる(論文リンク)。gate 数はコードレベルで実際の演算に応じて異なって測定され、1MHz の「クロック」(コードサイクル時間)基準で計算全体に約1週間かかる。キュービット数よりも計算時間の達成のほうが難しいメトリクスだ。量子誤り訂正の魔法のような効果(誤り率が下がるほど必要キュービット数が大きく減る)のおかげで、キュービット品質が1段階向上すると必要キュービット数は急減する。一方で、複数システムに演算を分割しなければならないなら状況はかなり悪化する

• 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' という論文が興味深い(論文を読む)

• RSA1024 のような暗号学的に意味のある数の因数分解回路の規模と実現可能性に関心がある

  • RSA1024 のコスト推定は、小さな数(4ビットなど)から単純にスケールさせたものではなく、実際の規模に合った回路設計を通じて算出されている。つまり、今回の文章で言及された不連続性の問題はすでに暗黙に反映されている。したがって、この投稿は既存のコスト推定には影響しない
  • (参考: 21 の因数分解回路の最適化は、大きな数を因数分解するときには適用しにくいはずだ。15 の因数分解回路と比べて500倍のコストのほうが現実的かもしれない。もちろん、100倍のオーバーヘッドでも論旨を説明するには十分だ。Noah Shutty がその回路最適化のために高価なコンピュータ探索をしてくれたことに特別な感謝を表したい)
  • 話題から少し外れるが、最近の超大型データセンターでも RSA1024 を因数分解するのは実質的に不可能だと暗号学者たちが確信しているのか気になる。現時点では最速のアルゴリズムでも現実的な時間内には因数分解できない。しかし、このアルゴリズムに近いうちに画期的な改善は起きないだろう、という点について合意があるのか意見を聞きたい

• いつか量子コンピュータが post-quantum RSA を狙えるようになるのか気になる(関連論文)。通常の RSA 演算(鍵生成、暗号化、復号)は Shor アルゴリズムに対して非対称に有利なので、十分に大きな鍵さえ使えばよいという見方もある。これは Merkle パズルに似た効果で、攻撃者は必ず量子コンピュータで攻撃しなければならないという条件が追加される。以前、ギガビットRSA公開鍵を作ってみたことがある(鍵ファイル)。フォーマットは、4バイト little-endian の鍵バイト数、続いて鍵、そのあと鍵の逆数(256^bytes で mod)。公開指数は 3 である

  • Post-Quantum RSA は、djb が「大きな鍵を使えば安全なんじゃないか」という質問に対応するために作ったジョークだ。1TB の鍵で、暗号化1回あたり100時間かかるように設計されている。量子コンピュータでも破れない

• 「error corection」という誤字を見て、ちょっと面白かった

• 「因数分解-15と比べて500倍の回路コスト」の部分が理解しづらい。著者はすでに115倍の例を出しているのに、追加の最適化がどうしてさらに悪い結果をもたらすのか気になる

  • 小規模な数の因数分解回路の作成に投入された膨大な最適化作業量は、大きな数では現実的に不可能だという意味だ。つまり一般には、因数分解する数が大きくなると、おおよそ500倍のゲート増加が必要だと考えるのが直感的であり(115倍のように少なくはない)
  • 実際、大規模では最適化の効果は薄れ、N=21 回路のような利益は大きくないだろう
  • 最小限の実装は不安定で、信頼性を保証しにくい。実用的な回路開発には、安定したキュービット確保のための多くの研究が必要で、「デコヒーレンス時間」のような概念も言及される。したがって、キュービット数は爆発的に増えざるを得ない
  • 115倍というのは、(現実的ではない)大量の最適化を加えた結果である

• この投稿の要点は、Schorr の因数分解に必要な Big-O の回路量が超多項式だと示唆しているのか疑問だ

  • 文章の内容によれば、ゲートコストは主に O(n) 回のモジュラー乗算から生じ、各演算は O(n^2) ゲートで実装できる。全体としては、最悪の場合でもおおよそ3次(キュービック)の複雑性に見える

• PQ(ポスト量子)暗号技術が導入される理由は、必ずしも QC がすぐに登場すると確信しているからではない。技術開発の速度次第で、QC がいつ現れるかは不確実だ。暗号技術の目標は、理論的にもほとんど破れない方法を見つけることであり、理論的に攻撃可能なら物理的にも可能性があるので必ず備える。ECC や RSA には理論上の経路が確認されており、実在する装置がなくても攻撃可能と見なされる。したがって、QC がないうちから備えておくのは十分に合理的な見通しだ。一方、SHA2、AES、ChaCha などには現実的な攻撃経路が見えていないので、今すぐの置き換え計画はない。暗号化は QC の唯一、あるいは最重要の応用先ではない。物理系、タンパク質フォールディング、機械学習など、さまざまな分野でまだ未知の革新が出てくるだろうという期待がある

  • タンパク質フォールディングなどの分野で今後さらに発展の余地があるのか気になる(AlphaFold 以後でも)。(参考記事)

  • 対称鍵暗号 (AES, ChaCha, SHA-2) の場合、量子攻撃の効果は実質的に鍵長が半分になるのと同じだ(3DES と 2DES の例のように)。実際には量子コンピュータの性能が同等とは限らないので単純に半分と断定はできないが、AES-256 に置き換えればよく、問題はない。だが、注目すべきなのは Key Exchange だ。なぜなら Key Exchange は、秘密鍵を双方が直接出さずに合意するために使われるからだ。Quantum Computer があれば、過去の会話を記録しておいたものも読めるようになる。署名アルゴリズムが破られても過去にさかのぼって署名することはできないが、Key Exchange は一度破られると過去の会話もすべて露出するため重要である。Key Exchange の安全な代替が急務だ