論文の概要: 3XOR Games with Perfect Commuting Operator Strategies Have Perfect
Tensor Product Strategies and are Decidable in Polynomial Time
- arxiv url: http://arxiv.org/abs/2010.16290v1
- Date: Fri, 30 Oct 2020 14:35:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-26 07:49:46.244258
- Title: 3XOR Games with Perfect Commuting Operator Strategies Have Perfect
Tensor Product Strategies and are Decidable in Polynomial Time
- Title（参考訳）: 完全通勤操作者戦略を持つ3XORゲームは、テンソル製品戦略が完璧であり、多項式時間で決定可能である
- Authors: Adam Bene Watts and J. William Helton
- Abstract要約: 完全通勤操作戦略を持つ3XORゲームについて検討する。
ゲームに対する完全な通勤者戦略の存在を時間内に決定できることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider 3XOR games with perfect commuting operator strategies. Given any
3XOR game, we show existence of a perfect commuting operator strategy for the
game can be decided in polynomial time. Previously this problem was not known
to be decidable. Our proof leads to a construction, showing a 3XOR game has a
perfect commuting operator strategy iff it has a perfect tensor product
strategy using a 3 qubit (8 dimensional) GHZ state. This shows that for perfect
3XOR games the advantage of a quantum strategy over a classical strategy
(defined by the quantum-classical bias ratio) is bounded. This is in contrast
to the general 3XOR case where the optimal quantum strategies can require high
dimensional states and there is no bound on the quantum advantage.
To prove these results, we first show equivalence between deciding the value
of an XOR game and solving an instance of the subgroup membership problem on a
class of right angled Coxeter groups. We then show, in a proof that consumes
most of this paper, that the instances of this problem corresponding to 3XOR
games can be solved in polynomial time.
- Abstract（参考訳）: 完全通勤操作戦略を持つ3XORゲームを考える。
任意の3xorゲームが与えられると、ゲームに対する完全可換作用素戦略の存在は多項式時間で決定できる。
以前はこの問題は決定不可能であった。
我々の証明は、3XORゲームが完全可換作用素戦略を持つことを示す構成へと導いており、3 qubit (8 次元) GHZ 状態を用いた完全テンソル積戦略を持つ。
これは完全3XORゲームにおいて、古典的戦略(古典的バイアス比によって定義される)よりも量子戦略の利点が有界であることを示している。
一般的な3XORの場合とは対照的に、最適量子戦略は高次元状態を必要とし、量子上の優位性に縛られない。
これらの結果を証明するために、まず、xorゲームの価値の決定と、右アングルコクセター群のクラスにおけるサブグループメンバーシップ問題の解との同値性を示す。
そして、この論文の大部分を消費する証明において、3XORゲームに対応する問題の事例を多項式時間で解くことができることを示す。
関連論文リスト
- 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) - 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) - On the power of quantum entanglement in multipartite quantum XOR games [3.655021726150368]
特に、量子絡み合いは、これらのゲームをプレイするための局所的な操作や古典的なコミュニケーションよりもはるかに強力な資源となる。
この結果は、近年、絡み合ったバイアスは常に一方通行の古典的コミュニケーションバイアスの普遍的定数倍で上界であることが証明されたバイパルタイトの場合と強い対比を示す。
論文 参考訳（メタデータ） (2023-02-23T06:26:37Z) - Satisfiability Phase Transtion for Random Quantum 3XOR Games [0.0]
ランダムに生成された3XORゲームの動作を,多数の質問に対して数値的に検討する。
我々の実験は、ランダムに生成されたゲームが擬テレパシーである確率が 1 から遠く離れていることを強く示唆している。
また、ランダムに生成された3XORゲームが量子および古典的な「相転移」の両方を実行しているという強い証拠も見つかる。
論文 参考訳（メタデータ） (2022-09-10T12:54:53Z) - Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states [0.0]
特に、ほぼ完全な量子戦略は、小さなフロベニウスノルムにおける対応するBCS代数の近似表現であることを示す。
XOR の非局所ゲームに対して、準最適量子戦略はゲームに関連する対応する *-代数の近似表現であることを示す。
論文 参考訳（メタデータ） (2022-03-04T19:05:58Z) - 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) - Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
ターン型戦略ゲーム(Tribes)のためのプログレッシブアンプランによるPortfolio Monte Carlo Tree Searchを提案する。
品質分散アルゴリズム(MAP-Elites)を使用して異なるプレイスタイルを実現し、競争レベルを維持しながらパラメータ化する方法を示します。
その結果,このアルゴリズムは,トレーニングに用いるレベルを超えて,幅広いゲームレベルにおいても,これらの目標を達成できることが示された。
論文 参考訳（メタデータ） (2021-04-17T20:33:24Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。
この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。
各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-21T17:51:57Z) - Efficient exploration of zero-sum stochastic games [83.28949556413717]
ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。
限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。
私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
論文 参考訳（メタデータ） (2020-02-24T20:30:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。