Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911606827384832 |
|---|---|
| author | Fu, Honghao Qin, Minglong Xu, Haochen Yao, Penghui |
| author_facet | Fu, Honghao Qin, Minglong Xu, Haochen Yao, Penghui |
| contents | Motivated by the limitations of near-term quantum devices, we study nonlocal games in the high-noise 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 [Clauser et al. '69], the Magic Square game [Mermin '90], and their 2-out-of-n variants [Chao et al. '18] 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 certify 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 high-noise 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 ($\text{MIP}^*_0$). Our proofs rely on Sum-of-Squares decompositions and Pauli analysis techniques originating from quantum proof systems and quantum learning theory, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20350 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity Fu, Honghao Qin, Minglong Xu, Haochen Yao, Penghui Quantum Physics Computational Complexity Motivated by the limitations of near-term quantum devices, we study nonlocal games in the high-noise 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 [Clauser et al. '69], the Magic Square game [Mermin '90], and their 2-out-of-n variants [Chao et al. '18] 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 certify 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 high-noise 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 ($\text{MIP}^*_0$). Our proofs rely on Sum-of-Squares decompositions and Pauli analysis techniques originating from quantum proof systems and quantum learning theory, respectively. |
| title | Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2509.20350 |