Quantum Magic Rectangles: Characterization and Application to Certified Randomness Expansion

Abstract

We study a generalization of the Mermin-Peres magic square game to arbitrary rectangular dimensions. After exhibiting some general properties, these rectangular games are fully characterized in terms of their optimal win probabilities for quantum strategies. We find that for $m\times n$ rectangular games of dimensions $m,n\ge 3$ there are quantum strategies that win with certainty, while for dimensions $1\times n$ quantum strategies do not outperform classical strategies. The final case of dimensions $2\times n$ is richer, and we give upper and lower bounds that both outperform the classical strategies. Finally, we apply our findings to quantum certified randomness expansion to find the noise tolerance and rates for all magic rectangle games. To do this, we use our previous results to obtain the winning probability of games with a distinguished input for which the devices give a deterministic outcome, and follow the analysis of C. A. Miller and Y. Shi [SIAM J. Comput. 46, 1304 (2017)].

arXiv comment23 pages, 3 figures; published version with minor corrections

References in corpus (26)

• A Theory of Fault-Tolerant Quantum Computation
• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Bounding the set of quantum correlations
• Fully device independent quantum key distribution
• A limit on nonlocality in any world in which communication complexity is not trivial
• General properties of Nonsignaling Theories
• Self-testing of quantum systems: a review
• Private Randomness Expansion With Untrusted Devices
• Certified randomness in quantum physics
• Local orthogonality as a multipartite principle for quantum correlations
• Almost quantum correlations
• Quantum Pseudo-Telepathy
• Simple and tight device-independent security proofs
• "All versus nothing" inseparability for two observers
• Bell's theorem without inequalities and without probabilities for two observers
• Entropy accumulation
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Robustness and device independence of verifiable blind quantum computing
• Algorithm 950: Ncpol2sdpa---Sparse Semidefinite Programming Relaxations for Polynomial Optimization Problems of Noncommuting Variables
• Entropy accumulation with improved second-order term
• A framework for quantum-secure device-independent randomness expansion
• Multi-Party Pseudo-Telepathy
• Robust self-testing for linear constraint system games
• A device-independent protocol for XOR oblivious transfer
• Certifiable Quantum Dice - Or, testable exponential randomness expansion
• Extending and Characterizing Quantum Magic Games

Cited by in corpus (4)

• Experimental Demonstration of Quantum Pseudotelepathy
• Practical parallel self-testing of Bell states via magic rectangles
• Quantitative comparison of quantum pseudo-telepathy games and Bell inequalities
• Parallel remote state preparation for fully device-independent verifiable blind quantum computation