論文の概要: 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
• Authors: Richard Cleve, Eric Culf, Aviv Taller,
• 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で近似可能であることが示唆される。

関連論文リスト

• 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)
• 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)

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

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