pith. sign in

arxiv: 2509.20350 · v2 · submitted 2025-09-24 · 🪐 quant-ph · cs.CC

Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity

Honghao Fu , Minglong Qin , Haochen Xu , Penghui Yao This is my paper

Pith reviewed 2026-05-18 14:14 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords nonlocal gamesquantum rigidityCHSH gameMagic Square gamehigh-noise regimePauli observablesdevice-independent protocols
0
0 comments X

The pith

CHSH, Magic Square and 2-out-of-n games certify anticommuting Pauli observables even when the shared state is highly noisy.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives explicit formulas for the highest quantum winning probability of the CHSH game, the Magic Square game, and their 2-out-of-n variants when the players share arbitrarily many independent copies of a noisy entangled state whose noise is controlled by one rate parameter. These formulas are obtained via Sum-of-Squares decompositions and Pauli analysis. The same characterizations are then used to prove that any strategy achieving the optimal score must implement one, two or n pairs of anticommuting Pauli observables, respectively. The resulting rigidity statements remain valid in the high-noise regime, which was previously inaccessible to existing rigidity theorems. The results directly support device-independent noise estimation and protocols in measurement-device-independent cryptography.

Core claim

The maximal quantum winning probabilities of the CHSH, Magic Square and 2-out-of-n games are explicit functions of the single noise rate that parameterizes the product of independent noisy entangled states. Any strategy attaining these maximal values must measure one, two or n pairs of anticommuting Pauli observables respectively, and this correspondence remains sound even when the noise rate is large.

What carries the argument

Explicit maximal winning probability expressed as a function of the noise rate, which is then used to establish noise-robust rigidity for Pauli observables via Sum-of-Squares and Pauli analysis.

If this is right

  • Device-independent protocols become possible for estimating the noise rate from the observed winning probability.
  • The rigidity results supply sound certification of Pauli observables for use in measurement-device-independent cryptography.
  • The same characterizations bound the computational power of multi-prover interactive proofs with entanglement when the completeness-soundness gap vanishes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The product-state noise model may be relaxed to more general channels while preserving the rigidity statements if similar Sum-of-Squares certificates can be found.
  • The explicit formulas offer a practical route to calibrate the effective noise rate in near-term quantum devices without trusting the measurement apparatus.
  • The combination of Sum-of-Squares and Pauli analysis may extend to other families of nonlocal games that have so far lacked high-noise rigidity results.

Load-bearing premise

The shared resource is modeled as arbitrarily many independent copies of one fixed noisy entangled state whose noise enters the winning-probability expressions through a single rate parameter.

What would settle it

An experiment in which the observed winning probability for a given noise rate exceeds the paper's explicit upper bound, or reaches the bound with a strategy that does not implement the claimed anticommuting Pauli measurements.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript studies nonlocal games in the high-noise regime, where the players may share arbitrarily many copies of a fixed noisy entangled state parameterized by a single noise rate. It derives explicit characterizations of the maximal quantum winning probabilities for the CHSH game, the Magic Square game, and the 2-out-of-n variants as functions of this noise rate. These characterizations are then used to prove noise-robust rigidity theorems certifying one, two, and n pairs of anticommuting Pauli observables, respectively. The proofs rely on Sum-of-Squares decompositions for the value upper bounds and Pauli-analysis techniques for extracting the rigidity statements.

Significance. If the characterizations and rigidity results hold under the stated product-noise model, the work provides the first explicit noise-robust rigidity theorems for Pauli observables that remain valid in the high-noise regime. This is a meaningful advance for near-term devices, enabling device-independent noise estimation protocols and supporting applications in MDI cryptography and the analysis of MIP* with vanishing completeness-soundness gap. The matching of SOS upper bounds to the explicit lower bounds achieved by Pauli measurements on the noisy product state, together with uniform control of error terms across copy number, constitutes a verifiable strength of the approach.

major comments (2)
  1. [§4] §4 (rigidity theorems): the claim that the error bounds in the certification of anticommuting Pauli pairs remain uniform in the number of copies is central to the high-noise robustness; the manuscript should explicitly display the dependence (or independence) of the additive error term on the copy number n in the final rigidity statements for the CHSH and Magic Square cases.
  2. [§3.2] §3.2 (CHSH characterization): the explicit functional form of the optimal quantum value as a function of the noise rate is load-bearing for both the device-independent estimation protocol and the subsequent rigidity; the SOS decomposition establishing the matching upper bound should be stated with the precise monomial basis and the resulting quadratic form to allow direct verification that no post-hoc parameter adjustment occurs.
