論文の概要: Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition

• arxiv url: http://arxiv.org/abs/2607.13816v1
• Date: Wed, 15 Jul 2026 13:25:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-16 16:39:12.783768
• Title: Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition
• Title（参考訳）: 空間効率の良い点付加による楕円曲線離散対数に対する量子アルゴリズム
• Abstract要約: 楕円曲線離散対数問題(ECDLP)は暗号の基本問題である。 本稿では,3n+6lfloor log nrfloor+O(1)$ logical qubits と 919n3/log n+O(n2)$ Toffoli gates で実装した。 我々の改良の鍵は、アフィン座標点加算における支配的な空間ボトルネックに対処する、新しい空間効率のリバーシブルなモジュラーインバージョン回路である。
• 参考スコア（独自算出の注目度）: 31.43193848243857
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only $3n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $919n^3/\log_2 n+O(n^2)$ Toffoli gates, where $n$ is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively. The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only $2n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $195n^2+O(n\log_2 n)$ Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.
• Abstract（参考訳）: 楕円曲線離散対数問題(ECDLP)は暗号の基本的な問題であり、ECCDLPを解くための量子アルゴリズムのリソース要求を減らすことが重要な目標である。 本研究では,素体上のCDLPを解くための空間効率のよい量子アルゴリズムを提案し,3n+6\lfloor \log_2 n \rfloor+O(1)$論理量子ビットと919n^3/\log_2 n+O(n^2)$トフォリゲートを実装した。 256ビットの素体曲線の場合、我々の構成では835個の論理量子ビットしか必要とせず、Chevignard et al [EUROCRYPT 2026] と Babbush et al [ArXiv Preprint 2026] による 1098 と 1175 の論理量子ビットをそれぞれ減少させる。 我々の改良の鍵は、アフィン座標点加算における支配的な空間ボトルネックに対処する、新しい空間効率のリバーシブルなモジュラーインバージョン回路である。 拡張ユークリッドアルゴリズム(EEA)から始まり、中間変数をコンパクトに保存・更新するために長さレジスタと位置制御演算を導入することにより、ProosとZalkaのレジスタ共有技術を洗練する。 さらに、可逆的な更新手順を最適化し、対応する制御された演算回路を構築することにより、2n+6\lfloor \log_2n \rfloor+O(1)$論理量子ビットと195n^2+O(n\log_2 n)$トフォリゲートで実装されたモジュラー反転回路を実現する。 このモジュラインバージョン回路は、中間回路の測定と古典的なフィードフォワード演算とともに、空間効率の高い制御されたアフィン点付加回路と、ショアのアルゴリズムの完全な実装を提供する。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation [30.009533492838028]
  楕円曲線離散対数問題(ECDLP)は広く展開されている楕円曲線暗号システムの量子セキュリティを評価する上で重要である。 ECDLPのための空間効率のよいモジュラインバージョンアルゴリズムを提案する。 特に256ビットの素体曲線の場合、これまでのHner et alの低幅実装の2124と比較して、論理キュービット数は1333に減少する。
  論文  参考訳（メタデータ） (2026-04-02T17:52:00Z)
• End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions [66.17960480460185]
  決定過程(MDP)における線形関数近似を用いた強化学習の研究 本稿では, 線形ベルマン完全オラクルに対して, 決定論的遷移, 初期状態, 報奨を伴う計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-24T17:32:29Z)
• Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice [7.999752490202695]
  量子コンピュータは古典的な暗号システムを壊す可能性がある。 toffoli depth $log n + loglog n + O(1)$ with only $O(n)$ ancillas。 2次元格子上のショア楕円曲線アルゴリズムの網羅的資源解析を行う。
  論文  参考訳（メタデータ） (2025-10-27T11:02:10Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Space-Efficient and Noise-Robust Quantum Factoring [10.974556218898435]
  Regevの最近の量子ファクタリングアルゴリズムに2つの改善がある。 レゲフの回路は$O(n3/2)$ qubitsと$O(n3/2 log n)$ gatesを必要とする。 Regev氏の古典的な後処理手順の分析は、すべての$approx sqrtn$の実行を成功させる必要がある。
  論文  参考訳（メタデータ） (2023-10-02T04:31:21Z)
• New Space-Efficient Quantum Algorithm for Binary Elliptic Curves using the Optimized Division Algorithm [1.2183405753834562]
  より少ない量子ビット数を用いる二進体上の新しい量子除算アルゴリズムを提案する。 2n$のフィールドの要素に対して、$lceil n/2 rceil - 1$ qubits を 8n2+4n-12+ 16n-8)lfloorlog(n)rfloor$ more Toffoli gates の代わりに保存できる。
  論文  参考訳（メタデータ） (2023-03-12T05:00:46Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)
• Improved quantum circuits for elliptic curve discrete logarithms [6.058525641792685]
  楕円曲線スカラー乗算のための改良された量子回路を提案する。 可逆整数やモジュラ演算などの低レベル成分を最適化する。 Q#量子プログラミング言語における点加算の完全な実装を提供する。
  論文  参考訳（メタデータ） (2020-01-27T04:08:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。