論文の概要: On the Two-sided Permutation Inversion Problem

• arxiv url: http://arxiv.org/abs/2306.13729v2
• Date: Mon, 22 Apr 2024 02:00:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-24 01:02:16.583590
• Title: On the Two-sided Permutation Inversion Problem
• Title（参考訳）: 両面置換反転問題について
• Authors: Gorjan Alagic, Chen Bai, Alexander Poremba, Kaiyan Shi,
• Abstract要約: オラクルが量子クエリーを、置換の前方方向と逆方向の両方に許容する設定について検討する。 逆問題の結果の変動の硬さを結合するいくつかの定理を証明した。 以上の結果から,逆数に対する逆数アクセスが与えられると,逆数問題はかなり難しくなる可能性が示唆された。
• 参考スコア（独自算出の注目度）: 45.69327512339002
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This is a fundamental problem in query complexity, and appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation -- except that the challenge value cannot be submitted to the latter. Within that setting, we consider two options for the inversion algorithm: whether it can get quantum advice about the permutation, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the inversion problem, and establish a number of lower bounds. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse, provided it cannot query the challenge itself.
• Abstract（参考訳）: 置換反転問題において、タスクは、置換へのオラクルアクセスを与えられたチャレンジ値のプリイメージを見つけることである。 これはクエリの複雑さの根本的な問題であり、多くのコンテキスト、特に暗号に現れる。 本研究では,量子クエリが量子列の前方方向と逆方向の両方に許容されるような設定について検討する。 この設定の中で、逆アルゴリズムの2つの選択肢として、置換に関する量子アドバイスが得られるか、前置画像全体を生成する必要があるか(探索)、第1のビットのみを生成するか(決定)を考える。 逆問題の結果の変動の硬さを結合するいくつかの定理を証明し、多くの下界を確立する。 以上の結果から,逆問題自体を問合せできない場合,逆問題に対して逆数アクセスが与えられると,逆問題はかなり難しくなる可能性が示唆された。

関連論文リスト

• Permutation Superposition Oracles for Quantum Query Lower Bounds [14.957648729581502]
  入力-出力ペアの述語に対するアルゴリズムの成功確率を、結果のオラクルシミュレーションを用いてバウンドする方法を示す。 本研究では, 1ラウンドスポンジ構成がランダムな置換モデルに対して無条件に事前画像に抵抗可能であることを示す。
  論文  参考訳（メタデータ） (2024-07-12T19:27:13Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Penalty Weights in QUBO Formulations: Permutation Problems [0.0]
  量子コンピュータで動くよう設計された最適化アルゴリズムは 近年 研究の関心を集めています これらの解法の多くは、二項形式と二項形式の問題を最適化することしかできない。 多くの最適化問題があり、自然に置換として表される。 より有望な結果をもたらすペナルティ重みを計算するための新しい静的手法を提案する。
  論文  参考訳（メタデータ） (2022-06-20T22:00:38Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandryは、量子クエリアルゴリズムとランダム関数に対応する量子オラクルの間の相互作用を研究した。 オラクルがランダム関数の代わりにランダムな置換に対応する場合にも同様の解釈を導入する。 乱数関数と乱数置換の両方がセキュリティ証明において極めて重要であるため、本フレームワークが量子暗号に応用されることを期待する。
  論文  参考訳（メタデータ） (2021-03-16T11:05:48Z)
• Multiview Sensing With Unknown Permutations: An Optimal Transport Approach [42.62524143925126]
  我々は、最適な輸送のレンズを介して未知の置換の対象となる信号を回復する問題を再検討します。 これを利用して、ソリューションのより可能性の高い置換を促進する正規化関数を導入しています。 一般的な問題は凸ではありませんが、結果として生じる正規化問題の適切な緩和は、OTのよく発達した機械を利用し、トラクタブルアルゴリズムを開発することを可能にします。
  論文  参考訳（メタデータ） (2021-03-12T18:48:18Z)
• Quantum Permutation Synchronization [88.4588059792167]
  本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。 本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
  論文  参考訳（メタデータ） (2021-01-19T17:51:02Z)

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

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