Shor's Algorithm for ECDLP — Q-Day Prize提出物

楕円曲線離散対数問題(ECDLP)のための量子ソルバー。Project Elevenが主催するQ-Day Prize Challengeのために構築されました。目標: 実際の量子ハードウェア上でShorのアルゴリズムを用いてECC秘密鍵を回復すること。

• 著者: Giancarlo Lelli
• 連絡先: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• 背景: エンタープライズソフトウェア、フルスタックアーキテクチャ、クラウドネイティブ開発において10年以上の経験を持つテクノロジーリーダー。コンピュータサイエンスのバックグラウンドを持ち、.NET、Python、Rust、Cloudエコシステムにわたる実践的な経験があります。現在は、ソリューションアーキテクチャとセールスエンジニアリングに焦点を当てたCloud GTMスペシャリストとして働いています。

アプローチ

すべてのチャレンジ曲線は、F_p上の y^2 = x^3 + 7 (a = 0, b = 7) を使用しており、secp256k1ファミリーと一致しています。ソルバーはECDLPのためのShorのアルゴリズムの2レジスタバリアントを実装しています:

1. 計数レジスタ|j>、|k>を一様重ね合わせ状態に準備する(アダマール)
2. 2t個の制御付き点加算により|j>|k>|jG + kQ>を計算する(t = 計数量子ビット数)
3. 点レジスタを測定し、ある群要素Rに収縮させる
4. 計数レジスタに逆QFTを適用する
5. j, kを測定し、関係式 j + kd = r (mod n) からdを抽出する

秘密鍵dは、群位数nを法として同じ線形関係を満たす複数の(j, k)サンプルを収集することで回復されます。ソルバーは制御付き点加算のための6つのオラクル戦略をサポートしており、曲線のサイズに基づいて自動的に選択されるか、--oracleで手動で選択されます。

オラクル戦略

戦略1: 高密度ユニタリ (n_bits <= 6 の場合のデフォルト)

群位数が最大約6ビットの曲線に使用されます。projecteleven.pyで実装されています。

各制御付き点加算"add S"は、qc.unitary()で適用される2^(n+1) x 2^(n+1)の置換行列として表されます。行列は群の完全な作用をエンコードします:左上ブロックは恒等(制御=0)、右下ブロックは写像P -> P+S (制御=1)に従って基底状態を置換します。

• エンコーディング: 群インデックス (0..n-1)
• メモリ: O(2^{2n}) 行列あたり
• 量子ビット数: 2t + n (2つの計数レジスタ + 点レジスタ)
• 制限事項: Qiskitのユニタリ分解はO(4^n)であり、約6ビットを超えると実行不可能になります

戦略2: 効率的な置換分解 (n_bits > 6 の場合のデフォルト)

より大きな曲線に使用されます。quantum_arithmetic.pyで実装されています。

高密度行列を構築する代わりに、各"add S"の置換はトランスポジションに巡回分解されます。各トランスポジション(2つの基底状態|a> <-> |b>のスワップ)は以下で実装されます:

1. CNOT削減 -- ピボットビットから他のすべての異なるビットへのCNOTにより、マルチビットの差をシングルビットの差に削減
2. マルチ制御X -- 他のすべてのビットがターゲットパターンと一致することを条件とした、ピボットビット上のMCXゲート
3. CNOTの元に戻す -- ステップ1を逆にして非ピボットビットを復元

MCXは(n-2)個の専用アンシラ量子ビットを持つVチェーン分解を使用し、アンシラなしのO(n^2)に対して、MCXあたりO(n)個のToffoliゲートを実現します。各制御付き加算は孤立したサブ回路として構築され、単一の不透明ゲートとして追加され、Qiskitでの二次的なDAGの増大を回避します。

• エンコーディング: 群インデックス (0..n-1)
• メモリ: O(N) 加算あたり (N = 群位数)
• 量子ビット数: 2t + n + (n-2) アンシラ
• ゲート数(加算あたり): O(N * n)

戦略3: 座標ベース量子オラクル (--oracle coordinate)

最大約6ビットの曲線で利用可能です。quantum_oracle.pyで実装されています。

点を群インデックスとしてエンコードする代わりに、量子レジスタは実際の**(x, y)体要素座標**をバイナリで保持し、さらに恒等フラグを加えます。点レジスタのレイアウトは:

• x_reg: f_bits 量子ビット (f_bits = ceil(log2(p)))
• y_reg: f_bits 量子ビット
• id_flag: 1 量子ビット (1 = 無限遠点)