minor comments (3)
  1. [Introduction] The abstract and introduction should include a brief comparison table or sentence contrasting the new high-noise rigidity statements with existing low-noise rigidity results (e.g., those based on the original CHSH or Magic Square analyses) to clarify the precise novelty.
  2. Notation for the noise rate and the explicit form of the noisy state (product of identical two-qubit channels) should be fixed consistently across sections; a single displayed equation defining the channel would improve readability.
  3. Figure captions for any plots of winning probability versus noise rate should state the classical bound and the derived quantum curve explicitly so that the gap above the classical value is immediately visible.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment, and constructive suggestions. We address each major comment below and will incorporate the requested clarifications into the revised manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (rigidity theorems): the claim that the error bounds in the certification of anticommuting Pauli pairs remain uniform in the number of copies is central to the high-noise robustness; the manuscript should explicitly display the dependence (or independence) of the additive error term on the copy number n in the final rigidity statements for the CHSH and Magic Square cases.

    Authors: We agree that explicit display of the error-term dependence strengthens the presentation of the high-noise robustness. The additive error terms in the rigidity statements (Theorems 4.1 and 4.2) are independent of the copy number n; this follows from the uniform control obtained via the product structure of the noisy state and the Pauli-analysis bounds that do not accumulate with additional copies. In the revised manuscript we will add a dedicated remark immediately after each theorem statement that explicitly records the independence of the additive error on n and displays its precise functional dependence on the noise rate alone. revision: yes

  2. Referee: [§3.2] §3.2 (CHSH characterization): the explicit functional form of the optimal quantum value as a function of the noise rate is load-bearing for both the device-independent estimation protocol and the subsequent rigidity; the SOS decomposition establishing the matching upper bound should be stated with the precise monomial basis and the resulting quadratic form to allow direct verification that no post-hoc parameter adjustment occurs.

    Authors: We agree that spelling out the SOS certificate improves verifiability. The upper bound in §3.2 is obtained from a degree-2 Sum-of-Squares decomposition whose monomial basis consists of the constant term together with the four single-observable monomials and the two anticommutator monomials; the resulting quadratic form is a 6×6 positive-semidefinite matrix whose entries are explicit rational functions of the noise rate. In the revision we will insert this basis and the explicit quadratic form (or the corresponding SDP matrix) as a short displayed equation or remark in §3.2, confirming that all coefficients are derived directly from the SOS solver output without subsequent tuning. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central results characterize maximal quantum winning probabilities for the CHSH, Magic Square, and 2-out-of-n games explicitly as functions of a single noise rate, then use these to prove noise-robust rigidity for one, two, or n pairs of anticommuting Pauli observables. These characterizations are obtained via Sum-of-Squares decompositions that upper-bound the value and match the lower bounds achieved by measuring the appropriate Paulis on the noisy product state; the rigidity statements control error terms uniformly in the number of copies while keeping the gap above the classical value explicit. The proofs rely on standard SOS and Pauli-analysis techniques from quantum proof systems and quantum learning theory, with no reduction of final expressions to internally fitted parameters, no load-bearing self-citations, and no ansatz or uniqueness imported from the authors' prior work. The derivation remains self-contained against external benchmarks such as classical game values and known rigidity results outside the high-noise regime.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on standard mathematical background (SOS hierarchies, representation theory of Pauli operators) and the modeling assumption that the shared state is a product of identical noisy copies; no new free parameters, ad-hoc axioms, or invented entities are introduced beyond the noise rate treated as an external input.

axioms (2)
  • standard math Sum-of-Squares decompositions exist for the relevant game operators and yield tight bounds on the quantum value.
    Invoked to obtain the explicit winning-probability formulas; standard technique in quantum proof systems.
  • domain assumption The shared resource is an arbitrary number of independent copies of a fixed noisy entangled state.
    Central modeling choice stated in the abstract that defines the high-noise regime.

