論文の概要: A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
- arxiv url: http://arxiv.org/abs/2402.17301v2
- Date: Wed, 25 Sep 2024 14:39:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-09 04:32:42.292837
- Title: A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
- Title（参考訳）: コンパイルされたXORゲームの価値に関する計算的Tsirelsonの理論
- Authors: David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang,
- Abstract要約: Kalaiらによって提案されたコンパイラは,任意の2プレーヤXORゲームに対して健全であることを示す。
提案手法を用いて並列繰り返しXORゲームのコンパイル値の厳密なバウンダリを含む,いくつかの追加結果を得た。
- 参考スコア（独自算出の注目度）: 9.818381970014284
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a ``nice'' sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.
- Abstract（参考訳）: 非局所ゲームは、複数の空間的に分離された量子デバイスの設定において、絡み合いを理解し、量子プロトコルを構築するための基本的なツールである。
本研究は,古典的検証器と暗号的に制限された単一量子デバイスの間で,コンパイルされた非局所ゲームであるKalai et al (STOC '23) によって開始された研究を継続する。本研究の主な成果は,Kalai et al が提案したコンパイラが任意の2つのプレイヤ XOR ゲームに対して健全であることである。Tsirelson の有名な定理は,XOR ゲームに対して,量子値が正確に半定値プログラムによって与えられることを示し,この結果は,コンパイルされたゲームに対する SDP 上界が,コンパイルから生じる無視可能な誤りを負うことを示し,Natarajan と Zhang (FOCS '23) が提起した質問に答える。
本手法を用いて,(1)並列繰り返しXORゲームのコンパイル値の厳密な境界,(2)コンパイルされたXORゲームに対する演算子自己検証文,(3)演算子剛性を示す任意のXORゲームに対する ``nice'' の総和証明など,いくつかの追加結果を得た。
関連論文リスト
- 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) - Photonic implementation of the quantum Morra game [69.65384453064829]
本研究は,古典ゲームを特殊なケースとして含めることにより,従来の研究を基盤とした2プレーヤ量子モラゲームの忠実な翻訳について研究する。
本稿では、アリスが古典ゲームのバランスを崩し、勝利の優位性を持つ量子状態におけるゲームの自然な変形を提案する。
量子情報と通信の研究における量子モラゲームの可能性について論じる。
論文 参考訳（メタデータ） (2023-11-14T19:41:50Z) - Bounding the quantum value of compiled nonlocal games: from CHSH to BQP
verification [2.298932494750101]
Kalaiらは、非ローカルゲームに適用されるブラックボックス暗号コンパイル手順を定義した。
単一プロデューサプロトコルの量子値の完全な理解に向けて前進する。
我々は,BQPに対して単一プロプライエタリな古典的検証プロトコルを提供し,CHSH剛性解析を用いてその健全性を証明した。
論文 参考訳（メタデータ） (2023-03-02T19:20:59Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Connecting XOR and XOR* games [0.0]
我々は、XOR非ローカルゲームとXOR*シーケンシャルゲームという、独占的なリソースを持つ2種類のゲームに焦点を当てる。
特定の仮定の下では、これらの2種類のゲームは、それらの最適戦略を結び付ける明示的な定理によって関連付けられることを証明している。
論文 参考訳（メタデータ） (2022-10-02T00:11:38Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。
また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
論文 参考訳（メタデータ） (2022-09-16T13:59:42Z) - Quantum Advantage from Any Non-Local Game [14.903809621145893]
我々は,任意の$k$プロデューサ非ローカルゲームを単一プロデューサインタラクティブゲームにコンパイルする一般的な方法を示す。
我々のコンパイラは任意の量子同型暗号スキームを使用する。
論文 参考訳（メタデータ） (2022-03-29T19:45:44Z) - 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) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。