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

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

Matthew McKague

Published May 30, 2016• 4 citations
arXivHTMLPDF

Abstract

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$.

DOI
10.48550/arxiv.1605.09435

Related papers

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

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

Device-independent parallel self-testing of two singlets

Xingyao Wu, Jean-Daniel Bancal, Matthew McKague +1 more

Device-independent self-testing offers the possibility of certifying the quantum state and measurements, up to local isometries, using only the statistics observed by querying uncharacterized local devices. In this paper we study parallel self-testing of two maximally entangled pairs of qubits; in particular, the local tensor product structure is not assumed but derived. We prove two criteria that achieve the desired result: a double use of the Clauser-Horne-Shimony-Holt inequality and the $3\ifmmode\times\else\texttimes\fi{}3$ magic square game. This demonstrate that the magic square game can only be perfectly won by measuring a two-singlet state. The tolerance to noise is well within reach of state-of-the-art experiments.

arXiv:1512.02074•Physical Review A•Jun 23, 2016•83 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

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

Self-testing in parallel

Matthew McKague

Self-testing allows us to determine, through classical interaction only, whether some players in a non-local game share particular quantum states. Most work on self-testing has concentrated on developing tests for small states like one pair of maximally entangled qubits, or on tests where there is a separate player for each qubit, as in a graph state. Here we consider the case of testing many maximally entangled pairs of qubits shared between two players. Previously such a test was shown where testing is sequential, i.e., one pair is tested at a time. Here we consider the parallel case where all pairs are tested simultaneously, giving considerably more power to dishonest players. We derive sufficient conditions for a self-test for many maximally entangled pairs of qubits shared between two players and also two constructions for self-tests where all pairs are tested simultaneously.

arXiv:1511.04194•New Journal of Physics•Apr 15, 2016•45 citations
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 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.
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).
Device-independent self-testing offers the possibility of certifying the quantum state and measurements, up to local isometries, using only the statistics observed by querying uncharacterized local devices. In this paper we study parallel self-testing of two maximally entangled pairs of qubits; in particular, the local tensor product structure is not assumed but derived. We prove two criteria that achieve the desired result: a double use of the Clauser-Horne-Shimony-Holt inequality and the $3\ifmmode\times\else\texttimes\fi{}3$ magic square game. This demonstrate that the magic square game can only be perfectly won by measuring a two-singlet state. The tolerance to noise is well within reach of state-of-the-art experiments.
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.
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 allows us to determine, through classical interaction only, whether some players in a non-local game share particular quantum states. Most work on self-testing has concentrated on developing tests for small states like one pair of maximally entangled qubits, or on tests where there is a separate player for each qubit, as in a graph state. Here we consider the case of testing many maximally entangled pairs of qubits shared between two players. Previously such a test was shown where testing is sequential, i.e., one pair is tested at a time. Here we consider the parallel case where all pairs are tested simultaneously, giving considerably more power to dishonest players. We derive sufficient conditions for a self-test for many maximally entangled pairs of qubits shared between two players and also two constructions for self-tests where all pairs are tested simultaneously.