各制御付き"add S"は、すべての有効な座標エンコーディングに対するEC加算式から計算され、座標レジスタ上の置換を生成します。この置換は、戦略2と同じCNOT削減 + MCXインフラストラクチャを使用してトランスポジションに巡回分解されます。

• エンコーディング: (x, y, id_flag) 座標
• 量子ビット数: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) アンシラ
• ゲート数(加算あたり): O(N * f_bits)

戦略4: 算術オラクル (--oracle arithmetic)

多項式スケーリングの点加算のためのフレームワーク。quantum_oracle.pyおよびquantum_arithmetic.pyで実装されています。

戦略3と同じ座標エンコーディングを使用し、QFTベースのモジュラ算術プリミティブを完全な算術点加算に向けた構成要素として使用します。コードベースには以下のテスト済み実装が含まれています:

• Beauregardモジュラ加算器 -- QFTベース (target + constant) mod p、適切なアンシラアンコンピュート付き
• 量子-量子モジュラ乗算 -- |a>|b>|0> -> |a>|b>|a*b mod p>、シフトアンド加算と明示的なモジュラ倍化を使用、O(n^3)ゲート
• モジュラ逆元置換 -- |x> -> |x^{-1} mod p>、ルックアップテーブルトランスポジションによる
• 制御付き量子-量子モジュラ加算 -- 制御付き|a> -> |a + b mod p>、Beauregard削減を使用

算術プリミティブは点加算あたりO(n^3)スケーリングを達成し、置換アプローチのO(N*n)に対して優れています。しかし、QFTベースの演算は約150倍の定数因子が大きく、そのため算術アプローチは約20ビット以上の群位数を持つ曲線でのみ効率的です。現在のチャレンジサイズ(最大12ビット)では、置換ベースの加算器が高速であり、デフォルトで使用されます。

戦略5: Google半古典位相推定 (--oracle google)

google_semiclassical.pyで実装されています。Griffiths & Niu (1996) の量子ビットリサイクル位相推定手法に触発され、Babbush et al. (2026) でsecp256k1 ECDLPリソース見積もりに大規模適用されました。Babbush et al. の論文は2026年3月30日に公開されました。

2つのマルチ量子ビット計数レジスタ(j, k)とバルク逆QFTを、2つの単一リサイクル量子ビットと古典的条件付き位相補正に置き換えます。各計数レジスタビットは順次処理されます:|+>に準備し、制御付き点加算を適用し、以前に測定されたすべてのビットに基づいて位相を補正し、測定します。Qiskitのreset + if_test動的回路プリミティブにより、IBM Quantumハードウェア上でこれが可能になります。

制御付き点加算のためのオラクルは既存のインフラストラクチャ(<=6ビットでは高密度ユニタリ、>6ビットでは効率的置換)に委譲されるため、量子ビット節約は完全に計数レジスタを排除することから来ています。

• エンコーディング: 基盤となる戦略と同じ (群インデックス)
• 量子ビット数: 2 + n_bits + アンシラ (2t + n_bits + アンシラ に対して)
• トレードオフ: 動的回路(中間回路測定、リセット、古典的条件付きゲート)が必要。IBM Heron r2では7ビットまで動作可能; 8ビット以上では、古典的フィードバック同期オーバーヘッドがQPU時間予算を超える

戦略6: リップルキャリーモジュラ加算 (--oracle ripple)

ripple_carry_shor.pyで実装されています。制御付き点加算にCDKMリップルキャリー加算器(Cuccaro et al. 2004)を使用し、高密度ユニタリ行列と巡回分解トランスポジション回路の両方を置き換えます。

群インデックスエンコーディングでは、点P = kGは巡回群内のインデックスkで表されます。S = sGの加算は、**既知の定数sのモジュラ加算(mod n)**になります。重要な洞察: 各制御付き点加算は、QiskitのCDKMRippleCarryAdderとIntegerComparatorを使用して実装された、既知の定数の単一制御付きモジュラ加算に還元されます。

オラクルは2m個の制御付きモジュラ加算(計数レジスタあたりm個)で構成され、各制御付きモジュラ加算は以下を実行します:

1. 定数をロード 制御量子ビットからアンシラレジスタへのCX経由
2. CDKM半加算器 アンシラをアキュムレータに加算(最近傍ゲートのみ)
3. 整数比較器 オーバーフローを検出(acc >= n)
4. 条件付きnの減算 フラグ制御による2^m1 - nの加算
5. フラグのアンコンピュート キャリーベースのプロービングによる

