Haochen Xu

Motivated by the limitations of near-term quantum devices, we study nonlocal games in the highnoise regime, where the two players may share arbitrarily many copies of a noisy entangled state. In this regime, existing rigidity theorems are unable to certify any nontrivial quantum structure. We first characterize the maximal quantum winning probabilities of the CHSH game[CHSH69], the Magic Square game[Mer90a], and their 2-out-of-𝑛 variants [CRSV18] as explicit functions of the noise rate. These characterizations enable the construction of device-independent protocols for estimating the underlying noise level. Building on these results, we prove noise-robust rigidity theorems showing that these games ceritify one, two, and n pairs of anticommuting Pauli observables, respectively. To our knowledge, these are the first rigidity results of Pauli measurements that remain sound in the highnoise regime, which has applications in Measurement-Device-Independent (MDI) cryptography and studying the computational power of Multi-prover Interactive Proof System with entanglement and a vanishing completeness-soundness gap (MIP∗0). Our proofs rely on Sum-of-Squares decompositions and Pauli analysis techniques originating from quantum proof systems and quantum learning theory, respectively.