pith-pipeline@v0.9.0 · 5762 in / 1473 out tokens · 36352 ms · 2026-05-18T14:14:11.197895+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · 2 internal anchors

  1. [1]

    Device-independent certification of one-shot distillable entanglement

    Rotem Arnon-Friedman and Jean-Daniel Bancal. Device-independent certification of one-shot distillable entanglement. New Journal of Physics , 21(3):033010, 2019

    work page 2019

  2. [2]

    Noise-Tolerant Testing of High Entanglement of Formation

    Rotem Arnon-Friedman and Henry Yuen. Noise-Tolerant Testing of High Entanglement of Formation . In Ioannis Chatzigiannakis, Christos Kaklamanis, D\' a niel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) , volume 107 of Leibniz International Proceedings in Informatics (LIPIcs) , pages ...

    work page 2018

  3. [3]

    Quantum mysteries revisited again

    Padmanabhan K Aravind. Quantum mysteries revisited again. American Journal of Physics , 72(10):1303--1307, 2004

    work page 2004

  4. [4]

    A new quantum data processing inequality

    Salman Beigi. A new quantum data processing inequality. Journal of Mathematical Physics , 54(8):082202, 2013

    work page 2013

  5. [5]

    On the Einstein Podolsky Rosen paradox

    John S Bell. On the Einstein Podolsky Rosen paradox. Physics Physique Fizika , 1(3):195, 1964

    work page 1964

  6. [6]

    Positive Definite Matrices

    Rajendra Bhatia. Positive Definite Matrices . Princeton University Press, 2007

    work page 2007

  7. [7]

    Proposed experiment to test local hidden-variable theories

    John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt. Proposed experiment to test local hidden-variable theories. Physical review letters , 23(15):880, 1969

    work page 1969

  8. [8]

    QIC 890 entanglement and nonlocal effects lecture notes

    Richard Cleve. QIC 890 entanglement and nonlocal effects lecture notes. May , 1:57, 2020

    work page 2020

  9. [9]

    All real projective measurements can be self-tested

    Ranyiliu Chen, Laura Man c inska, and Jurij Vol c i c . All real projective measurements can be self-tested. Nature Physics , 20(10):1642--1647, 2024

    work page 2024

  10. [10]

    Test for a large amount of entanglement, using few measurements

    Rui Chao, Ben W Reichardt, Chris Sutherland, and Thomas Vidick. Test for a large amount of entanglement, using few measurements. Quantum , 2:92, 2018

    work page 2018

  11. [11]

    The Computational Advantage of MIP ^* Vanishes in the Presence of Noise

    Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, and Penghui Yao. The Computational Advantage of MIP ^* Vanishes in the Presence of Noise . In Rahul Santhanam, editor, 39th Computational Complexity Conference (CCC 2024) , volume 300 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 30:1--30:71, Dagstuhl, Germany, 20...

    work page 2024

  12. [12]

    Bounding the persistency of the nonlocality of W states

    P \'e ter Divi \'a nszky, R \'e ka Trencs \'e nyi, Erika Bene, and Tam \'a s V \'e rtesi. Bounding the persistency of the nonlocality of W states. Physical Review A , 93(4):042113, 2016

    work page 2016

  13. [13]

    The membership problem for constant-sized quantum correlations is undecidable

    Honghao Fu, Carl A Miller, and William Slofstra. The membership problem for constant-sized quantum correlations is undecidable. Communications in Mathematical Physics , 406(5):96, 2025

    work page 2025

  14. [14]

    Constant-sized correlations are sufficient to self-test maximally entangled states with unbounded dimension

    Honghao Fu. Constant-sized correlations are sufficient to self-test maximally entangled states with unbounded dimension. Quantum , 6:614, 2022

    work page 2022

  15. [15]

    Violating Bell inequality by mixed spin-12 states: necessary and sufficient condition

    Ryszard Horodecki, Pawel Horodecki, and Michal Horodecki. Violating Bell inequality by mixed spin-12 states: necessary and sufficient condition. Physics Letters A , 200(5):340--344, 1995

    work page 1995

  16. [16]

    MIP*= RE.arXiv preprint arXiv:2001.04383,

    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP^*=RE . arXiv preprint arXiv:2001.04383 , 2020

    work page arXiv 2001

  17. [17]

    Quantum soundness of the classical low individual degree test

    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Quantum soundness of the classical low individual degree test. arXiv preprint arXiv:2009.12982 , 2020

    work page arXiv 2009

  18. [18]

    Analytic and nearly optimal self-testing bounds for the Clauser-Horne-Shimony-Holt and Mermin inequalities

    J e drzej Kaniewski. Analytic and nearly optimal self-testing bounds for the Clauser-Horne-Shimony-Holt and Mermin inequalities. Physical review letters , 117(7):070402, 2016

    work page 2016

  19. [19]

    Noise-robust self-testing: Detecting non-locality in noisy non-local inputs

    Romi Lifshitz. Noise-robust self-testing: Detecting non-locality in noisy non-local inputs. arXiv preprint arXiv:2505.13537 , 2025

    work page arXiv 2025

  20. [20]

    Highly noise resistant multipartite quantum correlations

    Wieslaw Laskowski, Tamas Vertesi, and Marcin Wiesniak. Highly noise resistant multipartite quantum correlations. arXiv preprint arXiv:1412.8745 , 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  21. [21]

    Quantum mysteries revisited

    N David Mermin. Quantum mysteries revisited. Am. J. Phys , 58(8):731--734, 1990

    work page 1990

  22. [22]

    Simple unified form for the major no-hidden-variables theorems

    N David Mermin. Simple unified form for the major no-hidden-variables theorems. Physical review letters , 65(27):3373, 1990

    work page 1990

  23. [23]

    Nonlocal games, compression theorems, and the arithmetical hierarchy

    Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen. Nonlocal games, compression theorems, and the arithmetical hierarchy. In Proceedings of the 54th annual ACM SIGACT symposium on theory of computing , pages 1--11, 2022

    work page 2022

  24. [24]

    Ashley Montanaro and Tobias J. Osborne. Quantum B oolean functions. Chicago Journal of Theoretical Computer Science , 2010(1), January 2010

    work page 2010

  25. [25]

    Constant-sized robust self-tests for states and measurements of unbounded dimension

    Laura Man c inska, Jitendra Prakash, and Christopher Schafhauser. Constant-sized robust self-tests for states and measurements of unbounded dimension. Communications in Mathematical Physics , 405(9):221, 2024

    work page 2024

  26. [26]

    Influence of noise in entanglement-based quantum networks

    Maria Flors Mor-Ruiz and Wolfgang D\" u r. Influence of noise in entanglement-based quantum networks. IEEE J.Sel. A. Commun. , 42(7):1793–1807, July 2024

    work page 2024

  27. [27]

    Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices

    Carl A Miller and Yaoyun Shi. Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices. Journal of the ACM (JACM) , 63(4):1--63, 2016

    work page 2016

  28. [28]

    Self testing quantum apparatus

    Dominic Mayers and Andrew Yao. Self testing quantum apparatus. Quant. Inf. Comput. , 4(arXiv: quant-ph/0307205):273--286, 2004

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  29. [29]

    Robust self-testing of the singlet

    Matthew McKague, Tzyh Haur Yang, and Valerio Scarani. Robust self-testing of the singlet. Journal of Physics A: Mathematical and Theoretical , 45(45):455304, 2012

    work page 2012

  30. [30]

    On the pauli spectrum of qac0

    Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. On the pauli spectrum of qac0. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 1498–1506, New York, NY, USA, 2024. Association for Computing Machinery

    work page 2024

  31. [31]

    A quantum linearity test for robustly verifying entanglement

    Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying entanglement. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 1003--1015, 2017

    work page 2017

  32. [32]

    NEEXP is C ontained in MIP^*

    Anand Natarajan and John Wright. NEEXP is C ontained in MIP^* . In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science , FOCS 2019, pages 510--518. IEEE, 2019

    work page 2019

  33. [33]

    Incompatible results of quantum measurements

    Asher Peres. Incompatible results of quantum measurements. Physics Letters A , 151(3-4):107--108, 1990

    work page 1990

  34. [34]

    Nonlocal games with noisy maximally entangled states are decidable

    Minglong Qin and Penghui Yao. Nonlocal games with noisy maximally entangled states are decidable. SIAM Journal on Computing , 50(6):1800--1891, 2021

    work page 2021

  35. [35]

    Decoherence effects on the nonlocality of symmetric states

    Adel Sohbi, Isabelle Zaquine, Eleni Diamanti, and Damian Markham. Decoherence effects on the nonlocality of symmetric states. Physical Review A , 91(2):022101, 2015

    work page 2015

  36. [36]

    Tsirel'son

    Boris S. Tsirel'son. Quantum analogues of the Bell inequalities. The case of two spatially separated domains . Journal of Soviet mathematics , 36:557--570, 1987

    work page 1987

  37. [37]

    Fully device independent quantum key distribution

    Umesh Vazirani and Thomas Vidick. Fully device independent quantum key distribution. Communications of the ACM , 62(4):133--133, 2019

    work page 2019

  38. [38]

    Device-independent parallel self-testing of two singlets

    Xingyao Wu, Jean-Daniel Bancal, Matthew McKague, and Valerio Scarani. Device-independent parallel self-testing of two singlets. Physical Review A , 93(6):062121, 2016

    work page 2016

  39. [39]

    Symmetrized persistency of Bell correlations for Dicke states and GHZ-based mixtures

    Marcin Wie \'s niak. Symmetrized persistency of Bell correlations for Dicke states and GHZ-based mixtures . Scientific Reports , 11(1):14333, 2021

    work page 2021