論文の概要: A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
- arxiv url: http://arxiv.org/abs/2402.17301v1
- Date: Tue, 27 Feb 2024 08:24:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-28 17:12:20.886688
- 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ゲームのコンパイル値の厳密なバウンダリを含む,いくつかの追加結果を得た。
- 参考スコア（独自算出の注目度）: 10.187610891144452
- 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（参考訳）: 非局所ゲームは、複数の空間的に分離された量子デバイスの設定において、絡み合いを理解し、量子プロトコルを構築するための基本的なツールである。
本研究は、古典的検証器と暗号に制限された1つの量子デバイスの間で行われる非局所的ゲームのkalaiら(stoc '23)による研究を継続する。
我々の主な成果は、Kalaiらによって提案されたコンパイラが、任意の2プレーヤXORゲームに対してサウンドであることである。
tsirelson の有名な定理は、xor のゲームでは量子値が半定値のプログラムによって正確に与えられることを示し、sdp の上限がコンパイル結果から生じる不可解な誤差までコンパイルされたゲームに対して保持することを示した。
これはnataarajan と zhang (focs '23) が提起した chsh ゲームの特定のケースに対して健全性を示した質問に対する答えである。
我々は,(1)並列繰り返しXORゲームのコンパイル値の厳密なバウンダリ,(2)コンパイルされたXORゲームに対する演算子自己検証文,(3)演算子剛性を示す任意のXORゲームに対する ` `nice' sum-of-squares 証明書など,いくつかの追加結果を得た。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。