技術要約: ECDSA.Fail: ショアのアルゴリズムにおける楕円曲線加算最適化のためのオープン・オートリサーチ

1. 問題提起

本論文は、ショアのアルゴリズムにおける楕円曲線離散対数問題（ECDLP）を解く際の決定的なボトルネックである、楕円曲線上の点加算のための可逆量子回路の最適化について扱っている。具体的には、ビットコインやイーサリアムの基盤となるsecp256k1曲線に焦点を当てている。

主な目的は、時空にインスパイアされたコスト指標 $S = Q \times T$ を最小化することである。ここで：

• $Q$: ピーク論理量子ビット幅（空間）。
• $T$: 平均実行トフォリ（Toffoli）ゲート数（非クリフォード演算量）。

ベンチマーク・タスクは、蓄積器 $R$ が量子データであり、加数 $A$ が古典的に指定される可逆混合点加算（$R \leftarrow R + A$）回路の実装である。この回路は、「クリーン」であること（アンシラ量子ビットが $|0\rangle$ に戻ること）および「フェーズ・クリーン」であること（残留位相がないこと）が求められる。これは、ショアのアルゴリズムのような、より大規模でコヒーレントなアルゴリズム内で正しく機能するために不可欠である。

2. 手法: オープン・オートリサーチ（Open Autoresearch）

本論文は、オープン・オートリサーチと呼ばれる新しい研究パラダイムを導入し、その実例を示している。個々の専門家や小規模なチームによって駆動される従来の研究とは異なり、このアプローチでは、公開リーダーボードを介して人間とAIエージェントからなる異種混合のコミュニティが、競争および協調を行う。

• メカニズム: 参加者は共有リポジトリに対して回路の修正案を提示する。これらは、古典的な正当性、アンシラのクリーンネス、およびフェーズのクリーンネスを検証する機械検証可能な評価器によって評価される。テストセットは、フィアット・シャミア・ハッシュ関数を用いて派生した、提出内容に依存する決定論的なものである。
• プロセス: 検証された改善策は、さらなる最適化のための公開された「ベース（基盤）」となる。このプロセスはオープンかつ観察可能であり、累積的であるため、独立した人間とエージェントのチームは、事前の調整なしに互いの成果の上に積み上げることができる。
• ツール: 参加者は、高レベルの戦略やドメイン制約に基づいた人間のステアリング（操舵）に従いつつ、仮説生成、コード実装、およびデバッグのために、大規模言語モデル（LLM）エージェント（Claude Code、Codexなど）を活用した。

3. 主な貢献

A. オープン・オートリサーチ・パラダイム

本論文は、以下の特性を持つフレームワークを定式化した：

1. 検証可能な目的: 問題は、効率的に計算可能で機械検証可能な指標によって定義される。
2. 累積的な探索: 独立したエージェントが、共有の公開記録に対して成功と失敗を寄与する。
3. 人間とエージェントの相乗効果: 人間はアーキテクチャの方向付けと結果の解釈を行い、エージェントは実装、反復的な実験、および局所的な最適化を担当する。
   本論文は、評価が容易かつ信頼できる場合において、このモデルが最前線の最適化問題に対して有効であると主張している。

B. 最前線の回路最適化

このチャレンジは、secp256k1の点加算に関するリソース見積もりの大幅な削減をもたらした。主なアーキテクチャ上の革新は以下の通りである：

• ジャンプ2（Jump-2）ユークリッド算法: ダイアログGCD（記録および再生）アルゴリズムを再タイミング化したもので、連続するユークリッドステップをマクロステップとしてグループ化することで、比較とスワップの回数を削減する。
• ベース5トランスクリプト・コーデック: 3つのJump-2シンボル（8つの状態のうち5つのみが有効な状態）を、9個ではなく7量子ビットのレジスタにエンコードする圧縮技術であり、可逆的な再生に必要なトランスクリプトのストレージを大幅に削減する。
• 比較フリー・ピンポン・ダイアログGCD: カットオフ後のアーキテクチャであり、低ビットのパリティチェックと交互の更新方向を用いることで、全幅の大きさの比較を排除し、量子ビット幅を犠牲にしてトフォリ数を削減する。
• レジスタ共有拡張ユークリッド算法（EEA）: 縮小する剰余と増大するベズート係数を共有の物理バンクに詰め込む、アグレッシブなレジスタ共有戦略（LuoらおよびTrailMixに由来）であり、極端な幅の削減を可能にする。
• 特化した算術: 擬似メルセンス剰余減少と定数伝播を用いたカラツバ（Karatsuba）二乗計算の実装により、古典的な入力に基づく冗長な演算を排除する。

