論文の概要: Lower bounds on quantum query complexity for symmetric functions

• arxiv url: http://arxiv.org/abs/2110.12616v3
• Date: Tue, 8 Feb 2022 12:41:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-10 08:10:03.943014
• Title: Lower bounds on quantum query complexity for symmetric functions
• Title（参考訳）: 対称関数に対する量子クエリ複雑性の下位境界
• Authors: Rajat Mittal, Sanjay S Nair, Sunayana Patro
• Abstract要約: 対称関数に対する量子クエリ複雑性に対する具体的な下界手法の値を示す。 また、部分対称関数Gap Majorityの量子クエリ複雑性についても考察する。 さらに,証明の複雑さとブロック感度が,対称関数に対する感度(定数要素まで)と比較していかに大きいかを検討した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show that the recently introduced measure of spectral sensitivity give the same value as both these bounds (positive adversary and approximate degree) for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.
• Abstract（参考訳）: 量子複雑性における問合せモデルの優位の主な理由の1つは、多項式法と逆法という具体的な下限法が存在することである。 これらの手法を使って下限を与えるだけでなく、それらを比較して関連付ける努力も盛んである。 対称関数のクラスに対する量子クエリの複雑性に対するこれらの境界の価値を考察し、おそらく最も自然で基本的なブール関数の集合の1つである。 最近導入されたスペクトル感度の測度は、すべての全対称ブール関数に対するこれらの境界(正の逆数と近似次数)に等しい値を与える。 また、部分対称関数Gap Majorityの量子クエリ複雑性についても考察する。 ランダム化クエリの複雑さの構成を理解する上で,近年重要になっている。 我々はギャップ多数の量子クエリの複雑性を特徴付け、ノイズの多いランダムなクエリの複雑性(ben-david and blais, focs 2020)を量子クエリの複雑さの観点から下限に示す。 さらに,対称関数に対する感度(定数まで)と比較して,証明書の複雑さとブロックの感度がどの程度大きいかを検討した。 強固な分離、すなわち、可能な分離の上限を与え、同じことを達成する構成関数を示す。

関連論文リスト

• Quantum advantage and lower bounds in parallel query complexity [0.0]
  本稿では,全関数に対する量子・ランダム化・決定論的(逐次的)問合せ複雑性について検討する。 これらの測度の平行一般化の間には、はるかに大きな分離が可能であることが分かる。 逐次上界から並列量子下界を導出する新しい手法を開発した。
  論文  参考訳（メタデータ） (2024-10-03T16:50:00Z)
• Quantum and Classical Communication Complexity of Permutation-Invariant Functions [4.410515368583671]
  置換不変ブール関数の量子的およびランダムな通信複雑性は(対数係数まで)2次同値であることを示す。 本研究は,通信複雑性に対するクエリ複雑性に関する最近の研究を拡張したものである。
  論文  参考訳（メタデータ） (2023-12-31T11:07:49Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Anti-symmetric Barron functions and their approximation with sums of determinants [1.8076403084528587]
  量子物理学の基本的な問題は、同一粒子の置換の下で完全に非対称な関数を符号化することである。 反対称構造を明示的に符号化することにより、バロン空間に属する反対称函数が行列式の和で効率的に近似できることを証明できる。
  論文  参考訳（メタデータ） (2023-03-22T18:31:15Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• Bounds on quantum evolution complexity via lattice cryptography [0.0]
  量子論における可積分運動とカオス運動の差は、対応する進化作用素の複雑さによって表される。 ここでの複雑性は、時間依存進化作用素とユニタリ群内の原点の間の最短測地線距離として理解されている。
  論文  参考訳（メタデータ） (2022-02-28T16:20:10Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)

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

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