論文の概要: A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography
- arxiv url: http://arxiv.org/abs/2405.14381v1
- Date: Thu, 23 May 2024 09:59:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-24 15:54:01.897525
- Title: A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography
- Title（参考訳）: 非対称暗号解読のための最先端量子アルゴリズムの高レベル比較
- Authors: Martin Ekerå, Joel Gärtner,
- Abstract要約: 我々はRegevの量子アルゴリズムを、一方のEkeraa-G"artnerの拡張と、他方の離散対数分解と計算のための既存の最先端量子アルゴリズムと比較する。
我々の結論は、空間節約最適化のないRegevのアルゴリズムは、非計算量子メモリが安価であれば、ラン当たりの優位性を得るが、全体的な優位性は得られないということである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide a high-level cost comparison between Regev's quantum algorithm with Eker{\aa}-G\"artner's extensions on the one hand, and existing state-of-the-art quantum algorithms for factoring and computing discrete logarithms on the other. This when targeting cryptographically relevant problem instances, and when accounting for the space-saving optimizations of Ragavan and Vaikuntanathan that apply to Regev's algorithm, and optimizations such as windowing that apply to the existing algorithms. Our conclusion is that Regev's algorithm without the space-saving optimizations may achieve a per-run advantage, but not an overall advantage, if non-computational quantum memory is cheap. Regev's algorithm with the space-saving optimizations does not achieve an advantage, since it uses more computational memory, whilst also performing more work, per run and overall, compared to the existing state-of-the-art algorithms. As such, further optimizations are required for it to achieve an advantage for cryptographically relevant problem instances.
- Abstract（参考訳）: 本稿では,Regevの量子アルゴリズムとEker{\aa}-G\"artner's拡張を高コストで比較する。
これは、暗号的に関連する問題インスタンスをターゲットとし、また、Regevのアルゴリズムに適用されるRagavanとVaikuntanathanの空間節約最適化と、既存のアルゴリズムに適用されるウィンドウ化のような最適化を考慮に入れたときである。
我々の結論は、空間節約最適化のないRegevのアルゴリズムは、非計算量子メモリが安価であれば、ラン当たりの優位性を得るが、全体的な優位性は得られないということである。
スペースセーブ最適化によるRegevのアルゴリズムは、計算メモリを多く使用する一方で、既存の最先端アルゴリズムと比較して、実行時および全体的な処理量も大きいため、優位性は得られない。
そのため、暗号関連問題インスタンスの利点を達成するためには、さらなる最適化が必要である。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - From Optimization to Control: Quasi Policy Iteration [3.4376560669160394]
準政治反復(QPI)と呼ばれる新しい制御アルゴリズムを提案する。
QPIは、政策反復アルゴリズムにおける「ヘシアン」行列の新たな近似に基づいて、MDPに特有の2つの線形構造制約を利用する。
これは、割引係数に対する感度が極めて低い政策反復と同様の実証的な収束挙動を示す。
論文 参考訳（メタデータ） (2023-11-18T21:00:14Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
雑音は量子回路のバイアスによる目的関数の評価を行う。
我々は、欠落した保証を導き、収束率が影響を受けないことを見出す。
論文 参考訳（メタデータ） (2022-09-21T19:18:41Z) - Regret Bounds for Expected Improvement Algorithms in Gaussian Process
Bandit Optimization [63.8557841188626]
期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。
本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。
我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2022-03-15T13:17:53Z) - Stochastic optimization algorithms for quantum applications [0.0]
本稿では、一階法、二階法、量子自然勾配最適化法の使用法を概観し、複素数体で定義される新しいアルゴリズムを提案する。
全ての手法の性能は、変分量子固有解法、量子状態の量子制御、および量子状態推定に応用して評価される。
論文 参考訳（メタデータ） (2022-03-11T16:17:05Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Optimal and Practical Algorithms for Smooth and Strongly Convex
Decentralized Optimization [21.555331273873175]
ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。
本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
論文 参考訳（メタデータ） (2020-06-21T11:23:20Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳（メタデータ） (2020-02-13T05:42:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。