論文の概要: Separations in query complexity for total search problems

• arxiv url: http://arxiv.org/abs/2410.16245v1
• Date: Mon, 21 Oct 2024 17:51:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:16:33.805058
• Title: Separations in query complexity for total search problems
• Title（参考訳）: 全探索問題に対する問合せ複雑性の分離
• Authors: Shalev Ben-David, Srijita Kundu,
• Abstract要約: 本稿では,全探索問題のクラスTFNPの問合せ複雑性の類似について検討する。 特定の条件下で部分関数を全探索問題に変換する方法を提供する。 また、探索問題を部分関数に変換する方法も提供します。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We study the query complexity analogue of the class TFNP of total search problems. We give a way to convert partial functions to total search problems under certain settings; we also give a way to convert search problems back into partial functions. As an application, we give new separations for degree-like measures. We give an exponential separation between quantum query complexity and approximate degree for a total search problem. We also give an exponential separation between approximate degree and the positive quantum adversary for a total search problem. We then strengthen the former separation to upper bound a larger measure: the two-sided approximate non-negative degree, also called the conical junta degree. This measure is often larger than quantum query complexity and even a separation from randomized query complexity was not known. We extend our results to communication complexity, and obtain an exponential separation between quantum information complexity and the relaxed partition bound for a total search problem. Even a weaker separation between randomized communication complexity and the relaxed partition bound was not known for total search problems (or even for partial functions). Most of our separations for total search problems can be converted to separations for partial functions. Using this, we reprove the recent exponential separation between quantum query complexity and approximate degree for a partial function by Ambainis and Belovs (2023), among other new results.
• Abstract（参考訳）: 本稿では,全探索問題のクラスTFNPの問合せ複雑性の類似について検討する。 また,特定の条件下で部分関数を全探索問題に変換する方法や,部分関数に変換する方法も提供する。 応用として、次数的な尺度に新たな分離を与える。 我々は,全探索問題に対して,量子クエリ複雑性と近似次数との指数関数的分離を与える。 また、全探索問題に対して、近似次数と正の量子逆数とを指数関数的に分離する。 次に、より大きい測度、すなわち円錐次数(英語版)(conical junta degree)とも呼ばれる二辺近似非負次数(英語版)(two-sided almost non- negative degree)を上界に拡張する。 この尺度は、多くの場合、量子クエリの複雑さよりも大きく、ランダム化されたクエリの複雑さからの分離でさえも分かっていない。 計算結果を通信複雑性に拡張し、全探索問題に対して量子情報複雑性と緩和分割を指数関数的に分離する。 ランダム化された通信複雑性と緩和された分割境界の間のより弱い分離でさえ、全探索問題(あるいは部分関数)については知られていなかった。 総探索問題の分離のほとんどは部分関数の分離に変換できる。 これを用いて、Ambainis と Belovs (2023) による部分関数に対する量子クエリ複雑性と近似次数との最近の指数関数的分離を再現する。

関連論文リスト

• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• The Complexity of Being Entangled [0.0]
  ニールセンの量子状態複雑性へのアプローチは、一元変換の多様体上の特定のノルムで計算された測地線の長さに状態を作るのに必要な最小の量子ゲート数に関係している。 バイパーティイトシステムでは,単一サブシステムに作用するゲートがコストがかからないノルムに対応する結合複雑性について検討する。
  論文  参考訳（メタデータ） (2023-11-07T19:00:02Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• Circuit Complexity through phase transitions: consequences in quantum state preparation [0.0]
  量子多体系の基底状態を作成するための回路の複雑さを解析する。 特に、基底状態が量子相転移に近づくにつれて、この複雑さがどのように成長するか。
  論文  参考訳（メタデータ） (2023-01-11T19:00:10Z)
• A Closer Look at Branch Classifiers of Multi-exit Architectures [103.27533521196817]
  一定の複雑さのブランチはすべてのブランチを同じに保ちますが、複雑性の増大と複雑性の低下は、それぞれバックボーンの遅かれ早かれ複雑なブランチを配置します。 知識の整合性を利用して,背骨に枝を追加する効果を探索する。 以上の結果から,複雑性が増大する分岐は,背骨の特徴的抽象的階層を最小限に破壊することが明らかとなった。
  論文  参考訳（メタデータ） (2022-04-28T08:37:25Z)
• On query complexity measures and their relations for symmetric functions [0.0]
  本稿では, ブール法と逆法を用いて, 量子クエリの複雑性を低く抑える方法について述べる。 また、部分対称関数Gap Majorityの量子クエリ複雑性についても考察する。 証明の複雑さとブロック感度が対称関数の感度と比較していかに大きいかを示す。
  論文  参考訳（メタデータ） (2021-10-25T02:55:39Z)
• Forster Decomposition and Learning Halfspaces with Noise [60.691817861402676]
  フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。 本稿では,Forster変換が存在し,効率よく計算できる少数の分布の解離混合として,任意の分布を効率的に分解可能であることを示す。
  論文  参考訳（メタデータ） (2021-07-12T17:00:59Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)
• Aspects of The First Law of Complexity [0.0]
  我々は、arXiv:1903.04511で提案される最初の複雑性の法則、すなわち、ターゲット状態が摂動した際の複雑性の変動について検討する。 Nielsenの量子回路複雑性に対する幾何学的アプローチに基づいて、変動は最適回路の端にのみ依存する。
  論文  参考訳（メタデータ） (2020-02-13T21:15:57Z)

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

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