論文の概要: Permutation Superposition Oracles for Quantum Query Lower Bounds

• arxiv url: http://arxiv.org/abs/2407.09655v1
• Date: Fri, 12 Jul 2024 19:27:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-16 21:28:05.266250
• Title: Permutation Superposition Oracles for Quantum Query Lower Bounds
• Title（参考訳）: 量子クエリローバウンドに対する置換重ね合わせオラクル
• Authors: Christian Majenz, Giulio Malavolta, Michael Walter,
• Abstract要約: 入力-出力ペアの述語に対するアルゴリズムの成功確率を、結果のオラクルシミュレーションを用いてバウンドする方法を示す。 本研究では, 1ラウンドスポンジ構成がランダムな置換モデルに対して無条件に事前画像に抵抗可能であることを示す。
• 参考スコア（独自算出の注目度）: 14.957648729581502
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a generalization of Zhandry's compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry's technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use strictly monotone factorizations to represent the permutation in the oracle's database. As an application of our framework, we show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model. This proves a conjecture by Unruh.
• Abstract（参考訳）: 本稿では,Zhandryの圧縮オラクル法をランダムな置換に一般化する手法を提案する。 そこで本稿では,ランダムな置換への一般化に抵抗したZhandryの手法の重要な特徴である,入力-出力対の述語に対するアルゴリズムの成功確率の有界化に,結果として生じるオラクルシミュレーションを利用する方法を示す。 重要な技術的要素の1つは、オラクルのデータベースの置換を表すために厳密に単調な分解を使用することである。 本フレームワークの適用例として, 1ラウンドスポンジ構成は, ランダムな置換モデルに対して無条件プレモージュ耐性を有することを示す。 これはウンルーの予想を証明している。

関連論文リスト

• Random sampling of permutations through quantum circuits [0.0]
  我々は,Steinhaus-Johnson-Trotterアルゴリズムからインスピレーションを得た,置換のランダムサンプリングのための古典的アルゴリズムを提案する。 我々は、量子回路モデルを用いて、量子回路モデルを用いて、$n$-qubit系に対する置換のランダムサンプリングを行う。
  論文  参考訳（メタデータ） (2024-09-04T18:19:30Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  簡単な構成は、少数の入力で元のものと矛盾する「反転」ランダムオラクルを、ランダム関数から微分不可能な対象に変換することができることを証明している。 この結果から, 暗号プリミティブの設計者は, 通常のクリプトグラフィ設定で, ランダムなオラクルを信頼できるブラックボックスとして使用することができる。
  論文  参考訳（メタデータ） (2024-04-15T04:01:50Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• A Survey and Analysis of Evolutionary Operators for Permutations [0.0]
  置換を進化させるには、特別な進化作用素が必要である。 本稿では、置換のための進化的演算子の幅を調査する。 これらのすべては、進化計算のためのオープンソースのJavaライブラリであるChips-n-Salsaで実装しています。
  論文  参考訳（メタデータ） (2023-11-24T16:32:44Z)
• On the Two-sided Permutation Inversion Problem [45.69327512339002]
  オラクルが量子クエリーを、置換の前方方向と逆方向の両方に許容する設定について検討する。 逆問題の結果の変動の硬さを結合するいくつかの定理を証明した。 以上の結果から,逆数に対する逆数アクセスが与えられると,逆数問題はかなり難しくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2023-06-23T18:31:48Z)
• Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
  まず、各入力トークンに複数の出力トークンをタグ付けします。 次に、新しいパラメータ化法と置換予測法を用いて、トークンを出力シーケンスに配置する。 我々のモデルは、事前訓練されたセq2seqモデルと、現実的なセマンティック解析タスクに関する先行研究より優れている。
  論文  参考訳（メタデータ） (2023-05-26T14:09:35Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandryは、量子クエリアルゴリズムとランダム関数に対応する量子オラクルの間の相互作用を研究した。 オラクルがランダム関数の代わりにランダムな置換に対応する場合にも同様の解釈を導入する。 乱数関数と乱数置換の両方がセキュリティ証明において極めて重要であるため、本フレームワークが量子暗号に応用されることを期待する。
  論文  参考訳（メタデータ） (2021-03-16T11:05:48Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。 本研究では,理論特性の知見を得るための後悔分析法を提案する。 二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
  論文  参考訳（メタデータ） (2021-02-26T10:15:57Z)

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

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