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:1911.01593 · Quantum

A generalization of CHSH and the algebraic structure of optimal strategies

David Cui, Arthur Mehta, Hamoon Mousavi, Seyed Sajjad Nezhadi

Published Oct 21, 2020• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2020-10-21-346

Related papers

Entanglement and Non-locality in Games and Graphs

Arthur Mehta

Quantum graph theory, also known as non-commutative graph theory, is an operator space generalization of graph theory. The independence number, and Lovasz theta function were generalized to this setting by Duan, Severini, and Winter [DSW13] and two different version of the chromatic number were introduced by Stahlke [Sta16] and Paulsen [HPP16]. We introduce two new generalizations of the chromatic number to non-commutative graphs and provide an upper bound on the parameter of Stahlke. We provide a generalization of the graph complement and show the chromatic number of the orthogonal complement of a non-commutative graph is bounded below by its theta number. We also provide a generalization of both Sabidussi's Theorem and Hedetniemi's conjecture to non-commutative graphs. The study of non-local games considers scenarios in which separated players collaborate to provide satisfying responses to questions given by a referee. The condition of separating players makes non-local games an excellent setting to gain insight into quantum phenomena such as entanglement and non-locality. Non-local games can also provide protocols known as self-tests. Self-testing allows an experimenter to interact classically with a black box quantum system and certify that a specific entangled state was present and a specific set of measurements were performed. The most studied self-test is the CHSH game which certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. We introduce an algebraic generalization of CHSH and obtain a self-test for 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). This thesis is primarily based on two collaborative works written by the author and several coauthors [CMMN20], [KM19].

•Jun 1, 2021•0 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 linear constraint system games

Andrea Coladangelo, Jalex Stark

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.

arXiv:1709.09267•Sep 26, 2017•21 citations

Self-testing high dimensional states using the generalized magic square game

Matthew McKague

To date all self-tests for high dimensional systems are confined to many-qubit states. This is due to two restrictions in the literature: the standard techniques for proving self-testing results apply only to qubits, and there are few suitable non-local games that are known to require high dimensional non-qubit states to achieve their optimal quantum value. In this paper we address these two problems. Specifically, we generalize the usual self-testing framework to q$d$its and then apply it to a generalization of the magic square game, giving a self-test for two maximally entangled pairs of q$d$its. This self-test has two parties, perfect completeness for honest quantum players, and requires only a constant number of measurement settings, regardless of the dimension $d$.

arXiv:1605.09435•May 30, 2016•4 citations

Toward correlation self-testing of quantum theory in the adaptive Clauser-Horne-Shimony-Holt game

Mirjam Weilenmann, Roger Colbeck

Correlation self-testing of a theory addresses the question of whether we can identify the set of correlations realizable in a theory from its performance in a particular information processing task. Applied to quantum theory it aims to identify an information processing task whose optimal performance is achieved only by theories realizing the same correlations as quantum theory in any causal structure. In M. Weilenmann and R. Colbeck [Phys. Rev. Lett. 125, 060406 (2020)], we introduce a candidate task for this---the adaptive Clauser-Horne-Shimony-Holt (CHSH) game. Here, we analyze the maximum probability of winning this game in different generalized probabilistic theories. We show that theories with a joint state space given by the minimal or the maximal tensor product are inferior to quantum theory, before considering other tensor products in theories whose elementary systems have various two-dimensional state spaces. For these, we find no theories that outperform quantum theory in the adaptive CHSH game and prove that it is impossible to recover the quantum performance in various cases. This is the first step towards a general solution that, if successful, will have wide-ranging consequences, in particular, enabling an experiment that could rule out all theories in which the set of realizable correlations does not coincide with the quantum set.

arXiv:2009.05069•Physical Review A•Aug 6, 2020•9 citations

The quantum commuting model (Ia): The CHSH game and other examples: Uniqueness of optimal states

Alexander Frei

We present in this paper that the CHSH game admits one and only one optimal state and so remove all ambiguity of representations. More precisely, we use the well-known universal description of quantum commuting correlations as state space on the universal algebra for two player games, and so allows us to unambigiously compare quantum strategies as states on this common algebra. As such we find that the CHSH game leaves a single optimal state on this common algebra. In turn passing to any non-minimal Stinespring dilation for this unique optimal state is the only source of ambiguity (including self-testing): More precisely, any state on some operator algebra may be uniquely broken up into its minimal Stinespring dilation as an honest representation for the operator algebra followed by its vector state. Any other Stinespring dilation however arises simply as an extension of the minimal Stinespring dilation (i.e., as an embedding of the minimal Hilbert space into some random ambient one). As such this manifests the only source of ambiguity appearing in most (but not all!) traditional self-testing results such as for the CHSH game as well as in plenty of similar examples. We then further demonstrate the simplicity of our arguments on the Mermin--Peres magic square and magic pentagram game. Most importantly however, we present this article as an illustration of operator algebraic techniques on optimal states and their quotients, and we further pick up the results of the current article in another following one (currently under preparation) to derive a first robust self-testing result in the quantum commuting model.

