Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1709.09267

Robust self-testing for linear constraint system games

Andrea Coladangelo, Jalex Stark

Published Sep 26, 2017• 21 citations
arXivHTMLPDF

Abstract

We study linear constraint system (LCS) games over the ring of arithmetic modulo $d$. We give a new proof that certain LCS games (the Mermin--Peres Magic Square and Magic Pentagram over binary alphabets, together with parallel repetitions of these) have unique winning strategies, where the uniqueness is robust to small perturbations. In order to prove our result, we extend the representation-theoretic framework of Cleve, Liu, and Slofstra (Journal of Mathematical Physics 58.1 (2017): 012202.) to apply to linear constraint games over $\mathbb{Z}_d$ for $d\geq 2$. We package our main argument into machinery which applies to any nonabelian finite group with a ''solution group'' presentation. We equip the $n$-qubit Pauli group for $n\geq 2$ with such a presentation; our machinery produces the Magic Square and Pentagram games from the presentation and provides robust self-testing bounds. The question of whether there exist LCS games self-testing maximally entangled states of local dimension not a power of $2$ is left open. A previous version of this paper falsely claimed to show self-testing results for a certain generalization of the Magic Square and Pentagram mod $d\neq 2$. We show instead that such a result is impossible.

DOI
10.48550/arxiv.1709.09267

Related papers

A generalization of CHSH and the algebraic structure of optimal strategies

David Cui, Arthur Mehta, Hamoon Mousavi +1 more

Self-testing has been a rich area of study in quantum information theory. It allows an experimenter to interact classically with a black box quantum system and to test that a specific entangled state was present and a specific set of measurements were performed. Recently, self-testing has been central to high-profile results in complexity theory as seen in the work on entangled games PCP of Natarajan and Vidick (FOCS 2018), iterated compression by Fitzsimons et al.\ (STOC 2019), and NEEXP in MIP* due to Natarajan and Wright (FOCS 2019). The most studied self-test is the CHSH game which features a bipartite system with two isolated devices. This game certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. Most of the self-testing literature has focused on extending these results to self-test for tensor products of EPR states and tensor products of Pauli measurements.In this work, we introduce an algebraic generalization of CHSH by viewing it as a linear constraint system (LCS) game, exhibiting self-testing properties that are qualitatively different. These provide the first example of LCS games that self-test non-Pauli operators resolving an open question posed by Coladangelo and Stark (QIP 2017). Our games also provide a self-test for states other than the maximally entangled state, and hence resolves the open question posed by Cleve and Mittal (ICALP 2012). Additionally, our games have 1 bit question and log⁡n bit answer lengths making them suitable candidates for complexity theoretic application. This work is the first step towards a general theory of self-testing arbitrary groups. In order to obtain our results, we exploit connections between sum of squares proofs, non-commutative ring theory, and the Gowers-Hatami theorem from approximate representation theory. A crucial part of our analysis is to introduce a sum of squares framework that generalizes the solution group of Cleve, Liu, and Slofstra (Journal of Mathematical Physics 2017) to the non-pseudo-telepathic regime. Finally, we give a game that is not a self-test by "gluing" together two copies of the magic square game. Our results suggest a richer landscape of self-testing phenomena than previously considered.

arXiv:1911.01593•Quantum•Oct 21, 2020•11 citations

A complete classification of the existence of finite-dimensional quantum solutions to inconsistent linear constraint systems

Markus Frembs

Linear constraint systems (LCS) provide a compact algebraic language for nonlocal games and state-independent contextuality. In the binary case the Mermin--Peres square shows that inconsistent LCS can be solved by promoting variables to local Pauli operators, whereas a series of no-go results excludes analogous Pauli-, Clifford- and monomial unitary-based constructions at odd prime modulus. We first isolate the reason for this difference: for tensor-product quantum solutions, the obstruction to a classical solution of a LCS over $\mathbb{Z}_n$ decomposes into obstruction classes carried by the individual factors. As a consequence, a genuinely global obstruction cannot arise solely by tensoring locally unobstructed systems. The argument is specific to odd modulus; at even modulus the reordering phase need not vanish, as in Pauli-based examples. Given this distinction, we instead associate LCS to finite arrangements of rank-one projectors and resolutions of the identity in finite-dimensional vector spaces. Quantum solvability for such LCS is automatic and the search for a quantum-classical gap rests entirely on proving classical unsatisfiability of the underlying modular incidence problem of the arrangement. By relating such LCS with group-valued frame functions, we identify a family of examples in the work of [Harding, Jager, and Smith, Int. J. Theor. Phys. 44, 539 (2005)]. To establish the (non)existence of classically unsatisfiable LCS over $\mathbb{Z}_n$ with quantum solutions in all dimensions $d$ and for all $n\in\mathbb{N}$, we further construct explicit examples for the cases $d=n$ prime. Our main result thus positively resolves the existence problem of such LCS beyond the binary case: such systems exist if and only if $d\geq 3$ and $\gcd(n,d)>1$. Moreover, we establish the existence of LCS with a quantum-classical gap over finite fields if and only if $d\geq 3$ and $p\mid d$.