C. 包括的な公開記録

本プロジェクトは、400件以上の昇格されたサブミッションを含む、完全かつソース監査可能な履歴を公開した。これには以下が含まれる：

• リソース改善の全軌跡。
• 最適化メカニズム（デッドコード削除、レジスタ割り当て、アルゴリズム置換など）による400件の受理されたコミットの分類。
• すべての報告された動作点の独立した検証を可能にする再現可能なアーティファクト。

4. 結果

パフォーマンス指標

データカットオフ時（2026年7月26日）において、チャレンジは以下の成果を達成した：

• ベースライン: $Q = 2,715$, $T = 3,960,753$, $S \approx 10.75$ 億。
• 最良の $Q \times T$ 回路 (8e9c9a2): $Q = 1,151$ および $T = 1,299,453$ に削減され、$S \approx 1.496$ 億 を実現。
  • これはスコアの 86.1% の削減 を意味する。
  • このスコアは、以前に報告されたGoogle/Babbushらの動作点（約2.993B）よりも50%以上低い。
• 最良の低量子ビット回路 (b6f2b0a): $Q = 825$（その後、カットオフ後の提出により813に改善）を達成し、$T \approx 4.89$ 億であった。
• カットオフ後の改善: 「ピンポン」バリアント（3616dbf）は、スコアをさらに $S \approx 1.259$ 億 ($Q=1,321, T=952,707$) まで低減させた。

先行研究との比較

最良の $Q \times T$ 回路は、$Q$ および $T$ の両方の軸において、Google/BabbushおよびSchrottenloherによって報告された動作点を下回っている。本論文は、数値的なスコアは優れているものの、インターフェースの違い（ベンチマークは古典的な加数を使用しているが、ウィンドウ化されたショアはコヒーレントな加数を使用する）および計数慣習の違いにより、形式的な支配（dominance）は成立しないと注記している。

ウィンドウ化への適合性

著者らは、最良スコアの回路のウィンドウ加算適合バリアントを構築した。このバリアントは、QROMを介して加数をコヒーレントに受け取り、11量子ビットと約29.6%のトフォリオーバーヘッドを加える。これにより、経験的な成功確率 $\hat{p} \approx 0.998$ を維持し、リトライ調整後のプロキシスコア $\approx 1.961$ 億を実現しており、依然としてGoogle/Schrottenloherのポイントを下回っている。

5. 重要性と主張

本論文は、2つの異なる領域において重要性を主張している：

1. 暗号リソースの見積もり: 本結果は、secップ256k1の点加算に関して、カットオフ時点で報告されている最も低い数値的 $Q \times T$ スコアを提供している。これらの数値は、楕円曲線暗号を打破するために暗号学的に関連する量子コンピュータ（CRQC）が必要とする論理リソースの理解を精緻化するものである。ただし、本論文はこれらが完全なフォールトトレラントのリソース見積もりではないこと（物理的なエラー訂正、ルーティング、および完全なショアの統合を省略していること）を明示している。

2. 手法の妥当性検証: 本論文は、オープン・オートリサーチの最初の規模のデモンストレーションとしてECDSA.Failを提示している。これは以下を証明している：

   • 人間とAIエージェントのコミュニティは、孤立したチームよりも速く、困難な最適化問題を集団的に解決できる。
   • オープンな共有、機械検証可能な検証、およびエージェント規模の実験の組み合わせが、累積的な研究プロセスを生み出す。
   • 人間の判断は、ステアリング、結果の解釈、および概念的なギャップを埋めるために依然として不可欠であるが、エージェントは実装と反復的な洗練において優れている。

著者らは、結果が特定のベンチマークにおける動作点であり、有限の検証サポートに基づいていることを強調し、控えめな立場をとっている。彼らはsecp256k1を破った、あるいは決定的な「Q-day」のタイムラインを確立したと主張しているのではなく、将来のリソース見積もりおよびポスト量子移行計画のための、透明性が高く再現可能な、大幅に改善されたベースラインを提供したと述べている。