arXiv:2210.03716•Oct 7, 2022•0 citations
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.
Quantum graph theory, also known as non-commutative graph theory, is an operator space generalization of graph theory. The independence number, and Lovasz theta function were generalized to this setting by Duan, Severini, and Winter [DSW13] and two different version of the chromatic number were introduced by Stahlke [Sta16] and Paulsen [HPP16]. We introduce two new generalizations of the chromatic number to non-commutative graphs and provide an upper bound on the parameter of Stahlke. We provide a generalization of the graph complement and show the chromatic number of the orthogonal complement of a non-commutative graph is bounded below by its theta number. We also provide a generalization of both Sabidussi's Theorem and Hedetniemi's conjecture to non-commutative graphs. The study of non-local games considers scenarios in which separated players collaborate to provide satisfying responses to questions given by a referee. The condition of separating players makes non-local games an excellent setting to gain insight into quantum phenomena such as entanglement and non-locality. Non-local games can also provide protocols known as self-tests. Self-testing allows an experimenter to interact classically with a black box quantum system and certify that a specific entangled state was present and a specific set of measurements were performed. The most studied self-test is the CHSH game which certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. We introduce an algebraic generalization of CHSH and obtain a self-test for 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). This thesis is primarily based on two collaborative works written by the author and several coauthors [CMMN20], [KM19].
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 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.
To date all self-tests for high dimensional systems are confined to many-qubit states. This is due to two restrictions in the literature: the standard techniques for proving self-testing results apply only to qubits, and there are few suitable non-local games that are known to require high dimensional non-qubit states to achieve their optimal quantum value. In this paper we address these two problems. Specifically, we generalize the usual self-testing framework to qdddits and then apply it to a generalization of the magic square game, giving a self-test for two maximally entangled pairs of qdddits. This self-test has two parties, perfect completeness for honest quantum players, and requires only a constant number of measurement settings, regardless of the dimension ddd.
Correlation self-testing of a theory addresses the question of whether we can identify the set of correlations realizable in a theory from its performance in a particular information processing task. Applied to quantum theory it aims to identify an information processing task whose optimal performance is achieved only by theories realizing the same correlations as quantum theory in any causal structure. In M. Weilenmann and R. Colbeck [Phys. Rev. Lett. 125, 060406 (2020)], we introduce a candidate task for this---the adaptive Clauser-Horne-Shimony-Holt (CHSH) game. Here, we analyze the maximum probability of winning this game in different generalized probabilistic theories. We show that theories with a joint state space given by the minimal or the maximal tensor product are inferior to quantum theory, before considering other tensor products in theories whose elementary systems have various two-dimensional state spaces. For these, we find no theories that outperform quantum theory in the adaptive CHSH game and prove that it is impossible to recover the quantum performance in various cases. This is the first step towards a general solution that, if successful, will have wide-ranging consequences, in particular, enabling an experiment that could rule out all theories in which the set of realizable correlations does not coincide with the quantum set.
We present in this paper that the CHSH game admits one and only one optimal state and so remove all ambiguity of representations. More precisely, we use the well-known universal description of quantum commuting correlations as state space on the universal algebra for two player games, and so allows us to unambigiously compare quantum strategies as states on this common algebra. As such we find that the CHSH game leaves a single optimal state on this common algebra. In turn passing to any non-minimal Stinespring dilation for this unique optimal state is the only source of ambiguity (including self-testing): More precisely, any state on some operator algebra may be uniquely broken up into its minimal Stinespring dilation as an honest representation for the operator algebra followed by its vector state. Any other Stinespring dilation however arises simply as an extension of the minimal Stinespring dilation (i.e., as an embedding of the minimal Hilbert space into some random ambient one). As such this manifests the only source of ambiguity appearing in most (but not all!) traditional self-testing results such as for the CHSH game as well as in plenty of similar examples. We then further demonstrate the simplicity of our arguments on the Mermin--Peres magic square and magic pentagram game. Most importantly however, we present this article as an illustration of operator algebraic techniques on optimal states and their quotients, and we further pick up the results of the current article in another following one (currently under preparation) to derive a first robust self-testing result in the quantum commuting model.