quant-pharXiv:2609.16490•Sep 16, 2026•0 citations

Robust self-testing for nonlocal games with robust game algebras

Yuming Zhao

We give an operator-algebraic formulation of robust self-testing in terms of states on C*-algebras. We show that a quantum correlation p is a robust self-test only if among all (abstract) states, there is a unique one achieving p. We show that the "if" direction of this statement also holds, provided that p is optimal/perfect for a nonlocal game that has a robust game algebra. This last condition applies to many nonlocal games of interest, including all XOR games, synchronous games, and boolean constrained system (BCS) games. For those nonlocal games with robust game algebras, we prove that self-testing is equivalent to the uniqueness of finite-dimensional tracial states on the associated game algebra, and robust self-testing is equivalent to the uniqueness of amenable tracial states. Applying this tracial-state characterization of self-testing to parallel repetition, we show that a synchronous game is a self-test for perfect quantum strategies if and only if its parallel repeated version is a self-test for perfect quantum strategies. As a proof approach, we give the first quantitative Gower-Hatami theorem that is applicable to C*-algebras. Here "quantitative" means there is a constructive bound on the distance between the approximate representations and exact representations. We also demonstrate how this quantitative Gowers-Hatami theorem can be used to calculate the explicit robustness function of a self-test.

arXiv:2411.03259•Nov 5, 2024•0 citations

Classical vs quantum satisfiability in linear constraint systems modulo an integer

Hammam Qassim, Joel J. Wallman

Abstract A system of linear constraints can be unsatisfiable and yet admit a solution in the form of quantum observables whose correlated outcomes satisfy the constraints. Recently, it has been claimed that such a satisfiability gap can be demonstrated using tensor products of generalized Pauli observables in odd dimensions. We provide an explicit proof that no quantum-classical satisfiability gap in any linear constraint system can be achieved using these observables. We prove a few other results for linear constraint systems modulo d > 2. We show that a characterization of the existence of quantum solutions when d is prime, due to Cleve et al , holds with a small modification for arbitrary d . We identify a key property of some linear constraint systems, called phase-commutation, and give a no-go theorem for the existence of quantum solutions to constraint systems for odd d whenever phase-commutation is present. As a consequence, all natural generalizations of the Peres–Mermin magic square and pentagram to odd prime d do not exhibit a satisfiability gap.

arXiv:1911.11171•Journal of Physics A Mathematical and Theoretical•Jul 6, 2020•3 citations

Glued magic games self-test maximally entangled states

Laura Mančinska, Thor Gabelgaard Nielsen, Jitendra Prakash

Self-testing results allow us to infer the underlying quantum mechanical description of states and measurements from classical outputs produced by non-communicating parties. The standard definition of self-testing does not apply in situations when there are two or more inequivalent optimal strategies. To address this, we introduce the notion of self-testing convex combinations of reference strategies, which is a generalisation of self-testing to multiple strategies. We show that the Glued Magic Square game [Quantum 4 (2020), p. 346] self-tests a convex combination of two inequivalent strategies. As a corollary, we obtain that the Glued Magic square game self-tests two EPR pairs thus answering an open question from [Quantum 4 (2020), p. 346]. Our self-test is robust and extends to natural generalisations of the Glued Magic Square game.

arXiv:2105.10658•May 22, 2021•3 citations

Robust Self-testing for Synchronous Correlations and Games

Prem Nigam Kar

