論文の概要: Certificate games
- arxiv url: http://arxiv.org/abs/2211.03396v2
- Date: Tue, 8 Nov 2022 11:39:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-20 02:02:13.503467
- Title: Certificate games
- Title（参考訳）: 証明ゲーム
- Authors: Sourav Chakraborty, Anna G\'al, Sophie Laplante, Rajat Mittal, Anupa
Sunny
- Abstract要約: 本稿では,ゲームに勝つ確率に基づいた複雑性尺度であるCertificate Game complexityについて検討する。
公開コインモデルの複雑さはランダム化クエリと証明書の複雑さによって上限づけられていることを示す。
我々は証明書ゲームのシングルビット版を考える(この2人のプレイヤーのインプットはハミング距離が1ドル)。
共有ランダム性を持つシングルビット版の証明書ゲーム複雑性は、一定要素までの感度に等しいことを証明した。
- 参考スコア（独自算出の注目度）: 2.817395666721831
- License: http://creativecommons.org/licenses/by/4.0/
- 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 $i$ such that $x_i\neq
y_i$ (zero-communication setting).
We give upper and lower bounds for private coin, public coin, shared
entanglement and non-signaling strategies, and give some separations. We show
that complexity in the public coin model is upper bounded by Randomized query
and Certificate complexity. On the other hand, it is lower bounded by
fractional and randomized certificate complexity, making it a good candidate to
prove strong lower bounds on randomized query complexity. Complexity in the
private coin model is bounded from below by zero-error randomized query
complexity.
The quantum measure highlights an interesting and surprising difference
between classical and quantum query models. Whereas the public coin certificate
game complexity is bounded from above by randomized query complexity, 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 or fractional block sensitivity.
We consider the single-bit version of certificate games (inputs of the two
players have Hamming distance $1$). We prove that the single-bit version of
certificate game complexity with shared randomness is equal to sensitivity up
to constant factors, giving a new characterization of sensitivity. The
single-bit version with private randomness is equal to $\lambda^2$, where
$\lambda$ is the spectral sensitivity.
- Abstract（参考訳）: 本稿では,2人のプレーヤーに異なる関数値の入力が与えられ,x_i\neq y_i$(ゼロコミュニケーション設定)のような$i$の出力が要求されるゲームに勝つ確率に基づく複雑性の尺度であるCertificate Game complexityを紹介し,研究する。
我々は、プライベートコイン、パブリックコイン、共有絡み合いとノンシグナリング戦略の上限を上下に設定し、いくつかの分離を与える。
公開コインモデルの複雑さはランダム化クエリと証明書の複雑さによって上限づけられていることを示す。
一方、分数的およびランダム化証明書の複雑さにより境界が低くなり、ランダム化クエリの複雑さに対して強い下位境界を証明するのがよい候補となる。
プライベートコインモデルの複雑さは、ゼロエラーランダム化クエリの複雑さによって下から制限される。
この量子測度は、古典的および量子的クエリーモデルの間の興味深い、驚くべき違いを浮き彫りにする。
公開コイン証明書ゲーム複雑性はランダム化されたクエリ複雑性によって上から区切られているのに対し、量子証明書ゲーム複雑性は量子クエリ複雑性よりも2倍大きい可能性がある。
量子情報の概念であるノンシグナリング(non-signaling)を使用して、$or$関数の量子証明書ゲーム複雑性(量子クエリの複雑性は$\theta(\sqrt{n})$)を低く設定し、その後、この ‘non-signaling bottleneck'' が高感度、ブロック感度、分数ブロック感度のすべての関数に適用されることを示す。
私たちは、証明書ゲームのシングルビットバージョンを考えています(2人のプレーヤーの入力は、距離が1ドル弱です)。
共有ランダム性を持つシングルビット版の証明書ゲーム複雑性は、一定要素までの感度に等しいことを証明し、新しい感度特性を与える。
プライベートなランダム性を持つシングルビットバージョンは$\lambda^2$に等しいが、$\lambda$はスペクトル感度である。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。