論文の概要: The NPA hierarchy does not always attain the commuting operator value

• arxiv url: http://arxiv.org/abs/2510.04943v1
• Date: Mon, 06 Oct 2025 15:46:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.955416
• Title: The NPA hierarchy does not always attain the commuting operator value
• Title（参考訳）: NPA階層は常に交換演算子値を達成するとは限らない
• Authors: Marco Fanizza, Larissa Kroell, Arthur Mehta, Connor Paddock, Denis Rochette, William Slofstra, Yuming Zhao,
• Abstract要約: 非局所ゲームの可換作用素値が1/2より厳密に大きいかどうかを決定できない。 非局所ゲームの可換演算子値が1/2より厳密に大きいかどうかを決定できないことを示す。
• 参考スコア（独自算出の注目度）: 2.2033670716898475
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. As a corollary, there is a boolean constraint system (BCS) game for which the value of the Navascu\'es-Pironio-Ac\'in (NPA) hierarchy does not attain the commuting operator value at any finite level. Our contribution involves establishing a computable mapping from Turing machines to BCS nonlocal games in which the halting property of the machine is encoded as a decision problem for the commuting operator value of the game. Our techniques are algebraic and distinct from those used to establish MIP*=RE.
• Abstract（参考訳）: 非局所ゲームの可換演算子値が1/2より厳密に大きいかどうかを決定できないことを示す。 座標系として、Navascu\es-Pironio-Ac\in (NPA)階層の値が任意の有限レベルで可換作用素値に達しないブール制約系 (BCS) ゲームが存在する。 我々の貢献はチューリングマシンからBCS非ローカルゲームへの計算可能なマッピングを確立することであり、そのマシンの停止特性はゲームの通勤演算子値の決定問題として符号化される。 我々の手法は代数的であり、MIP*=REを確立するために使われるものとは異なっている。

関連論文リスト

• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  暗号コンパイラは、任意の非ローカルゲームを単一の計算バウンド証明器で対話的プロトコルに変換する。 我々は、コンパイルされた2人プレイヤの非ローカルゲームに対して量子音響結果を確立する。
  論文  参考訳（メタデータ） (2024-08-13T08:11:56Z)
• Bounding the Graph Capacity with Quantum Mechanics and Finite Automata [55.2480439325792]
  チャネルのゼロエラーキャパシティは、エラーのリスクを伴わずに、どれだけの情報を送信できるかを定量化する。 チャネルのシャノン容量とは対照的に、ゼロエラー容量は計算可能であることも示されていない。 ユニタリキャパシティはゼロエラーキャパシティの制御可能な要素内にあることを示す。
  論文  参考訳（メタデータ） (2024-03-16T17:41:01Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• Representation of the Fermionic Boundary Operator [10.522527427240352]
  量子コンピュータ上での完全境界演算子を表現する問題を考える。 まず、境界作用素がフェルミオン生成および消滅作用素の完全和の形で特別な構造を持つことを証明する。 次に、これらの作用素が対対反共役であるという事実を用いて、トロッター化やテイラー級数近似の誤差なしに境界演算子を正確に実装する$O(n)$-depth回路を生成する。
  論文  参考訳（メタデータ） (2022-01-27T13:42:57Z)
• Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy [0.12891210250935145]
  非局所ゲームと算術的階層の関係について検討する。 量子値を正確に計算することは、それを近似するよりも厳密に、また通勤演算子値を計算するより厳密に難しいことを示す。
  論文  参考訳（メタデータ） (2021-10-09T21:53:02Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)

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

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