論文の概要: XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games

• arxiv url: http://arxiv.org/abs/2607.06876v1
• Date: Wed, 08 Jul 2026 00:19:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-09 22:50:30.241482
• Title: XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games
• Title（参考訳）: XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games
• Abstract要約: 我々は、傾いたXORゲームと呼ばれるXORゲームモデルの変種について研究し、勝利条件は出力ビットの1つにのみ依存する。 傾いたXORゲームの量子値を一定精度で近似する計算複雑性は再完備である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. Håstad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.
• Abstract（参考訳）: 勝利条件が2人のプレーヤーの出力ビットのXORのみに依存するXOR非局所ゲームの量子値は多項式時間で近似できることはよく知られている。 我々は、傾いたXORゲームと呼ばれるXORゲームモデルの変種について研究し、勝利条件は出力ビットの1つにのみ依存する。 傾いたXORゲームの量子値を一定精度で近似する問題の計算複雑性は再完備である。 また、この結果は、多項式時間検証器によって生成される多項式長のバイナリ文字列を問うことができる傾き型XORゲームの簡潔なバージョンにまで拡張される。 古典的戦略では、XORゲームと傾いたXORゲームとの区別は不適切である。 Håstad (J. ACM, 2001) は、線形系から XOR ゲームへの還元を用いて、どちらもNP完全で近似可能であることを示した。 提案手法は,線形系ゲームから傾いたXORゲームへの還元として,量子音響にも応用可能であることを示すものである。 XORゲーム」というタイトルはバイナリゲーム(各パーティが1ビット出力する)の特殊な場合であるため、この結果からバイナリゲームはRe-hardで近似可能であることが示唆される。

関連論文リスト

• Quantum non-local games: Quantum relations, projection lattices and rule operators [51.56484100374058]
  (mathcal R)-射影テスト 有限次元入力とノイマン代数の出力を持つ量子ゲーム。 (mathcal R)-射影テスト 有限次元入力とノイマン代数の出力を持つ量子ゲーム。 (mathcal R)-射影テスト 有限次元入力とノイマン代数の出力を持つ量子ゲーム。 (mathcal R)-射影テスト 有限次元入力とノイマン代数の出力を持つ量子ゲーム。
  論文  参考訳（メタデータ） (2026-08-31T09:41:14Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。 我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
  論文  参考訳（メタデータ） (2025-10-20T00:45:47Z)
• Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, $\mathrm{XOR}^{*}$, compiled XOR, $\mathrm{XOR}^{*}$, and strong parallel repetiton of XOR, $\mathrm{XOR}^{*}$, and FFL games [0.0]
  我々は、プレイヤーが量子戦略を用いて操作できるゲームの正確で近似的な最適性を特徴づける。 我々は、量子優位性のための提案された情報源として、他の可能な戦略の変種を記述することで、この取り組みを締めくくる。
  論文  参考訳（メタデータ） (2025-05-09T03:47:41Z)
• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  暗号コンパイラは、任意の非ローカルゲームを単一の計算バウンド証明器で対話的プロトコルに変換する。 我々は、コンパイルされた2人プレイヤの非ローカルゲームに対して量子音響結果を確立する。
  論文  参考訳（メタデータ） (2024-08-13T08:11:56Z)
• A Computational Tsirelson's Theorem for the Value of Compiled XOR Games [9.818381970014284]
  Kalaiらによって提案されたコンパイラは,任意の2プレーヤXORゲームに対して健全であることを示す。 提案手法を用いて並列繰り返しXORゲームのコンパイル値の厳密なバウンダリを含む,いくつかの追加結果を得た。
  論文  参考訳（メタデータ） (2024-02-27T08:24:21Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。 これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
  論文  参考訳（メタデータ） (2022-10-18T15:10:25Z)
• Connecting XOR and XOR* games [0.0]
  我々は、XOR非ローカルゲームとXOR*シーケンシャルゲームという、独占的なリソースを持つ2種類のゲームに焦点を当てる。 特定の仮定の下では、これらの2種類のゲームは、それらの最適戦略を結び付ける明示的な定理によって関連付けられることを証明している。
  論文  参考訳（メタデータ） (2022-10-02T00:11:38Z)
• 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)
• 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time [0.0]
  完全通勤操作戦略を持つ3XORゲームについて検討する。 ゲームに対する完全な通勤者戦略の存在を時間内に決定できることを示す。
  論文  参考訳（メタデータ） (2020-10-30T14:35:19Z)
• Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
  サブトラクションゲームはワンヒープニムゲームと呼ばれることもある。 量子ゲーム理論において、サブトラクションゲームの部分集合は、ゼロサムゲームの最初の明示的に定義されたクラスとなった。 サブトラクションゲームのより狭い部分集合については、すべての決定論的アルゴリズムを超える正確な量子サブ線形アルゴリズムが知られている。
  論文  参考訳（メタデータ） (2020-06-12T06:36:07Z)

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

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