論文の概要: On query complexity measures and their relations for symmetric functions
- arxiv url: http://arxiv.org/abs/2110.12616v5
- Date: Mon, 19 Feb 2024 07:04:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 07:55:12.627232
- Title: On query complexity measures and their relations 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: The main reason for query model's prominence in complexity theory and quantum
computing is the presence of concrete lower bounding techniques: polynomial and
adversary method. There have been considerable efforts to give lower bounds
using these methods, and to compare/relate them with other measures based on
the decision tree.
We explore the value of these lower bounds on quantum query complexity and
their relation with other decision tree based complexity measures for the class
of symmetric functions, arguably one of the most natural and basic sets of
Boolean functions. We show an explicit construction for the dual of the
positive adversary method and also of the square root of private coin
certificate game complexity for any total symmetric function. This shows that
the two values can't be distinguished for any symmetric function. Additionally,
we show that the recently introduced measure of spectral sensitivity gives the
same value as both positive adversary and approximate degree for every total
symmetric Boolean function.
Further, we 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.
Finally, we study how large certificate complexity and block sensitivity can
be as compared to sensitivity for symmetric functions (even up to constant
factors). We show tight separations, i.e., give upper bounds on possible
separations and construct functions achieving the same.
- Abstract（参考訳）: クエリモデルの複雑性理論と量子コンピューティングにおける優位性の主な理由は、多項式と逆法という具体的な下界技術の存在である。
これらの手法を用いて下限を下限に定め、決定木に基づく他の指標と比較・比較する試みが盛んに行われている。
量子クエリの複雑性に対するこれらの下限の値と、対称関数のクラスに対する他の決定木に基づく複雑性測度との関係について、おそらく最も自然で基本的なブール関数の集合の1つである。
本論文では,任意の対称関数に対する正逆法とプライベートコイン証明書ゲーム複雑性の平方根の双対に対する明示的な構成を示す。
これは、2つの値がいかなる対称関数に対しても区別できないことを示している。
さらに,最近導入されたスペクトル感度の測定値は,全対称ブール関数の正の逆数と近似次数の両方と同じ値を与えることを示した。
さらに,部分対称関数である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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。