論文の概要: Certificate Games and Consequences for the Classical Adversary Bound

• arxiv url: http://arxiv.org/abs/2211.03396v3
• Date: Mon, 10 Mar 2025 20:14:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 19:16:10.913718
• Title: Certificate Games and Consequences for the Classical Adversary Bound
• Title（参考訳）: 古典的逆境の認定ゲームとコンシークエンス
• Authors: Sourav Chakraborty, Anna Gál, Mika Göös, Sophie Laplante, Rajat Mittal, Anupa Sunny,
• Abstract要約: 証明ゲームの4つのバージョン、すなわち、プライベートコイン、パブリックコイン、共有エンタングルメント、および非署名ゲームについて検討する。 量子測度は古典的クエリモデルと量子的クエリモデルの間に興味深い、そして驚くべき違いを明らかにしている。
• 参考スコア（独自算出の注目度）: 3.11717505289722
• License:
• Abstract: We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting. We study four versions of certificate games, namely private coin, public coin, shared entanglement and non-signaling games. The public-coin variant of certificate games gives a new characterization of the classical adversary bound, a lower bound on randomized query complexity which was introduced as a classical version of the quantum (non-negative) quantum adversary bound. We show that complexity in the public coin model (therefore also the classical adversary) is bounded above by certificate complexity, as well as by expectational certificate complexity and sabotage complexity. On the other hand, it is bounded below by fractional and randomized certificate complexity. The quantum measure reveals an interesting and surprising difference between classical and quantum query models: the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of $n$ on the quantum certificate game complexity of the OR function, whose quantum query complexity is $\Theta(\sqrt{n})$, then go on to show that this ``non-signaling bottleneck'' applies to all functions with high sensitivity, block sensitivity, fractional block sensitivity, as well as classical adversary. This implies the collapse of all models of certificate games, except private randomness, to the classical adversary bound. We consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1, and give a new characterization of sensitivity and spectral sensitivity.
• Abstract（参考訳）: 我々は,2人のプレーヤーに異なる関数値の入力が与えられ,x_i\neq y_i$ のような指数 $i$ をゼロコミュニケーション設定で出力するゲームに勝つ確率に基づく複雑性の尺度 Certificate Game complexity を紹介し,研究する。 証明ゲームの4つのバージョン、すなわち、プライベートコイン、パブリックコイン、共有エンタングルメント、および非署名ゲームについて検討する。 証明ゲームの公開コイン変種は、量子(非負)量子逆境界の古典的なバージョンとして導入されたランダム化クエリ複雑性の下位境界である古典的逆境界の新たな特徴を与える。 公的なコインモデルの複雑さ(前述した古典的逆境)は、証明書の複雑さと期待された証明書の複雑さと破壊の複雑さによって境界づけられていることが示される。 一方、以下は分数的およびランダム化証明書の複雑さによって制限される。 この量子測度は、古典的および量子的クエリモデルの間の興味深い、驚くべき違いを明らかにしている。 量子情報の概念である非符号化(non-signaling)を用いて、OR関数の量子証明ゲーム(quantum certificate game)の複雑さに$n$の低いバウンダリを与える。その量子的クエリ複雑性は$\Theta(\sqrt{n})$である。 これは、私的ランダム性を除いて、証明書ゲームの全モデルが古典的な逆境に崩壊することを意味する。 両プレイヤーの入力をハミング距離1に制限したシングルビット版証明書ゲームについて検討し、感度とスペクトル感度の新たな特徴を与える。

関連論文リスト

• Quantum complexity and localization in random quantum circuits [0.0]
  ランダム量子回路の複雑性を計測・無測定で研究する。 測定なしの$N$ qubitsの場合、飽和値は$2N-1$、飽和時間は$2N$となる。 複雑性はアンダーソンの局所化と多体局在の新しいプローブとして機能する。
  論文  参考訳（メタデータ） (2024-09-05T16:10:54Z)
• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  暗号コンパイラは、任意の非ローカルゲームを単一の計算バウンド証明器で対話的プロトコルに変換する。 我々は、コンパイルされた2人プレイヤの非ローカルゲームに対して量子音響結果を確立する。
  論文  参考訳（メタデータ） (2024-08-13T08:11:56Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Learning quantum states and unitaries of bounded gate complexity [2.034135396070497]
  我々は、G$2量子ビットゲートを持つ量子回路によって生成された状態を微量なトレース距離に学習するには、G$で線形にスケールするサンプル複雑性が必要であることを証明した。 また、$G$ゲートによって生成されるユニタリを、小さな平均ケースエラーに対して線形に$G$で学習するのに最適なクエリの複雑さが証明される。
  論文  参考訳（メタデータ） (2023-10-30T18:00:03Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Majorization-based benchmark of the complexity of quantum processors [105.54048699217668]
  我々は、様々な量子プロセッサの動作を数値的にシミュレートし、特徴付ける。 我々は,各デバイスの性能をベンチマークラインと比較することにより,量子複雑性を同定し,評価する。 我々は、回路の出力状態が平均して高い純度である限り、偏化ベースのベンチマークが成り立つことを発見した。
  論文  参考訳（メタデータ） (2023-04-10T23:01:10Z)
• On query complexity measures and their relations for symmetric functions [0.0]
  本稿では, ブール法と逆法を用いて, 量子クエリの複雑性を低く抑える方法について述べる。 また、部分対称関数Gap Majorityの量子クエリ複雑性についても考察する。 証明の複雑さとブロック感度が対称関数の感度と比較していかに大きいかを示す。
  論文  参考訳（メタデータ） (2021-10-25T02:55:39Z)
• Straddling-gates problem in multipartite quantum systems [20.428960719376164]
  量子回路の複雑性,結合複雑性の変種について検討する。 任意の$m$partite Schmidt decomposable状態が$m$のバインディング複雑性を持つことを示す。
  論文  参考訳（メタデータ） (2021-10-13T16:28:12Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Complexity limitations on one-turn quantum refereed games [0.6091702876917281]
  本論文は,量子参照ゲームの理論的側面を研究する。 抽象ゲームは、審判に量子状態を送信する2人のプレーヤーの間のものである。 審判は、2つの状態に対して効率よく実施可能な共同測定を行い、どのプレイヤーが勝つかを判定する。
  論文  参考訳（メタデータ） (2020-02-04T19:28:03Z)

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

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