We develop an abstract operator-algebraic characterization of robust self-testing for synchronous correlations and games. Specifically, we show that a synchronous correlation is a robust self-test if and only if there is a unique state on an appropriate $C^*$-algebra that "implements" the correlation. Extending this result, we prove that a synchronous game is a robust self-test if and only if its associated $C^*$-algebra admits a unique amenable tracial state. This framework allows us to establish that all synchronous correlations and games that serve as commuting operator self-tests for finite-dimensional strategies are also robust self-tests. As an application, we recover sufficient conditions for linear constraint system games to exhibit robust self-testing. We also demonstrate the existence of a synchronous nonlocal game that is a robust self-test but not a commuting operator self-test, showing that these notions are not equivalent.

arXiv:2503.23500•Mar 30, 2025•0 citations
We study linear constraint system (LCS) games over the ring of arithmetic modulo ddd. We give a new proof that certain LCS games (the Mermin--Peres Magic Square and Magic Pentagram over binary alphabets, together with parallel repetitions of these) have unique winning strategies, where the uniqueness is robust to small perturbations. In order to prove our result, we extend the representation-theoretic framework of Cleve, Liu, and Slofstra (Journal of Mathematical Physics 58.1 (2017): 012202.) to apply to linear constraint games over Zd\mathbb{Z}_dZd​ for d≥2d\geq 2d≥2. We package our main argument into machinery which applies to any nonabelian finite group with a ''solution group'' presentation. We equip the nnn-qubit Pauli group for n≥2n\geq 2n≥2 with such a presentation; our machinery produces the Magic Square and Pentagram games from the presentation and provides robust self-testing bounds. The question of whether there exist LCS games self-testing maximally entangled states of local dimension not a power of 222 is left open. A previous version of this paper falsely claimed to show self-testing results for a certain generalization of the Magic Square and Pentagram mod d≠2d\neq 2d=2. We show instead that such a result is impossible.
Self-testing has been a rich area of study in quantum information theory. It allows an experimenter to interact classically with a black box quantum system and to test that a specific entangled state was present and a specific set of measurements were performed. Recently, self-testing has been central to high-profile results in complexity theory as seen in the work on entangled games PCP of Natarajan and Vidick (FOCS 2018), iterated compression by Fitzsimons et al.\ (STOC 2019), and NEEXP in MIP* due to Natarajan and Wright (FOCS 2019). The most studied self-test is the CHSH game which features a bipartite system with two isolated devices. This game certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. Most of the self-testing literature has focused on extending these results to self-test for tensor products of EPR states and tensor products of Pauli measurements.In this work, we introduce an algebraic generalization of CHSH by viewing it as a linear constraint system (LCS) game, exhibiting self-testing properties that are qualitatively different. These provide the first example of LCS games that self-test non-Pauli operators resolving an open question posed by Coladangelo and Stark (QIP 2017). Our games also provide a self-test for states other than the maximally entangled state, and hence resolves the open question posed by Cleve and Mittal (ICALP 2012). Additionally, our games have 1 bit question and log⁡n bit answer lengths making them suitable candidates for complexity theoretic application. This work is the first step towards a general theory of self-testing arbitrary groups. In order to obtain our results, we exploit connections between sum of squares proofs, non-commutative ring theory, and the Gowers-Hatami theorem from approximate representation theory. A crucial part of our analysis is to introduce a sum of squares framework that generalizes the solution group of Cleve, Liu, and Slofstra (Journal of Mathematical Physics 2017) to the non-pseudo-telepathic regime. Finally, we give a game that is not a self-test by "gluing" together two copies of the magic square game. Our results suggest a richer landscape of self-testing phenomena than previously considered.
Linear constraint systems (LCS) provide a compact algebraic language for nonlocal games and state-independent contextuality. In the binary case the Mermin--Peres square shows that inconsistent LCS can be solved by promoting variables to local Pauli operators, whereas a series of no-go results excludes analogous Pauli-, Clifford- and monomial unitary-based constructions at odd prime modulus. We first isolate the reason for this difference: for tensor-product quantum solutions, the obstruction to a classical solution of a LCS over Zn\mathbb{Z}_nZn​ decomposes into obstruction classes carried by the individual factors. As a consequence, a genuinely global obstruction cannot arise solely by tensoring locally unobstructed systems. The argument is specific to odd modulus; at even modulus the reordering phase need not vanish, as in Pauli-based examples. Given this distinction, we instead associate LCS to finite arrangements of rank-one projectors and resolutions of the identity in finite-dimensional vector spaces. Quantum solvability for such LCS is automatic and the search for a quantum-classical gap rests entirely on proving classical unsatisfiability of the underlying modular incidence problem of the arrangement. By relating such LCS with group-valued frame functions, we identify a family of examples in the work of [Harding, Jager, and Smith, Int. J. Theor. Phys. 44, 539 (2005)]. To establish the (non)existence of classically unsatisfiable LCS over Zn\mathbb{Z}_nZn​ with quantum solutions in all dimensions ddd and for all n∈Nn\in\mathbb{N}n∈N, we further construct explicit examples for the cases d=nd=nd=n prime. Our main result thus positively resolves the existence problem of such LCS beyond the binary case: such systems exist if and only if d≥3d\geq 3d≥3 and gcd⁡(n,d)>1\gcd(n,d)>1gcd(n,d)>1. Moreover, we establish the existence of LCS with a quantum-classical gap over finite fields if and only if d≥3d\geq 3d≥3 and p∣dp\mid dp∣d.
We give an operator-algebraic formulation of robust self-testing in terms of states on C*-algebras. We show that a quantum correlation p is a robust self-test only if among all (abstract) states, there is a unique one achieving p. We show that the "if" direction of this statement also holds, provided that p is optimal/perfect for a nonlocal game that has a robust game algebra. This last condition applies to many nonlocal games of interest, including all XOR games, synchronous games, and boolean constrained system (BCS) games. For those nonlocal games with robust game algebras, we prove that self-testing is equivalent to the uniqueness of finite-dimensional tracial states on the associated game algebra, and robust self-testing is equivalent to the uniqueness of amenable tracial states. Applying this tracial-state characterization of self-testing to parallel repetition, we show that a synchronous game is a self-test for perfect quantum strategies if and only if its parallel repeated version is a self-test for perfect quantum strategies. As a proof approach, we give the first quantitative Gower-Hatami theorem that is applicable to C*-algebras. Here "quantitative" means there is a constructive bound on the distance between the approximate representations and exact representations. We also demonstrate how this quantitative Gowers-Hatami theorem can be used to calculate the explicit robustness function of a self-test.
Abstract A system of linear constraints can be unsatisfiable and yet admit a solution in the form of quantum observables whose correlated outcomes satisfy the constraints. Recently, it has been claimed that such a satisfiability gap can be demonstrated using tensor products of generalized Pauli observables in odd dimensions. We provide an explicit proof that no quantum-classical satisfiability gap in any linear constraint system can be achieved using these observables. We prove a few other results for linear constraint systems modulo d > 2. We show that a characterization of the existence of quantum solutions when d is prime, due to Cleve et al , holds with a small modification for arbitrary d . We identify a key property of some linear constraint systems, called phase-commutation, and give a no-go theorem for the existence of quantum solutions to constraint systems for odd d whenever phase-commutation is present. As a consequence, all natural generalizations of the Peres–Mermin magic square and pentagram to odd prime d do not exhibit a satisfiability gap.
Self-testing results allow us to infer the underlying quantum mechanical description of states and measurements from classical outputs produced by non-communicating parties. The standard definition of self-testing does not apply in situations when there are two or more inequivalent optimal strategies. To address this, we introduce the notion of self-testing convex combinations of reference strategies, which is a generalisation of self-testing to multiple strategies. We show that the Glued Magic Square game [Quantum 4 (2020), p. 346] self-tests a convex combination of two inequivalent strategies. As a corollary, we obtain that the Glued Magic square game self-tests two EPR pairs thus answering an open question from [Quantum 4 (2020), p. 346]. Our self-test is robust and extends to natural generalisations of the Glued Magic Square game.
We develop an abstract operator-algebraic characterization of robust self-testing for synchronous correlations and games. Specifically, we show that a synchronous correlation is a robust self-test if and only if there is a unique state on an appropriate C∗C^*C∗-algebra that "implements" the correlation. Extending this result, we prove that a synchronous game is a robust self-test if and only if its associated C∗C^*C∗-algebra admits a unique amenable tracial state. This framework allows us to establish that all synchronous correlations and games that serve as commuting operator self-tests for finite-dimensional strategies are also robust self-tests. As an application, we recover sufficient conditions for linear constraint system games to exhibit robust self-testing. We also demonstrate the existence of a synchronous nonlocal game that is a robust self-test but not a commuting operator self-test, showing that these notions are not equivalent.