giancarlolelli/quantumこのリポジトリには、https://www.projecteleven.com/ によるQDay賞チャレンジのコードと提出詳細が含まれています。
楕円曲線離散対数問題(ECDLP)のための量子ソルバー。Project Elevenが主催するQ-Day Prize Challengeのために構築されました。目標: 実際の量子ハードウェア上でShorのアルゴリズムを用いてECC秘密鍵を回復すること。
すべてのチャレンジ曲線は、F_p上の y^2 = x^3 + 7 (a = 0, b = 7) を使用しており、secp256k1ファミリーと一致しています。ソルバーはECDLPのためのShorのアルゴリズムの2レジスタバリアントを実装しています:
秘密鍵dは、群位数nを法として同じ線形関係を満たす複数の(j, k)サンプルを収集することで回復されます。ソルバーは制御付き点加算のための6つのオラクル戦略をサポートしており、曲線のサイズに基づいて自動的に選択されるか、--oracleで手動で選択されます。
群位数が最大約6ビットの曲線に使用されます。projecteleven.pyで実装されています。
各制御付き点加算"add S"は、qc.unitary()で適用される2^(n+1) x 2^(n+1)の置換行列として表されます。行列は群の完全な作用をエンコードします:左上ブロックは恒等(制御=0)、右下ブロックは写像P -> P+S (制御=1)に従って基底状態を置換します。
より大きな曲線に使用されます。quantum_arithmetic.pyで実装されています。
高密度行列を構築する代わりに、各"add S"の置換はトランスポジションに巡回分解されます。各トランスポジション(2つの基底状態|a> <-> |b>のスワップ)は以下で実装されます:
MCXは(n-2)個の専用アンシラ量子ビットを持つVチェーン分解を使用し、アンシラなしのO(n^2)に対して、MCXあたりO(n)個のToffoliゲートを実現します。各制御付き加算は孤立したサブ回路として構築され、単一の不透明ゲートとして追加され、Qiskitでの二次的なDAGの増大を回避します。
--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インフラストラクチャを使用してトランスポジションに巡回分解されます。
--oracle arithmetic)多項式スケーリングの点加算のためのフレームワーク。quantum_oracle.pyおよびquantum_arithmetic.pyで実装されています。
戦略3と同じ座標エンコーディングを使用し、QFTベースのモジュラ算術プリミティブを完全な算術点加算に向けた構成要素として使用します。コードベースには以下のテスト済み実装が含まれています:
算術プリミティブは点加算あたりO(n^3)スケーリングを達成し、置換アプローチのO(N*n)に対して優れています。しかし、QFTベースの演算は約150倍の定数因子が大きく、そのため算術アプローチは約20ビット以上の群位数を持つ曲線でのみ効率的です。現在のチャレンジサイズ(最大12ビット)では、置換ベースの加算器が高速であり、デフォルトで使用されます。
--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ビットでは効率的置換)に委譲されるため、量子ビット節約は完全に計数レジスタを排除することから来ています。
| 曲線サイズ | 標準量子ビット数 | 半古典量子ビット数 | 削減率 | ハードウェア検証 |
|---|---|---|---|---|
| 4ビット (n=7) | 11 | 5 | 55% | はい |
| 6ビット (n=31) | 17 | 7 | 59% | はい |
| 7ビット (n=79) | 26 + anc | 14 | 46% | はい |
| 8ビット (n=139) | 25 + anc | 10 + anc | 60% | いいえ (QPU同期オーバーヘッド) |
| 10ビット (n=547) | 31 + anc | 12 + anc | 61% | いいえ (QPU同期オーバーヘッド) |
--oracle ripple)ripple_carry_shor.pyで実装されています。制御付き点加算にCDKMリップルキャリー加算器(Cuccaro et al. 2004)を使用し、高密度ユニタリ行列と巡回分解トランスポジション回路の両方を置き換えます。
群インデックスエンコーディングでは、点P = kGは巡回群内のインデックスkで表されます。S = sGの加算は、**既知の定数sのモジュラ加算(mod n)**になります。重要な洞察: 各制御付き点加算は、QiskitのCDKMRippleCarryAdderとIntegerComparatorを使用して実装された、既知の定数の単一制御付きモジュラ加算に還元されます。
オラクルは2m個の制御付きモジュラ加算(計数レジスタあたりm個)で構成され、各制御付きモジュラ加算は以下を実行します:
秘密鍵dの知識は回路構築に使用されません。Gパワーの群インデックスは2^i mod n(公開)として計算されます。Qパワーの群インデックスは、Gによって生成される巡回群の公開列挙から導出されます — 点Qはこの列挙の中で検索されます。
| 曲線サイズ | 量子ビット数 | 2量子ビットゲート数(トランスパイル後) | ハードウェア検証 |
|---|---|---|---|
| 4ビット (n=7) | 17 | 1,824 | はい (シミュレーション) |
| 8ビット (n=139) | 37 | 11,224 | — |
| 10ビット (n=547) | 45 | 17,204 | — |
| 12ビット (n=2143) | 53 | 24,304 | — |
| 16ビット (n=32497) | 65 | 98,049 | はい |
| 17ビット (n=65173) | 69 | 111,816 | はい |
| 指標 | 高密度ユニタリ | 効率的置換 | 座標オラクル | 算術オラクル | 半古典位相推定 | リップルキャリー |
|---|---|---|---|---|---|---|
| 点エンコーディング | 群インデックス | 群インデックス | (x, y, id_flag) | (x, y, id_flag) | 群インデックス | 群インデックス |
| 加算あたりのスケーリング | O(4^n) 分解 | O(N * n) | O(N * f_bits) | O(n^3) 漸近的 | O(N * n) | O(m^2) |
| 量子ビット数 (4ビット) | 11 | 13 | 24 | 24 | 5 | 17 |
| 量子ビット数 (6ビット) | 17 | 21 | 36 | 36 | 9 | 25 |
| 2量子ビットゲート数 (4ビット) | 774 | ~1,200 | 6,449 | 6,449 | ~1,200 | 1,824 |
| 2量子ビットゲート数 (6ビット) | 23,471 | ~38,000 | 95,254 | 95,254 | ~38,000 | 4,582 |
| 実用範囲 | 6ビット以下 | 約16ビット以下 | 6ビット以下 | 20ビット以上 (将来) | 約16ビット以下 | 約20ビット以下 |
コードベースには、完全な算術座標エンコーディングを256ビットで実現するための基盤として、QFTベースのモジュラ算術構成要素(Beauregard/Draper加算器、量子-量子モジュラ乗算、モジュラ逆元/否定)が含まれています。これらのプリミティブは、p=13までの素数に対するStatevectorシミュレーションで正しく動作することが検証されています。
IBM Quantumハードウェア上で、最大17ビットのチャレンジ曲線に対する秘密鍵の回復に成功しました: