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

Almost perfect strategies for projection games are approximately tracial

Eric Culf

quant-phmath.OASubmitted Mar 16, 2026• Announced Mar 17, 2026• 0 citations
arXivHTMLPDF

Abstract

Projection games constitute an important class of nonlocal games where, for any answer from the first player, there is a unique correct answer for the second player. This class of games captures nonlocal games arising from constraint satisfaction problems, oracularisations, and unique games. However, due to the asymmetry between the players, projection games are in general not synchronous, and therefore the powerful results constraining the structure of almost perfect strategies for synchronous games do not apply. In this work, we adapt results of Marrakchi and de la Salle for synchronous games to show that, in both the quantum and commuting-operator models, any strategy that wins with probability $1-\varepsilon$ in a projection game gives rise to a tracial strategy that wins with probability $1-O((L\varepsilon)^{1/4})$, where $L$ is the inverse of the minimal conditional probability of a question for the second player being sampled given a question to the first. For constraint system games, this strengthens the rounding result of Paddock by eliminating the dependence on number of constraints and improving the dependence on constraint size, while also generalising to the commuting-operator setting.

Comments
19 pages, 0 figures

Related papers

Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states

Connor Paddock

We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding $*$-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp.~XOR-algebra) yields measurement operators for near-perfect (resp.~near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp.~near-optimal XOR) quantum strategy is close to a near-perfect (resp.~near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is $*$-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.

arXiv:2203.02525•Mar 4, 2022•0 citations

Rounding near-optimal quantum strategies for nonlocal games to strategies using a maximally entangled state

Connor Paddock

We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding ∗-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp. XOR-algebra) yields measurement operators for near-perfect (resp. near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp. near-optimal XOR) quantum strategy is close to a near-perfect (resp. near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is ∗-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.

Journal of Mathematical Physics•Dec 1, 2025•0 citations

Synchronous games with *-isomorphic game algebras

Samuel J. Harris

We establish several strong equivalences of synchronous non-local games, in the sense that the corresponding game algebras are $*$-isomorphic. We first show that the game algebra of any synchronous game on $n$ inputs and $k$ outputs is $*$-isomorphic to the game algebra of an associated bisynchronous game on $nk$ inputs and $nk$ outputs. As a result, we show that there are bisynchronous games with equal question and answer sets, whose optimal strategies only exist in the quantum commuting model, and not in the quantum approximate model. Moreover, we show that there are bisynchronous games with equal question and answer sets that have non-zero game algebras, but no winning quantum commuting strategies, resolving a problem of V.I. Paulsen and M. Rahaman. We also exhibit a $*$-isomorphism between any synchronous game algebra with $n$ questions and $k>3$ answers and a synchronous game algebra with $n(k-2)$ questions and $3$ answers.

arXiv:2109.04859•Quantum Information and Computation•Aug 1, 2022•2 citations

Tracially embeddable strategies: Lifting MIP* tricks to MIPco

Junqiao Lin

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.

arXiv:2304.01940•Apr 4, 2023•1 citation

A nonlocal game whose dimension exponent is uncomputable

Seth Douglas, Nidhal Mghirbi

Can uncomputability occur in the resource law of one fixed finite nonlocal game, rather than in a problem whose input is a game? We construct a finite two-player Boolean constraint-system game with rational question probabilities, quantum value one, and no finite-dimensional perfect strategy. If $D(\varepsilon)$ is the least local dimension needed to win with probability at least $1-\varepsilon$, then $\lim_{n\to\infty}\log_2 D(2^{-n})/n=(3+\theta_K)/4$, where $\theta_K=\sum_{e\in K}4^{-(e+1)}$ and $K$ is the halting set. This exponent has the Turing degree of $K$. The construction combines finite operator relations for three Cantor clocks, a counter program with forced initialization, and a conditional clock that charges dimension for halting inputs. A Boolean compiler preserves weighted precision linearly and converts flat models to strategies with quadratic loss. The lower bound holds in every density matrix. Explicit finite models attain the same rate. The flag-density lower bound uses compactness without an effective modulus; convergence to the dimension exponent has no computable certified rate.

•Oct 27, 2026•8 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
Projection games constitute an important class of nonlocal games where, for any answer from the first player, there is a unique correct answer for the second player. This class of games captures nonlocal games arising from constraint satisfaction problems, oracularisations, and unique games. However, due to the asymmetry between the players, projection games are in general not synchronous, and therefore the powerful results constraining the structure of almost perfect strategies for synchronous games do not apply. In this work, we adapt results of Marrakchi and de la Salle for synchronous games to show that, in both the quantum and commuting-operator models, any strategy that wins with probability 1−ε1-\varepsilon1−ε in a projection game gives rise to a tracial strategy that wins with probability 1−O((Lε)1/4)1-O((L\varepsilon)^{1/4})1−O((Lε)1/4), where LLL is the inverse of the minimal conditional probability of a question for the second player being sampled given a question to the first. For constraint system games, this strengthens the rounding result of Paddock by eliminating the dependence on number of constraints and improving the dependence on constraint size, while also generalising to the commuting-operator setting.
We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding ∗*∗-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp.~XOR-algebra) yields measurement operators for near-perfect (resp.~near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp.~near-optimal XOR) quantum strategy is close to a near-perfect (resp.~near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is ∗*∗-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.
We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding ∗-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp. XOR-algebra) yields measurement operators for near-perfect (resp. near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp. near-optimal XOR) quantum strategy is close to a near-perfect (resp. near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is ∗-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.
We establish several strong equivalences of synchronous non-local games, in the sense that the corresponding game algebras are ∗*∗-isomorphic. We first show that the game algebra of any synchronous game on nnn inputs and kkk outputs is ∗*∗-isomorphic to the game algebra of an associated bisynchronous game on nknknk inputs and nknknk outputs. As a result, we show that there are bisynchronous games with equal question and answer sets, whose optimal strategies only exist in the quantum commuting model, and not in the quantum approximate model. Moreover, we show that there are bisynchronous games with equal question and answer sets that have non-zero game algebras, but no winning quantum commuting strategies, resolving a problem of V.I. Paulsen and M. Rahaman. We also exhibit a ∗*∗-isomorphism between any synchronous game algebra with nnn questions and k>3k>3k>3 answers and a synchronous game algebra with n(k−2)n(k-2)n(k−2) questions and 333 answers.
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.
Can uncomputability occur in the resource law of one fixed finite nonlocal game, rather than in a problem whose input is a game? We construct a finite two-player Boolean constraint-system game with rational question probabilities, quantum value one, and no finite-dimensional perfect strategy. If D(ε)D(\varepsilon)D(ε) is the least local dimension needed to win with probability at least 1−ε1-\varepsilon1−ε, then lim⁡n→∞log⁡2D(2−n)/n=(3+θK)/4\lim_{n\to\infty}\log_2 D(2^{-n})/n=(3+\theta_K)/4limn→∞​log2​D(2−n)/n=(3+θK​)/4, where θK=∑e∈K4−(e+1)\theta_K=\sum_{e\in K}4^{-(e+1)}θK​=∑e∈K​4−(e+1) and KKK is the halting set. This exponent has the Turing degree of KKK. The construction combines finite operator relations for three Cantor clocks, a counter program with forced initialization, and a conditional clock that charges dimension for halting inputs. A Boolean compiler preserves weighted precision linearly and converts flat models to strategies with quadratic loss. The lower bound holds in every density matrix. Explicit finite models attain the same rate. The flag-density lower bound uses compactness without an effective modulus; convergence to the dimension exponent has no computable certified rate.
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.