Perfect parallel repetition theorem for quantum XOR proof systems
From MaRDI portal
Abstract: We consider a class of two-prover interactive proof systems where each prover returns a single bit to the verifier and the verifier's verdict is a function of the XOR of the two bits received. We show that, when the provers are allowed to coordinate their behavior using a shared entangled quantum state, a perfect parallel repetition theorem holds in the following sense. The prover's optimal success probability for simultaneously playing a collection of XOR proof systems is exactly the product of the individual optimal success probabilities. This property is remarkable in view of the fact that, in the classical case (where the provers can only utilize classical information), it does not hold. The theorem is proved by analyzing parities of XOR proof systems using semidefinite programming techniques, which we then relate to parallel repetitions of XOR games via Fourier analysis.
Recommendations
- Efficient quantum protocols for XOR functions
- A \(k\)-provers parallel repetition theorem for a version of no-signaling model
- A K-Provers Parallel Repetition Theorem for a Version of No-Signaling Model
- XOR of PRPs in a quantum world
- A proof system for disjoint parallel quantum programs
- Parallelization of entanglement-resistant multi-prover interactive proofs
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- Quantum algorithms for the \(k\)-XOR problem
- Quantum proof systems for iterated exponential time, and beyond
- An efficient parallel repetition theorem
Cited in
(20)- Parallel repetition and concentration for (sub-)no-signalling games via a flexible constrained de Finetti reduction
- Exponential quantum enhancement for distributed addition with local nonlinearity
- Parallel repetition of two-prover one-round games: an exposition
- Rank-one quantum games
- Lower bounds on the entanglement needed to play XOR non-local games
- Quantum XOR games
- Information value of two-prover games
- On decomposable correlation matrices
- A parallel repetition theorem for entangled projection games
- Extended nonlocal games from quantum-classical games
- A K-Provers Parallel Repetition Theorem for a Version of No-Signaling Model
- Synchronous values of games
- Anchored parallel repetition for nonlocal games
- A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
- Survey on nonlocal games and operator space theory
- Parallel Repetition of the Odd Cycle Game
- Large violation of Bell inequalities with low entanglement
- Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
- Linear conic formulations for two-party correlations and values of nonlocal games
- Optimal bounds for parity-oblivious random access codes
This page was built for publication: Perfect parallel repetition theorem for quantum XOR proof systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q937205)
