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• 1 citation
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 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.

arXiv:2203.02525•Journal of Mathematical Physics•Dec 1, 2025•15 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•3 citations

Quadratic Repetition for Commuting Projection Games and Noisy Quantum Communication

Harjas Sandhu

How reliably does repeating a quantum verification test amplify its soundness when the players can coordinate all their answers? This paper proves a quadratic-gap parallel-repetition bound for finite two-player games whose winning answer graphs are unions of disjoint complete bipartite blocks. The class includes noninjective and partial projection games, with arbitrary joint question distributions within each independent round and arbitrary commuting-operator strategies. If the single-game commuting value is 1 − ε, the probability of winning all n repetitions is at most exp(−2−75 ε²n). Known binary line games show that the quadratic gap power is optimal within the full block class, up to constants. A separate finite-dimensional tensor theorem uses its own single-game gap. The proof constructs one exact conditioned target with square-root-weighted rectangle labels and two independently normalized one-sided comparison states. Entropy cancellation and finite-tracial local reconstruction give a charged extension, heterogeneous repetition bounds and weighted-threshold concentration. Scalar finite-table closure then transfers the estimates to arbitrary commuting strategies. A further application bounds interactive finite-dimensional quantum protocols communicating through prescribed memoryless channels. Exponential zero-communication soundness survives a strict aggregate entanglement-assisted capacity budget. An explicit erasure-channel coding example illustrates the bound with polynomial encoding and decoding costs. The results do not establish quadratic repetition for arbitrary predicates, uniform finite-dimensional resources for arbitrary commuting strategies, or an efficient locality-preserving Hamiltonian or cryptographic compiler. The paper develops the reconstruction premise left conditional in Entropy Budgets and Weighted Concentration in Parallel Games.

•Nov 7, 2026•0 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•10 citations

k-partite quantum homomorphisms

Amin Karamlou

$k$-partite XOR games and linear binary constraint system (BCS) games arise from systems of linear equations over $\mathbb{Z}_2$, providing distinct quantum relaxations of the same classical constraint satisfaction problem (CSP). Linear BCS games have been generalised to synchronous homomorphism games on arbitrary relational structures, with compositional semantics provided by the quantum monad. We introduce $k$-partite homomorphism games, extending $k$-XOR games from linear systems to arbitrary relational structures. This yields a framework for studying multipartite quantum CSPs and quantum homomorphisms. We characterise perfect strategies in both the tensor-product and commuting-operator models as Kleisli morphisms of suitable state-dependent graded quantum monads on a category of $k$-partite relational structures. We then study quantum advantage in the pseudotelepathic sense: the existence of a perfect quantum strategy without a perfect classical strategy. We show that synchronous and $k$-partite quantum advantage are incomparable at the level of CSP instances. The GHZ instance admits three-player quantum advantage but no synchronous commuting-operator advantage, whereas the magic-square instance admits synchronous quantum advantage but no $k$-partite commuting-operator advantage for any number of players or proper colouring. We also exhibit an explicit six-element template whose CSP is NP-complete and admits two-player quantum advantage. Finally, we prove that no bounded-width CSP template admits $k$-partite quantum advantage, even in the commuting-operator model.

arXiv:2611.15839•Nov 11, 2026•0 citations

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•10 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 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.
How reliably does repeating a quantum verification test amplify its soundness when the players can coordinate all their answers? This paper proves a quadratic-gap parallel-repetition bound for finite two-player games whose winning answer graphs are unions of disjoint complete bipartite blocks. The class includes noninjective and partial projection games, with arbitrary joint question distributions within each independent round and arbitrary commuting-operator strategies. If the single-game commuting value is 1 − ε, the probability of winning all n repetitions is at most exp(−2−75 ε²n). Known binary line games show that the quadratic gap power is optimal within the full block class, up to constants. A separate finite-dimensional tensor theorem uses its own single-game gap. The proof constructs one exact conditioned target with square-root-weighted rectangle labels and two independently normalized one-sided comparison states. Entropy cancellation and finite-tracial local reconstruction give a charged extension, heterogeneous repetition bounds and weighted-threshold concentration. Scalar finite-table closure then transfers the estimates to arbitrary commuting strategies. A further application bounds interactive finite-dimensional quantum protocols communicating through prescribed memoryless channels. Exponential zero-communication soundness survives a strict aggregate entanglement-assisted capacity budget. An explicit erasure-channel coding example illustrates the bound with polynomial encoding and decoding costs. The results do not establish quadratic repetition for arbitrary predicates, uniform finite-dimensional resources for arbitrary commuting strategies, or an efficient locality-preserving Hamiltonian or cryptographic compiler. The paper develops the reconstruction premise left conditional in Entropy Budgets and Weighted Concentration in Parallel Games.
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.
kkk-partite XOR games and linear binary constraint system (BCS) games arise from systems of linear equations over Z2\mathbb{Z}_2Z2​, providing distinct quantum relaxations of the same classical constraint satisfaction problem (CSP). Linear BCS games have been generalised to synchronous homomorphism games on arbitrary relational structures, with compositional semantics provided by the quantum monad. We introduce kkk-partite homomorphism games, extending kkk-XOR games from linear systems to arbitrary relational structures. This yields a framework for studying multipartite quantum CSPs and quantum homomorphisms. We characterise perfect strategies in both the tensor-product and commuting-operator models as Kleisli morphisms of suitable state-dependent graded quantum monads on a category of kkk-partite relational structures. We then study quantum advantage in the pseudotelepathic sense: the existence of a perfect quantum strategy without a perfect classical strategy. We show that synchronous and kkk-partite quantum advantage are incomparable at the level of CSP instances. The GHZ instance admits three-player quantum advantage but no synchronous commuting-operator advantage, whereas the magic-square instance admits synchronous quantum advantage but no kkk-partite commuting-operator advantage for any number of players or proper colouring. We also exhibit an explicit six-element template whose CSP is NP-complete and admits two-player quantum advantage. Finally, we prove that no bounded-width CSP template admits kkk-partite quantum advantage, even in the commuting-operator model.
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.