論文の概要: A convergent sum-of-squares hierarchy for compiled nonlocal games

• arxiv url: http://arxiv.org/abs/2507.17581v1
• Date: Wed, 23 Jul 2025 15:16:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-24 22:33:15.052432
• Title: A convergent sum-of-squares hierarchy for compiled nonlocal games
• Title（参考訳）: コンパイルされた非局所ゲームに対する収束和-二乗階層
• Authors: David Cui, Chirag Falor, Anand Natarajan, Tina Zhang,
• Abstract要約: 古典的検証器と1つの量子証明器の間でプレイされる「コンパイルされた」非局所ゲームについて検討する。 コンパイルされたゲームにおける量子証明器の成功確率は、ゲームの量子交換演算値によって制限されることを示す。 良質なフレームワークを拡張し、良質な証明書を独占的に検索する半定型プログラムの階層を構築します。
• 参考スコア（独自算出の注目度）: 1.5029560229270191
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We continue the line of work initiated by Kalai et al. (STOC '23), studying "compiled" nonlocal games played between a classical verifier and a single quantum prover, with cryptography simulating the spatial separation between the players. The central open question in this area is to understand the soundness of this compiler against quantum strategies, and apart from results for specific games, all that is known is the recent "qualitative" result of Kulpe et al. (STOC '25) showing that the success probability of a quantum prover in the compiled game is bounded by the game's quantum commuting-operator value in the limit as the cryptographic security parameter goes to infinity. In this work, we make progress towards a quantitative understanding of quantum soundness for general games, by giving a concrete framework to bound the quantum value of compiled nonlocal games. Building on the result of Kulpe et al. together with the notion of "nice" sum-of-squares certificates, introduced by Natarajan and Zhang (FOCS '23) to bound the value of the compiled CHSH game, we extend the niceness framework and construct a hierarchy of semidefinite programs that searches exclusively over nice certificates. We show that this hierarchy converges to the optimal quantum value of the game. Additionally, we present a transformation to make any degree-1 sum-of-squares certificate nice. This approach provides a systematic method to reproduce all known bounds for special classes of games together with Kulpe et al.'s bound for general games from the same framework.
• Abstract（参考訳）: 我々は、古典的検証器と1つの量子証明器の間の「コンパイルされた」非局所ゲームの研究を、プレイヤー間の空間的分離をシミュレートする暗号を用いて、Kalai et al (STOC '23) によって開始された作業のラインを継続する。 この領域の中心的な疑問は、このコンパイラの量子戦略に対する健全性を理解することであり、特定のゲームの結果とは別に、Kulpe et al (STOC '25) の最近の "qualitative" 結果が知られている。 本研究では,一般ゲームにおける量子音質の定量的理解に向けて,コンパイルされた非局所ゲームの量子値に束縛する具体的な枠組みを与える。 Kulpe らは、Natarajan と Zhang (FOCS '23) によって導入され、コンパイルされたCHSHゲームの価値を束縛する「ニッチ」な2乗証明の概念とともに構築し、良質なフレームワークを拡張し、良質な証明書を独占的に検索する半定型プログラムの階層を構築する。 この階層はゲームの最適量子値に収束することを示す。 さらに、任意の次数-1の2乗証明を良好にするための変換を提案する。 このアプローチは、Kulpe et al's bound for general game from the same framework と共に、ゲームの特別なクラスに対する既知のすべての境界を再現する体系的な方法を提供する。

関連論文リスト

• Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy [3.34301287453961]
  両部構成されたベルゲーム毎に、最初の量子音響量境界を示す。 より一般的には、全ての二部ゲームにおいて、コンパイルされたスコアが新しく定式化されたシーケンシャルなNavascu'es-Pironio-Ac'in階層によって与えられる境界を超えないことが示される。
  論文  参考訳（メタデータ） (2025-07-22T20:31:41Z)
• A Game-Theoretic Quantum Algorithm for Solving Magic Squares [2.09260520196733]
  完全量子優位性を持つ2プレイヤー非ローカルゲームであるマジックスクエアゲーム(MSG)の変分フレームワークを提案する。 我々は、ゲームのパリティと一貫性の制約を符号化する値ハミルトニアンを構築し、パラメータ化された量子回路を最適化し、このコストを最小化する。
  論文  参考訳（メタデータ） (2025-05-19T17:12:53Z)
• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  暗号コンパイラは、任意の非ローカルゲームを単一の計算バウンド証明器で対話的プロトコルに変換する。 我々は、コンパイルされた2人プレイヤの非ローカルゲームに対して量子音響結果を確立する。
  論文  参考訳（メタデータ） (2024-08-13T08:11:56Z)
• Quantum bounds for compiled XOR games and $d$-outcome CHSH games [1.099532646524593]
  Kalai et al. のコンパイル手順は、2種類のゲームに対する量子境界を保存することを示す。 任意の qubit の測定に対して、XOR ゲームが存在し、その最適な勝利確率はその測定の特定のペアの自己テストとして機能する。
  論文  参考訳（メタデータ） (2024-03-08T18:20:21Z)
• A Computational Tsirelson's Theorem for the Value of Compiled XOR Games [9.818381970014284]
  Kalaiらによって提案されたコンパイラは,任意の2プレーヤXORゲームに対して健全であることを示す。 提案手法を用いて並列繰り返しXORゲームのコンパイル値の厳密なバウンダリを含む,いくつかの追加結果を得た。
  論文  参考訳（メタデータ） (2024-02-27T08:24:21Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  本研究は,古典ゲームを特殊なケースとして含めることにより,従来の研究を基盤とした2プレーヤ量子モラゲームの忠実な翻訳について研究する。 本稿では、アリスが古典ゲームのバランスを崩し、勝利の優位性を持つ量子状態におけるゲームの自然な変形を提案する。 量子情報と通信の研究における量子モラゲームの可能性について論じる。
  論文  参考訳（メタデータ） (2023-11-14T19:41:50Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• 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 guessing games with posterior information [68.8204255655161]
  後続情報を持つ量子推測ゲームは、量子システムを用いてメッセージと古典的な通信を符号化し、量子測定が実行された後に部分的な情報を与える。 我々は、推理ゲームの対称性を定式化し、対称性が既約表現と関連している場合の最適測定を特徴付ける。
  論文  参考訳（メタデータ） (2021-07-25T19:10:26Z)

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

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