秘密鍵dの知識は回路構築に使用されません。Gパワーの群インデックスは2^i mod n(公開)として計算されます。Qパワーの群インデックスは、Gによって生成される巡回群の公開列挙から導出されます — 点Qはこの列挙の中で検索されます。

• エンコーディング: 群インデックス (0..n-1)
• 量子ビット数: 4m + 5 (m = ceil(log2(n)))
• ゲート数(加算あたり): O(m) CDKM演算、各O(m) CXゲート
• 総CXスケーリング: O(m^3)
• ハードウェアマッピング: CDKMは最近傍ゲートのみを使用し、IBM heavy-hexトポロジ上で約1倍のルーティングオーバーヘッドを与える(QFTベース加算器の26-33倍に対して)

比較

QFT算術プリミティブ

コードベースには、完全な算術座標エンコーディングを256ビットで実現するための基盤として、QFTベースのモジュラ算術構成要素(Beauregard/Draper加算器、量子-量子モジュラ乗算、モジュラ逆元/否定)が含まれています。これらのプリミティブは、p=13までの素数に対するStatevectorシミュレーションで正しく動作することが検証されています。

結果

IBM Quantumハードウェア上で、最大17ビットのチャレンジ曲線に対する秘密鍵の回復に成功しました:

すべての実行はIBM Quantumオープンインスタンスプランで行われ、月10分の無料量子計算が付与されています。完全な実行ログはexecutions/フォルダにあります。

リップルキャリー戦略(戦略6)により、大きな飛躍が可能になりました: 10ビット(40量子ビット、200万ゲート)から**17ビット(69量子ビット、112Kゲート)**へ — 7ビットの鍵サイズ増加で、2量子ビットゲート数を18分の1に削減。CDKM加算器の最近傍ゲート構造はIBMのheavy-hexトポロジに効率的にマッピングされ、ルーティングオーバーヘッドを約1倍に保ちます。

半古典位相推定: IBMハードウェア上の動的回路

半古典戦略(--oracle google)は、IBM Heron r2プロセッサ上で動的回路(中間回路reset、if_testによる古典的条件付きpゲート)を使用して、4ビット、6ビット、7ビットで鍵の回復に成功しました。7ビットでは、回路はわずか14量子ビット(標準の置換アプローチの26に対して)を使用し、トランスパイル後も同等の2量子ビットゲート数を生成します。

8ビット以上では、半古典アプローチは現在のIBMハードウェアでは実用的でなくなります。if_elseとresetはHeron r2でサポートされていますが(バックエンドターゲット検査で確認)、各古典的フィードバックポイントは完全なQPU同期を必要とします — 156個すべての物理量子ビットがアイドル状態になり、古典的コントローラーが約16個のアクティブ量子ビットに対する条件付きを処理する間待機します。約295KのCZゲートが16以上のフィードバックポイントに分散しているため、1ショットあたりの実行オーバーヘッドによりジョブがQPU時間予算を超過します。同じゲート数を動的回路なしで単一の連続バッチとして実行する標準の置換アプローチは、この規模で正常に完了します。

近似QFT打ち切り(max_correctionsパラメータ)により、if_elseブロックの数をO(n^2)からO(n)に削減します。これは、測定ステップごとに最も近いk個の位相補正のみを保持することによるものです(kを超える角度はpi/2^{k+1}未満に寄与し、ハードウェアノイズフロア以下)。max_corrections=1の場合、8ビット回路には16個のif_elseブロックがあります — このゲート数ではIBMハードウェア上でタイムアウトを引き起こすには十分です。

ノイズと忠実度の解析

推定回路忠実度

典型的なIBM Quantum 2量子ビット(CX)ゲート忠実度を約99.5%と仮定すると、推定回路忠実度はゲート数とともに指数関数的に低下します:

回路忠実度はF ≈ (0.995)^{CX_count}として計算されます。4ビットを超えるすべてにおいて、推定忠実度は天文学的に小さい — 出力分布は圧倒的にノイズです。

それでも機能する理由

8ビット以上では、各ショットはほぼユニークなビットストリングを生成します(8ビットで8,192ショット中8,128のユニークな結果; 16ビットと17ビットでは20,000すべてがユニーク)。出力はビットストリングレベルで一様ランダムサンプリングと区別がつきません。しかし、アルゴリズムは正しい秘密鍵を回復します。

