Quantum Magic Rectangles: Characterization and Application to Certified Randomness Expansion
This work advances quantum information theory by providing a full characterization of magic rectangle games, with applications to improving randomness expansion protocols, though it is incremental as it builds on prior game generalizations and analysis methods.
The authors generalized the Mermin-Peres magic square game to arbitrary rectangular dimensions, characterizing optimal quantum win probabilities and finding that quantum strategies win with certainty for dimensions m,n ≥ 3, while for 2 × n games, they outperform classical strategies with bounds. They applied these results to quantum certified randomness expansion to determine noise tolerance and rates for all such games.
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 \geq 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)].