論文の概要: A Parallel Repetition Theorem for the GHZ Game
- arxiv url: http://arxiv.org/abs/2008.05059v1
- Date: Wed, 12 Aug 2020 01:32:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-06 11:53:07.308357
- Title: A Parallel Repetition Theorem for the GHZ Game
- Title（参考訳）: GHZゲームにおける並列反復理論
- Authors: Justin Holmgren and Ran Raz
- Abstract要約: GHZゲームが並列に$t$の回数で繰り返される値は、少なくとも$t-Omega(1)$であることを示す。
GHZゲームは、Greenberger, Horne and Zeilingerによって最初に導入されたもので、量子絡みの研究の中心的なゲームである。
- 参考スコア（独自算出の注目度）: 2.561899487681323
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove that parallel repetition of the (3-player) GHZ game reduces the
value of the game polynomially fast to 0. That is, the value of the GHZ game
repeated in parallel $t$ times is at most $t^{-\Omega(1)}$. Previously, only a
bound of $\approx \frac{1}{\alpha(t)}$, where $\alpha$ is the inverse Ackermann
function, was known.
The GHZ game was recently identified by Dinur, Harsha, Venkat and Yuen as a
multi-player game where all existing techniques for proving strong bounds on
the value of the parallel repetition of the game fail. Indeed, to prove our
result we use a completely new proof technique. Dinur, Harsha, Venkat and Yuen
speculated that progress on bounding the value of the parallel repetition of
the GHZ game may lead to further progress on the general question of parallel
repetition of multi-player games. They suggested that the strong correlations
present in the GHZ question distribution represent the "hardest instance" of
the multi-player parallel repetition problem.
Another motivation for studying the parallel repetition of the GHZ game comes
from the field of quantum information. The GHZ game, first introduced by
Greenberger, Horne and Zeilinger, is a central game in the study of quantum
entanglement and has been studied in numerous works. For example, it is used
for testing quantum entanglement and for device-independent quantum
cryptography. In such applications a game is typically repeated to reduce the
probability of error, and hence bounds on the value of the parallel repetition
of the game may be useful.
- Abstract（参考訳）: 3-player) GHZ ゲームの並列反復は多項式的に高速にゲーム値が 0 に減少することを示す。
つまり、GHZゲームが並列に$t$の回数で繰り返される値は、最大$t^{-\Omega(1)}$である。
以前は、$\approx \frac{1}{\alpha(t)}$ のバウンドしか知られておらず、ここで$\alpha$ は逆アッカーマン函数である。
GHZゲームは、最近Dinur、Harsha、Venkat、Yuenによってマルチプレイヤーゲームとして特定された。
実際、結果を証明するためには全く新しい証明テクニックを使用します。
dinur, severea, venkat および yuen は、ghz ゲームの並列反復の値の境界に関する進歩は、マルチプレイヤーゲームの並列反復の一般的な問題においてさらなる進展をもたらすと推測した。
彼らは、ghz問題分布に存在する強い相関関係は、マルチプレイヤー並列反復問題の「最も難しい例」を表していると示唆した。
GHZゲームの並列反復を研究するもう一つの動機は、量子情報の分野から来ている。
ghzゲームはgreenberger, horne, zeilingerによって初めて紹介され、量子の絡み合いの研究の中心的ゲームであり、多くの作品で研究されている。
例えば、量子エンタングルメントのテストやデバイスに依存しない量子暗号の試験に使用される。
このようなアプリケーションでは、ゲームは通常、エラーの確率を減らすために繰り返されるので、ゲームの並列反復の値の境界は有用かもしれない。
関連論文リスト
- Stronger Nonlocality in GHZ States: A Step Beyond the Conventional GHZ Paradox [0.0]
Greenberger-Horne-Zeilinger(GHZ)パラドックスは、3つ以上のサブシステムを持つ量子系を含む。
本稿では,GHZゲームにおいて,確率条件を複数の可能性からランダムに選択し,ランダムに選択した当事者のうちの1つにのみ露呈するランダム化変種を導入する。
このランダム化されたGHZパラドックスは、GHZ状態を用いて完全に解決できることを示し、元のパラドックスよりも潜在的に強い非局所性を示す。
論文 参考訳（メタデータ） (2024-09-23T05:12:28Z) - A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
暗号コンパイラは、任意の非ローカルゲームを単一の計算バウンド証明器で対話的プロトコルに変換する。
我々は、コンパイルされた2人プレイヤの非ローカルゲームに対して量子音響結果を確立する。
論文 参考訳（メタデータ） (2024-08-13T08:11:56Z) - Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。
不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
論文 参考訳（メタデータ） (2024-06-23T00:27:28Z) - A Computational Tsirelson's Theorem for the Value of Compiled XOR Games [9.818381970014284]
Kalaiらによって提案されたコンパイラは,任意の2プレーヤXORゲームに対して健全であることを示す。
提案手法を用いて並列繰り返しXORゲームのコンパイル値の厳密なバウンダリを含む,いくつかの追加結果を得た。
論文 参考訳（メタデータ） (2024-02-27T08:24:21Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - Repeated quantum game as a stochastic game: Effects of the shadow of the
future and entanglement [0.0]
本稿では,新しい繰り返しゲームプロトコルを用いて構築された量子ゲームについて,体系的な研究を行う。
2つの純粋な戦略の相違が、ディスカウント要因に大きく依存していることがわかりました。
量子ゲーム設定では、高い割引係数に対するティット・フォー・テイト戦略により、常に欠陥戦略を破ることができる。
論文 参考訳（メタデータ） (2023-12-08T15:54:51Z) - Photonic implementation of the quantum Morra game [69.65384453064829]
本研究は,古典ゲームを特殊なケースとして含めることにより,従来の研究を基盤とした2プレーヤ量子モラゲームの忠実な翻訳について研究する。
本稿では、アリスが古典ゲームのバランスを崩し、勝利の優位性を持つ量子状態におけるゲームの自然な変形を提案する。
量子情報と通信の研究における量子モラゲームの可能性について論じる。
論文 参考訳（メタデータ） (2023-11-14T19:41:50Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - On the relation between completely bounded and $(1,cb)$-summing maps
with applications to quantum XOR games [65.51757376525798]
一般作用素空間から C$*$-代数の双対への線型写像が与えられたとき、その完全有界ノルムは、その$(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
論文 参考訳（メタデータ） (2021-12-09T21:06:52Z) - Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
サブトラクションゲームはワンヒープニムゲームと呼ばれることもある。
量子ゲーム理論において、サブトラクションゲームの部分集合は、ゼロサムゲームの最初の明示的に定義されたクラスとなった。
サブトラクションゲームのより狭い部分集合については、すべての決定論的アルゴリズムを超える正確な量子サブ線形アルゴリズムが知られている。
論文 参考訳（メタデータ） (2020-06-12T06:36:07Z) - Infinitely Repeated Quantum Games and Strategic Efficiency [0.0]
繰り返し量子ゲーム理論は、量子戦略を選択するプレイヤー間の長期の関係に対処する。
従来の量子ゲーム理論では、単一ラウンド量子ゲームや、ほとんどの有限繰り返しゲームが広く研究されている。
論文 参考訳（メタデータ） (2020-05-12T07:39:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。