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:2105.10658

Glued magic games self-test maximally entangled states

Laura Mančinska, Thor Gabelgaard Nielsen, Jitendra Prakash

Published May 22, 2021• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2105.10658

Related papers

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

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

Practical parallel self-testing of Bell states via magic rectangles

Sean A. Adamson, Petros Wallden

Self-testing is a method to verify that one has a particular quantum state from purely classical statistics. For practical applications, such as device-independent delegated verifiable quantum computation, it is crucial that one self-tests multiple Bell states in parallel while keeping the quantum capabilities required of one side to a minimum. In this work, we use the $3\ifmmode\times\else\texttimes\fi{}n$ magic rectangle games (generalizations of the magic square game) to obtain a self-test for $n$ Bell states where the one side needs only to measure single-qubit Pauli observables. The protocol requires small input sizes [constant for Alice and $O({log}_{2}n)$ bits for Bob] and is robust with robustness $O({n}^{5/2}\sqrt{\ensuremath{\varepsilon}})$, where $\ensuremath{\varepsilon}$ is the closeness of the ideal (perfect) correlations to those observed. To achieve the desired self-test, we introduce a one-side-local quantum strategy for the magic square game that wins with certainty, we generalize this strategy to the family of $3\ifmmode\times\else\texttimes\fi{}n$ magic rectangle games, and we supplement these nonlocal games with extra check rounds (of single and pairs of observables).

arXiv:2105.04044•Physical Review A•Mar 31, 2022•2 citations

Robust self-testing of nonmaximal entanglement from a reduced inner product game

Ranyiliu Chen

We reduce Lalonde's pseudo-telepathy inner product game from six to five dimensions, keeping its four Alice questions and three Bob questions and reducing each answer alphabet to five. We prove that the reduced game self-tests its nonmaximally entangled state and all 35 measurement effects. The self-test is also robust: for a strategy winning with probability at least $1-\varepsilon$ we obtain $d_{\mathrm{ext}}\le\min\{1,2^{21}\sqrt{\varepsilon}\}$, where $d_{\mathrm{ext}}=\sqrt{1-Ξ}$ and $Ξ$ is the optimal squared fidelity with the reference state under local extraction channels. A compactness argument then gives simultaneous qualitative robustness for all measurement actions on the state under common local isometries. As a consequence of the self-test, no maximally entangled state of any finite dimension can win the game perfectly.

quant-pharXiv:2609.24349•Sep 22, 2026•0 citations

Lifting the maximally-entangledness assumption in robust self-testing for synchronous games

Matthijs Vernooij, Yuming Zhao

Robust self-testing in non-local games allows a classical referee to certify that two untrustworthy players are able to perform a specific quantum strategy up to high precision. Proving robust self-testing results becomes significantly easier when one restricts the allowed strategies to symmetric projective maximally entangled (PME) strategies, which allow natural descriptions in terms of tracial von Neumann algebras. This has been exploited in the celebrated M I P ∗ = R E paper and related articles to prove robust self-testing results for synchronous games when restricting to PME strategies. However, the PME assumptions are not physical, so these results need to be upgraded to make them physically relevant. In this work, we do just that: we prove that any perfect synchronous game which is a robust self-test when restricted to PME strategies, is in fact a robust self-test for all strategies. We then apply our result to the Quantum Low Degree Test to find an efficient n -qubit test.

arXiv:2505.05994•Quantum•Oct 1, 2026•0 citations

The right entanglement for perfect nonlocality and zero-error communication

Laura Mančinska

We identify a structural mechanism by which perfect play in a nonlocal game requires and self-tests a specific non-maximally entangled state. To this end, we construct a Flagged Magic-Square game by extending the standard Magic-Square game with an additional ``flag'' outcome and two additional questions for each player. The game admits a perfect strategy using a state with Schmidt coefficients proportional to $(1,\sqrt{2},\sqrt{2},\sqrt{2},\sqrt{2})$. We give a direct algebraic proof that maximally entangled strategies have winning probability bounded away from one, independently of dimension. Moreover, the game self-tests this state, providing an example of a two-party pseudo-telepathy game that certifies a specific non-maximally entangled state. Our construction illustrates how adding suitable constraints to a rigid measurement geometry can enforce specific Schmidt ratios and provides a modular route to further self-tests based on other rigid pseudo-telepathy games. We establish a general game-to-channel reduction that transfers separations in the game model to one-shot zero-error communication over classical channels. Applied to the Flagged Magic-Square game, it yields a classical channel for which entanglement permits the zero-error transmission of ten messages in a single use, whereas any finite-dimensional maximally entangled resource permits at most nine. Thus, maximally entangled states are not a universally optimal entanglement resource for zero-error communication over classical noisy channels.

