Quantum bounds for compiled XOR games and $d$-outcome CHSH games

• URL: http://arxiv.org/abs/2403.05502v2
• Date: Tue, 4 Jun 2024 15:51:27 GMT
• Title: Quantum bounds for compiled XOR games and $d$-outcome CHSH games
• Authors: Matilde Baroni, Quoc-Huy Vu, Boris Bourdoncle, Eleni Diamanti, Damian Markham, Ivan Šupić,
• Abstract summary: 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.
• Score: 1.099532646524593
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nonlocal games play a crucial role in quantum information theory and have numerous applications in certification and cryptographic protocols. Kalai et al. (STOC 2023) introduced a procedure to compile a nonlocal game into a single-prover interactive proof, using a quantum homomorphic encryption scheme, and showed that their compilation method preserves the classical bound of the game. Natarajan and Zhang (FOCS 2023) then showed that the quantum bound is preserved for the specific case of the CHSH game. Extending the proof techniques of Natarajan and Zhang, we show that the compilation procedure of Kalai et al. preserves the quantum bound for two classes of games: XOR games and d-outcome CHSH games. We also establish that, 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.

Related papers

• Cloning Games, Black Holes and Cryptography [53.93687166730726]
  This paper is the new, natural, notion of Haar cloning games together with two applications. In the area of black-hole physics, our game reveals that, in an idealized model of a black hole, the information from infalling entangled qubits can only be recovered from either the interior or the exterior. In the area of quantum cryptography, our game helps us construct succinct unclonable encryption schemes from the existence of pseudorandom unitaries.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Transfer of quantum game strategies [0.0]
  We show a new class of QNS correlations needed for the transfer of strategies between games. We define jointly tracial correlations and show they correspond to traces acting on tensor products of canonical $rm C*$-algebras associated with individual game parties.
  arXiv  Detail & Related papers  (2024-10-12T17:25:58Z)
• 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)
• A Computational Tsirelson's Theorem for the Value of Compiled XOR Games [9.818381970014284]
  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.
  arXiv  Detail & Related papers  (2024-02-27T08:24: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 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)
• Quantum guessing games with posterior information [68.8204255655161]
  A quantum guessing game with posterior information uses quantum systems to encode messages and classical communication to give partial information after a quantum measurement has been performed. We formalize symmetry of guessing games and characterize the optimal measurements in cases where the symmetry is related to an irreducible representation.
  arXiv  Detail & Related papers  (2021-07-25T19:10:26Z)

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.