A Computational Tsirelson's Theorem for the Value of Compiled XOR Games

• URL: http://arxiv.org/abs/2402.17301v1
• Date: Tue, 27 Feb 2024 08:24:21 GMT
• Title: A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
• Authors: David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang
• Abstract summary: We show that the compiler proposed by Kalai et al. is sound for any two-player XOR game. Using our techniques, we obtain several additional results, including tight bounds on the compiled value of parallel-repeated XOR games.
• Score: 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.

Related papers

• Quantum bounds for compiled XOR games and $d$-outcome CHSH games [1.099532646524593]
  We show that the compilation procedure of Kalai et al. preserves the quantum bound for two classes of games. For any pair of qubit measurements, there exists an XOR game such that its optimal winning probability serves as a self-test for that particular pair of measurements.
  arXiv  Detail & Related papers  (2024-03-08T18:20:21Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case. We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game. We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
  arXiv  Detail & Related papers  (2023-11-14T19:41:50Z)
• Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification [2.298932494750101]
  Kalai et al. defined a black-box cryptographic compilation procedure that applies to any nonlocal game. We make progress towards a full understanding of the quantum value of the single-prover protocols. We give a single-prover cryptographically sound classical verification protocol for BQP, and we prove its soundness using our CHSH rigidity analysis.
  arXiv  Detail & Related papers  (2023-03-02T19:20:59Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Connecting XOR and XOR* games [0.0]
  We focus on two classes of games: XOR nonlocal games and XOR* sequential games with monopartite resources. We prove that under certain assumptions these two classes of games can be related via an explicit theorem that connects their optimal strategies.
  arXiv  Detail & Related papers  (2022-10-02T00:11:38Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Quantum Advantage from Any Non-Local Game [14.903809621145893]
  We show a general method of compiling any $k$-prover non-local game into a single-prover interactive game. Our compiler uses any quantum homomorphic encryption scheme.
  arXiv  Detail & Related papers  (2022-03-29T19:45:44Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time [0.0]
  We consider 3XOR games with perfect commuting operator strategies. We show existence of a perfect commuting operator strategy for the game can be decided in time.
  arXiv  Detail & Related papers  (2020-10-30T14:35:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.