論文の概要: Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
- arxiv url: http://arxiv.org/abs/2604.02311v1
- Date: Thu, 02 Apr 2026 17:52:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-03 14:21:10.980639
- Title: Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
- Title（参考訳）: 資源推定を伴う楕円曲線離散対数に対する空間効率のよい量子アルゴリズム
- Abstract要約: 楕円曲線離散対数問題(ECDLP)は広く展開されている楕円曲線暗号システムの量子セキュリティを評価する上で重要である。
ECDLPのための空間効率のよいモジュラインバージョンアルゴリズムを提案する。
特に256ビットの素体曲線の場合、これまでのHner et alの低幅実装の2124と比較して、論理キュービット数は1333に減少する。
- 参考スコア（独自算出の注目度）: 30.009533492838028
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses $3n + 4\lfloor \log_2 n \rfloor + O(1)$ logical qubits and $204n^2\log_2 n + O(n^2)$ Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with $5n + 4\lfloor \log_2 n \rfloor + O(1)$ qubits and $O(n^3)$ Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.
- Abstract（参考訳）: 楕円曲線離散対数問題(ECDLP)の解法は、広く展開された楕円曲線暗号システムの量子セキュリティを評価する上で重要である。
したがって、このアルゴリズムを実行するのに必要な論理量子ビットの数を最小化することが鍵となる。
Shorのアルゴリズムの実装では、空間の複雑さは、点加算時のモジュラー反転演算によって決定される。
拡張ユークリッドアルゴリズム(EEA)から、ProosとZalkaのレジスタ共有法を改良し、空間効率の良い可逆的モジュラー逆アルゴリズムを提案する。
我々は、長さレジスタと位置制御演算を用いて、計算全体を通して中間変数をコンパクトな形式で格納する。
次に、段階的に更新ルールを最適化し、制御された演算部品に対して具体的な回路構成を与える。
これにより、3n + 4\lfloor \log_2 n \rfloor + O(1)$論理量子ビットと204n^2\log_2 n + O(n^2)$トフォリゲートを使用するモジュラー反転回路が生成される。
このモジュラー反転成分を制御されたアフィン点付加回路に挿入することにより, 5n + 4\lfloor \log_2 n \rfloor + O(1)$ qubits および $O(n^3)$ Toffoli gates を用いた ECDLP の空間効率アルゴリズムを得る。
特に256ビットの素体曲線では、Häner et al の以前の低幅実装の 2124 と比較して、この推定は論理キュービット数 1333 に減少する。
関連論文リスト
- Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition [31.43193848243857]
楕円曲線離散対数問題(ECDLP)は暗号の基本問題である。
本稿では,3n+6lfloor log nrfloor+O(1)$ logical qubits と 919n3/log n+O(n2)$ Toffoli gates で実装した。
我々の改良の鍵は、アフィン座標点加算における支配的な空間ボトルネックに対処する、新しい空間効率のリバーシブルなモジュラーインバージョン回路である。
論文 参考訳（メタデータ） (2026-07-15T13:25:00Z) - Improved quantum circuits for division [42.76841620787673]
様々な整数分割アルゴリズムのための新しいフォールトトレラント量子回路を開発した。
回路は最大76.08%、68.35%のT数とCNOT数を実現している。
論文 参考訳（メタデータ） (2026-03-18T13:41:43Z) - Asymptotically Optimal Quantum Circuits for Comparators and Incrementers [2.488003578430483]
本稿では,Clifford+Toffoliゲート集合上での最適ゲート数$(n)$と深さ$(log n)$を,比較および増分演算のための量子回路を提案する。
これらの結果を古典量子コンパレータに拡張し、最適化された古典量子加算器を最適量子数で生成する。
論文 参考訳（メタデータ） (2026-03-13T11:41:14Z) - Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。
本手法の様々な応用は, 微分問題を解く文脈で論じる。
論文 参考訳（メタデータ） (2026-02-11T07:24:33Z) - Quantum and classical algorithms for SOCP based on the multiplicative weights update method [44.99833362998488]
第二次コーンプログラム(SOCP)を解くための古典的および量子的アルゴリズムを与える。
我々のアプローチは、半定値プログラム(SDP)に先立って適用されたMWフレームワークに従う。
我々は、SOCPの付加構造を利用して、SOCP固有のアルゴリズムでより優れたランタイムを提供することを示す。
論文 参考訳（メタデータ） (2025-07-18T17:55:58Z) - Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
ウィンドウ演算は、空間時間トレードオフを伴う量子回路のコストを削減する手法である。
この作業では、ウィンドウ化されたモジュラー指数に4つの最適化を導入する。
これにより、暗号化アプリケーションに関連するモジュール型指数回路において、Toffoli数とToffoli深度が3%向上する。
論文 参考訳（メタデータ） (2025-02-24T16:59:16Z) - 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) - Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。
次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。
Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文 参考訳（メタデータ） (2020-06-21T06:57:59Z) - Improved quantum circuits for elliptic curve discrete logarithms [6.058525641792685]
楕円曲線スカラー乗算のための改良された量子回路を提案する。
可逆整数やモジュラ演算などの低レベル成分を最適化する。
Q#量子プログラミング言語における点加算の完全な実装を提供する。
論文 参考訳（メタデータ） (2020-01-27T04:08:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。