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

Tracially embeddable strategies: Lifting MIP* tricks to MIPco

Junqiao Lin

Published Apr 4, 2023• 1 citation
arXivHTMLPDF

Abstract

We prove that any two-party correlation in the commuting operator model can be approximated using a tracially embeddable strategy, a class of strategies defined on a finite tracial von Neumann algebra, which we define in this paper. Using this characterization, we show that any approximately synchronous correlation can be approximated to the average of a collection of synchronous correlations in the commuting operator model. This generalizes the result from Vidick [JMP 2022] which only applies to finite-dimensional quantum correlations. As a corollary, we show that the quantum tensor code test from Ji et al. [FOCS 2022] follows the soundness property even under the general commuting operator model. Furthermore, we extend the state-dependent norm variant of the Gowers-Hatami theorem to finite von Neumann algebras. Combined with the aforementioned characterization, this enables us to lift many known results about robust self-testing for non-local games to the commuting operator model, including a sample efficient finite-dimensional EPR testing for the commuting operator strategies. We believe that, in addition to the contribution from this paper, this class of strategies can be helpful for further understanding non-local games in the infinite-dimensional setting.

DOI
10.48550/arxiv.2304.01940

Related papers

MIPco=coRE

J. F. Lin

In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP* except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.

arXiv:2510.07162•Oct 8, 2025•1 citation

MIPᶜᵒ=coRE

Junqiao (Randy) Lin

In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen shows that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP*, except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084].

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•0 citations

A non-robust quantum correlation self-test

Ranyiliu Chen, Yuming Zhao

We show that exact self-testing of a quantum correlation does not imply robust self-testing. Mančinska and Schmidt previously established such a separation for non-local games, but their obstruction to robustness arises from two distinct optimal correlations, with the self-tested one remaining robust. We establish the separation for a single correlation. Our proof is operator-algebraic. The main technical contribution is a general construction that associates a synchronous binary correlation to any finitely presented C*-algebra with unitary generators and real-coefficient relations. The implementing states of the correlation correspond exactly to the tracial states on the algebra. We apply this construction to an algebra with a unique finite-dimensional tracial state and a distinct amenable tracial state. By a characterization established by Zhao and independently by Kar, the resulting correlation is a self-test but not a robust self-test.

quant-pharXiv:2609.25117•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

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

A commuting operator self-test for exact entanglement embezzlement

Connor Paddock, Simon Schmidt

We show that the optimal commuting operator correlation for a variant of Coladangelo's two-player generalized nonlocal game, based on the embezzlement of entanglement, is a commuting operator self-test. Our result gives the first correlation self-test for an exact entanglement embezzlement protocol in the commuting operator framework. Because the unique optimal correlation necessitates the exact embezzlement of entanglement, the correlation is unrealizable using quantum tensor-product models, even if the local spaces are allowed to be infinite dimensional. As such, our result provides an example of a commuting operator self-test where the Hilbert space shared by the two parties cannot be factored into a tensor-product of local spaces that is compatible with the local measurement operators. Our main proof technique relies on Harris' unique abstract state characterization of exact embezzlement of entanglement involving Cuntz algebras.

quant-pharXiv:2609.38083•Sep 30, 2026•0 citations
We prove that any two-party correlation in the commuting operator model can be approximated using a tracially embeddable strategy, a class of strategies defined on a finite tracial von Neumann algebra, which we define in this paper. Using this characterization, we show that any approximately synchronous correlation can be approximated to the average of a collection of synchronous correlations in the commuting operator model. This generalizes the result from Vidick [JMP 2022] which only applies to finite-dimensional quantum correlations. As a corollary, we show that the quantum tensor code test from Ji et al. [FOCS 2022] follows the soundness property even under the general commuting operator model. Furthermore, we extend the state-dependent norm variant of the Gowers-Hatami theorem to finite von Neumann algebras. Combined with the aforementioned characterization, this enables us to lift many known results about robust self-testing for non-local games to the commuting operator model, including a sample efficient finite-dimensional EPR testing for the commuting operator strategies. We believe that, in addition to the contribution from this paper, this class of strategies can be helpful for further understanding non-local games in the infinite-dimensional setting.
In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP* except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.
In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen shows that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP*, except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084].
We show that exact self-testing of a quantum correlation does not imply robust self-testing. Mančinska and Schmidt previously established such a separation for non-local games, but their obstruction to robustness arises from two distinct optimal correlations, with the self-tested one remaining robust. We establish the separation for a single correlation. Our proof is operator-algebraic. The main technical contribution is a general construction that associates a synchronous binary correlation to any finitely presented C*-algebra with unitary generators and real-coefficient relations. The implementing states of the correlation correspond exactly to the tracial states on the algebra. We apply this construction to an algebra with a unique finite-dimensional tracial state and a distinct amenable tracial state. By a characterization established by Zhao and independently by Kar, the resulting correlation is a self-test but not a robust self-test.
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 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.
We show that the optimal commuting operator correlation for a variant of Coladangelo's two-player generalized nonlocal game, based on the embezzlement of entanglement, is a commuting operator self-test. Our result gives the first correlation self-test for an exact entanglement embezzlement protocol in the commuting operator framework. Because the unique optimal correlation necessitates the exact embezzlement of entanglement, the correlation is unrealizable using quantum tensor-product models, even if the local spaces are allowed to be infinite dimensional. As such, our result provides an example of a commuting operator self-test where the Hilbert space shared by the two parties cannot be factored into a tensor-product of local spaces that is compatible with the local measurement operators. Our main proof technique relies on Harris' unique abstract state characterization of exact embezzlement of entanglement involving Cuntz algebras.