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

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

URL: http://arxiv.org/abs/2402.17301v2
Date: Wed, 25 Sep 2024 14:39:03 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: 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.

Related papers

A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
arXiv Detail & Related papers (2024-08-13T08:11:56Z)
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)
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)

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