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
- Lossy-and-Constrained Extended Non-Local Games with Applications to Cryptography: BC, QKD and QPV [0.0]
We show that if one extends such games by considering constraints and loss, the convergence of the SDPs to the optimal value still holds.
We give applications of this result, and we compute SDPs that show tighter security of protocols for relativistic bit commitment, quantum key distribution, and quantum position verification.
arXiv Detail & Related papers (2024-05-22T15:09:30Z) - A Computational Tsirelson's Theorem for the Value of Compiled XOR Games [10.187610891144452]
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) - 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) - 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) - 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) - QUANTIFY: A framework for resource analysis and design verification of
quantum circuits [69.43216268165402]
QUANTIFY is an open-source framework for the quantitative analysis of quantum circuits.
It is based on Google Cirq and is developed with Clifford+T circuits in mind.
For benchmarking purposes QUANTIFY includes quantum memory and quantum arithmetic circuits.
arXiv Detail & Related papers (2020-07-21T15:36:25Z)
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.