重要な洞察は、Shorの後処理は生のビットストリング解析とは異なる方法でノイズに対してロバストであるということです。各ショットは(j, k, r)測定トリプルを生成します。抽出はd_cand = (r - j) · k^{-1} mod nを計算し、d_cand · G == Qで検証します。真のdのみがEC検証に合格するため、数千のノイズショットの中から単一の正しい候補があれば十分です。

純粋にランダムな(j, k, r)トリプルは、確率約1/nで正しいd_candを生成します。Sショットの場合、ノイズのみからの期待される検証済みヒット数は約S/nです。17ビット(n=65,173、S=20,000)では、これは約0.3の期待ノイズヒットを与えます — この規模での成功した回復は、古典的ノイズフロアを超えた量子信号の証拠を提供します。

ショット数 >> n の小さな曲線(例: 10ビット、n=547、1,024ショット)では、ノイズフロアは約1,024/547 ≈ 1.9票/候補です。少数の信号を含むショットでも、正しいdをノイズフロアより上に押し上げます。これにより、回路忠実度が計算を不可能にするように見えるにもかかわらず、アルゴリズムが成功する理由が説明されます。

量子信号 vs 古典ノイズ

おもちゃ規模では、抽出の検証ステップ(d_cand * G == Q)は、真のdのみを受け入れるフィルターとして機能します。これは、純粋にランダムな(j, k, r)トリプルでも、約 ショット数 / n の割合で有効な候補を生成することを意味します。ショット数 >> n の場合、ランダムノイズだけでも高い確率でdを回復できます。

量子回路がこの古典的ノイズフロアを超えて信号に寄与しているかどうかをテストするために、6ビットチャレンジ(n=31)をわずか8ショット(群位数よりはるかに少ない)で10回ibm_kingstonで実行しました:

結果: 10回中4回成功(40%) vs 古典的ノイズベースライン約20%(モンテカルロシミュレーションで計算: 8個のランダムビットストリングを(r-j)*k_inv mod 31でフィルタリングし検証)。片側二項検定: P(X >= 4 | n=10, p=0.20) = 0.121、ノイズフロアに対する2倍の改善を示しています。統計的に有意(p < 0.05)であるためには5回以上の成功が必要ですが、観測された割合は、量子信号が実行あたりランダムチャンスが提供するものよりも約1-2個の追加の有効な(j, k)ペアに寄与していることと一致しています。

この結果は、古典的ノイズフロアと理論的な量子優位領域の間に位置します。n >> ショット数となるより大きな曲線サイズでは、ノイズベースラインは1%未満に低下し、成功した鍵回復は強い量子計算の証拠となります。

クイックスタート```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

### 実行方法

[IBM Quantum](https://quantum.ibm.com/) アカウントが必要です。初回実行時にAPIトークンを入力すると、ローカルに保存されます：```bash
# Solve the 4-bit challenge curve:
python projecteleven.py --challenge 4 --token YOUR_IBM_TOKEN --backend ibm_marrakesh

# Subsequent runs (token already saved):
python projecteleven.py --challenge 4 --backend ibm_marrakesh

# Use the coordinate-based quantum oracle:
python projecteleven.py --challenge 4 --oracle coordinate --backend ibm_marrakesh

# Use the arithmetic oracle (coordinate encoding + QFT primitives):
python projecteleven.py --challenge 4 --oracle arithmetic --backend ibm_marrakesh

# Use ripple-carry modular addition (CDKM — best for 8-bit+):
python projecteleven.py --challenge 16 --oracle ripple --backend ibm_fez --shots 20000

# Use Google semiclassical phase estimation (qubit-recycled):
python projecteleven.py --challenge 4 --oracle google --backend ibm_marrakesh

# Use a specific IBM Quantum instance:
python projecteleven.py --challenge 4 --instance ibm-q/open/main --backend ibm_marrakesh

# Verify curve parameters without quantum execution:
python projecteleven.py --curve curve_4 --verify-only

CLIオプション

プロジェクト構成```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime

## 参考文献

- P. Shor, ["量子計算のためのアルゴリズム：離散対数と素因数分解"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["2n+3量子ビットを用いたShorのアルゴリズムの回路"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, ["新しい量子リプルキャリー加算回路"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, ["楕円曲線離散対数計算のための量子リソース見積もり"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu, ["量子計算のための半古典的フーリエ変換"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush et al., ["量子脆弱性に対する楕円曲線暗号通貨の保護：リソース見積もりと緩和策"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## ライセンス

このプロジェクトは、[MIT LICENSE](https://github.com/giancarlolelli/quantum/blob/HEAD/LICENSE) に基づいてリリースされた Q-Day Prize Challenge への提出物です。