quant-pharXiv:2610.06512•Oct 6, 2026•0 citations
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.
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.
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.
Self-testing is a method to verify that one has a particular quantum state from purely classical statistics. For practical applications, such as device-independent delegated verifiable quantum computation, it is crucial that one self-tests multiple Bell states in parallel while keeping the quantum capabilities required of one side to a minimum. In this work, we use the $3\ifmmode\times\else\texttimes\fi{}n$ magic rectangle games (generalizations of the magic square game) to obtain a self-test for nnn Bell states where the one side needs only to measure single-qubit Pauli observables. The protocol requires small input sizes [constant for Alice and O(log2n)O({log}_{2}n)O(log2​n) bits for Bob] and is robust with robustness $O({n}^{5/2}\sqrt{\ensuremath{\varepsilon}})$, where $\ensuremath{\varepsilon}$ is the closeness of the ideal (perfect) correlations to those observed. To achieve the desired self-test, we introduce a one-side-local quantum strategy for the magic square game that wins with certainty, we generalize this strategy to the family of $3\ifmmode\times\else\texttimes\fi{}n$ magic rectangle games, and we supplement these nonlocal games with extra check rounds (of single and pairs of observables).
We reduce Lalonde's pseudo-telepathy inner product game from six to five dimensions, keeping its four Alice questions and three Bob questions and reducing each answer alphabet to five. We prove that the reduced game self-tests its nonmaximally entangled state and all 35 measurement effects. The self-test is also robust: for a strategy winning with probability at least 1−ε1-\varepsilon1−ε we obtain dext≤min⁡{1,221ε}d_{\mathrm{ext}}\le\min\{1,2^{21}\sqrt{\varepsilon}\}dext​≤min{1,221ε​}, where dext=1−Ξd_{\mathrm{ext}}=\sqrt{1-Ξ}dext​=1−Ξ​ and ΞΞΞ is the optimal squared fidelity with the reference state under local extraction channels. A compactness argument then gives simultaneous qualitative robustness for all measurement actions on the state under common local isometries. As a consequence of the self-test, no maximally entangled state of any finite dimension can win the game perfectly.
Robust self-testing in non-local games allows a classical referee to certify that two untrustworthy players are able to perform a specific quantum strategy up to high precision. Proving robust self-testing results becomes significantly easier when one restricts the allowed strategies to symmetric projective maximally entangled (PME) strategies, which allow natural descriptions in terms of tracial von Neumann algebras. This has been exploited in the celebrated M I P ∗ = R E paper and related articles to prove robust self-testing results for synchronous games when restricting to PME strategies. However, the PME assumptions are not physical, so these results need to be upgraded to make them physically relevant. In this work, we do just that: we prove that any perfect synchronous game which is a robust self-test when restricted to PME strategies, is in fact a robust self-test for all strategies. We then apply our result to the Quantum Low Degree Test to find an efficient n -qubit test.
We identify a structural mechanism by which perfect play in a nonlocal game requires and self-tests a specific non-maximally entangled state. To this end, we construct a Flagged Magic-Square game by extending the standard Magic-Square game with an additional ``flag'' outcome and two additional questions for each player. The game admits a perfect strategy using a state with Schmidt coefficients proportional to (1,2,2,2,2)(1,\sqrt{2},\sqrt{2},\sqrt{2},\sqrt{2})(1,2​,2​,2​,2​). We give a direct algebraic proof that maximally entangled strategies have winning probability bounded away from one, independently of dimension. Moreover, the game self-tests this state, providing an example of a two-party pseudo-telepathy game that certifies a specific non-maximally entangled state. Our construction illustrates how adding suitable constraints to a rigid measurement geometry can enforce specific Schmidt ratios and provides a modular route to further self-tests based on other rigid pseudo-telepathy games. We establish a general game-to-channel reduction that transfers separations in the game model to one-shot zero-error communication over classical channels. Applied to the Flagged Magic-Square game, it yields a classical channel for which entanglement permits the zero-error transmission of ten messages in a single use, whereas any finite-dimensional maximally entangled resource permits at most nine. Thus, maximally entangled states are not a universally optimal entanglement resource for zero-error communication over classical noisy channels.