論文の概要: A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem

• arxiv url: http://arxiv.org/abs/2209.02814v4
• Date: Tue, 25 Apr 2023 14:03:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-27 03:54:43.672482
• Title: A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem
• Title（参考訳）: 半間接離散対数問題に対する部分指数量子アルゴリズム
• Authors: Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, and Siamak F. Shahandashti
• Abstract要約: グループベースの暗号は、量子後暗号における比較的未発見の家系である。 いわゆる半間接離散対数問題(Semidirect Discrete Logarithm Problem, SDLP)は、その最も中心的な問題の一つである。 SDLPのセキュリティ分析を初めて行った。
• 参考スコア（独自算出の注目度）: 2.123711812861527
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Group-based cryptography is a relatively unexplored family in post-quantum cryptography, and the so-called Semidirect Discrete Logarithm Problem (SDLP) is one of its most central problems. However, the complexity of SDLP and its relationship to more well-known hardness problems, particularly with respect to its security against quantum adversaries, has not been well understood and was a significant open problem for researchers in this area. In this paper we give the first dedicated security analysis of SDLP. In particular, we provide a connection between SDLP and group actions, a context in which quantum subexponential algorithms are known to apply. We are therefore able to construct a subexponential quantum algorithm for solving SDLP, thereby classifying the complexity of SDLP and its relation to known computational problems.
• Abstract（参考訳）: グループベースの暗号は、量子後暗号における比較的未発見の家系であり、いわゆるセミダイレクト離散対数問題(Semidirect Discrete Logarithm Problem, SDLP)は最も中心的な問題の一つである。 しかし、SDLPの複雑さと、特に量子敵に対するセキュリティに関して、よりよく知られた硬さ問題との関係はよく理解されておらず、この分野の研究者にとって重要なオープンな問題であった。 本稿では,sdlpのセキュリティ解析を初めて実施する。 特に、SDLPとグループアクションの間には、量子部分指数アルゴリズムを適用することが知られているコンテキストがある。 したがって、SDLPを解くための部分指数量子アルゴリズムを構築することができ、SDLPの複雑さと既知の計算問題との関係を分類することができる。

関連論文リスト

• Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm [0.5919433278490629]
  独立支配問題(IDP)は、様々な現実のシナリオにおいて実践的な意味を持つ。 IDPの既存の古典的アルゴリズムは計算の複雑さに悩まされている。 本稿では、IDPに対処するための量子近似最適化(QAOA)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-10-22T17:49:00Z)
• Quantum Algorithm for Maximum Biclique Problem [11.96554895748371]
  頂点の最大数で双斜線を同定することは、多くの応用分野に相当な意味を持つ。 本稿では,時間的複雑性O*(2(n/2))を持つ基底破れアルゴリズムqMBSを提案する。 最大二進問題と最大二進問題に適した2つの変種を詳述する。
  論文  参考訳（メタデータ） (2023-09-08T04:43:05Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。 アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
  論文  参考訳（メタデータ） (2022-11-22T18:54:48Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
  論文  参考訳（メタデータ） (2021-09-23T07:46:20Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。 量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。 我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
  論文  参考訳（メタデータ） (2021-06-11T18:00:09Z)
• Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
  本稿では,部分和問題として知られるNP完全決定問題のクラスに対する解を求めるGrover探索を提案する。 各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
  論文  参考訳（メタデータ） (2020-09-11T17:31:39Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

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

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