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

Perfect Games in Dimension-Bounded Communication

E. Zambrini Cruzeiro

quant-phSubmitted Aug 5, 2026• Announced Aug 6, 2026• 0 citations
v1 · Aug 5, 2026v2 · Aug 25, 2026
arXivHTMLPDF

Abstract

Perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage: a quantum system of dimension $d$ satisfies every prescribed winning constraint, whereas a classical $d$-level message cannot. We establish two structural results for such forbidden-output support constraints. First, every binary-output support game reduces exactly to a conflict graph: perfect classical realization with a $d$-level message is equivalent to $d$-colorability, perfect $d$-dimensional quantum realization is equivalent to a $d$-dimensional orthogonal representation, and the minimum number of Bob inputs realizing a fixed conflict graph is its edge biclique-cover number. Second, for an arbitrary finite output alphabet, every perfect qubit strategy admits a perfect classical-bit realization. As a flagship application, the $13$-ray qutrit graph yields a compressed game $(X,Y,B)=(13,8,2)$ with $C_3=39<Q_3=S=40$, and eight Bob inputs are minimal among all binary-output realizations of that graph. Graph extensions demonstrate the mechanism in every dimension, while Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime. These results connect exact communication, graph coloring, contextuality, state exclusion, and zero-error information theory.

Related papers

The price of precision: usable entanglement in nonlocal games and the geometry of groups

Seth Douglas, Nidhal Mghirbi

In a nonlocal game of quantum value one that no finite-dimensional strategy wins, near-perfect play needs growing dimension, which separable states can have. We ask how much usable entanglement it needs: the demand at loss $\varepsilon$ is the least one-way distillable entanglement of the original state of a strategy of loss at most $\varepsilon$. For synchronous games with tested diagonals and for constraint-variable consistency games, demand diverges exactly when no finite-dimensional strategy is perfect; then, for any number of Bell pairs and any fidelity below one, every sufficiently good mixed strategy yields that many at that fidelity by local isometries. For rational synchronous or binary constraint games, a loss guaranteeing this is computable under a promise, but boundedness of demand is undecidable among games of value one. Demand is at least logarithmic if near-winners have a sign relation and an even dilation mirrored by both players, as in a game from Abels' group. For agreement games the directions agree up to a factor three in loss, optimal among Bob-fixed deterministic local symmetrizations. The geometry of the group behind a game, not its presentation, sets the rates. Fixed games demand $\alpha\log(1/\varepsilon)$ for every $\alpha=\frac12\sum_i\log_{m_i}q_i$ with $q_i\ge2$ a power of two dividing $m_i$, a dense set containing all positive rationals and some transcendentals, such as $\frac12\log_62$; a configuration-lamp game demands $\varepsilon^{-1+o(1)}$; Pauli lamps on the points of Houghton's three rays give demand between $\varepsilon^{-0.0690}$ and $\varepsilon^{-1/4}$. If group relations hold exactly and Alice matches Bob to error $e$, demand counts qubits addressable by short words: $\Theta(1/e)$, $\Theta(e^{-k})$ for integers $k\ge1$, or $2^{\Theta(1/e)}$. Conditional on our attainment and tail bounds, the $I_{3322}$ optimum needs bounded usable entanglement.

•Oct 27, 2026•2 citations

Quantum communication and Bell nonlocality require infinite classical communication to simulate

Carlos de Gois, Thyago S. R. Santos, Carlos Vieira

A quantum system of any fixed dimension can be prepared in a continuum of states, yet it cannot be used to transmit an unlimited amount of classical information. Similarly, the correlations observed between measurement outcomes on separate parts of a shared quantum system can be stronger than classical correlations, but they cannot transmit information. These fundamental limitations suggest that the statistics observed from quantum communication and quantum correlations may admit a simulation using a finite amount of classical communication. This expectation is confirmed in the smallest nontrivial quantum dimension, with two classical bits being necessary and sufficient to exactly simulate qubit communication and all correlations between qubits. Despite significant efforts during the previous decades, this remained the only solved case. Here we resolve both problems for every quantum dimension. The solution reveals an unexpected qualitative transition starting at dimension four: no finite amount of classical communication can exactly simulate ququart communication nor all quantum correlations of two entangled ququarts, even with unlimited shared randomness. One might have expected this transition, if it existed, to appear already for qutrits. Instead, we construct an explicit protocol that exactly simulates qutrit communication using $357$ classical bits, and consequently, all correlations of two entangled qutrits.

quant-pharXiv:2609.04182•Sep 4, 2026•0 citations

Simplest Bipartite Perfect Quantum Strategies

Adán Cabello

A bipartite perfect quantum strategy (BPQS) allows two players who cannot communicate with each other to always win a nonlocal game. BPQSs are rare but fundamental in light of some recent results in quantum information, computation, and foundations. A more than 40-year-old open problem is how many inputs (measurement settings) a BPQS requires. A related problem is how many inputs are needed if, in addition, the quantum system has minimum dimension. A third, apparently unrelated, problem is what is the connection between BPQSs and state-independent contextuality, which inspired the first BPQSs. Here, we solve the third problem: we prove that every BPQS defines a Kochen-Specker set. We use this result to identify the BPQS with the smallest number of inputs, both in the general case and in the case of minimum dimension, and solve some related problems. We conjecture that the BPQSs presented here are the solutions to the first two problems.

arXiv:2311.17735•Physical Review Letters•Jan 2, 2025•8 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

All-vs-Nothing Operational Manifestation of Preparation Contextuality

Jayashree Karmakar, Rafiuddin Gazi, Biswadeep Chatterjee +4 more

Preparation contextuality is often manifested operationally through a quantitative advantage over preparation-noncontextual models in information-processing tasks, yet quantum theory typically falls short of perfect success. Here we introduce a parity-oblivious Hidden Matching task that instead yields an all-vs-nothing manifestation of preparation contextuality. Alice encodes an $n$-bit string so that her message reveals no information about any input parity other than the two-bit parities. Bob, given a perfect matching on the input positions, must output an edge of the matching together with the parity of its two bits. A quantum protocol using a single $\lceil\log_2 n\rceil$-qubit message satisfies the parity-obliviousness constraint and succeeds with certainty. We prove that no preparation-noncontextual model achieves perfect success for any even $n\ge6$. The result holds for arbitrary ontic state spaces and assumes neither outcome determinism nor measurement noncontextuality. For $n=6$ and $n=8$, the optimal noncontextual success probabilities are $4/5$ and $3/4$, respectively, while asymptotically the optimal noncontextual success probability is $1/2+Θ(1/\sqrt n)$. Our asymptotic upper bound follows from a Fourier-analytic sum rule derived via hypercontractivity on the Boolean hypercube. The resulting separation is qualitative rather than merely quantitative: quantum theory achieves perfect success, whereas preparation-noncontextual models cannot. We aslo show that at $n=8$ the noncontextual bound remains $3/4$ even when Bob is restricted to just suitable $4$ of the $105$ possible perfect matchings, bringing the effect within experimental reach.

quant-pharXiv:2609.34964•Sep 29, 2026•0 citations

Perfect quantum strategies with small input cardinality

Stefan Trandafir, Junior R. Gonzales-Ureta, Adán Cabello

A perfect strategy is one that allows the mutually in-communicated players of a nonlocal game to win every trial of the game. Perfect strategies are basic tools for some fundamental results in quantum computation and crucial resources for some applications in quantum information. Here, we address the problem of producing qudit-qudit perfect quantum strategies with a small number of settings. For that, we exploit a recent result showing that any perfect quantum strategy induces a Kochen-Specker set. We identify a family of KS sets in even dimension $d \ge 6$ that, for many dimensions, require the smallest number of orthogonal bases known: $d+1$. This family was only defined for some $d$. We first extend the family to infinitely many more dimensions. Then, we show the optimal way to use each of these sets to produce a bipartite perfect strategy with minimum input cardinality. As a result, we present a family of perfect quantum strategies in any $(2,d-1,d)$ Bell scenario, with $d = 2^kp^m$ for $p$ prime, $m \geq k \geq 0$ (excluding $m=k=0$), $d = 8p$ for $p \geq 19$, $d=kp$ for $p > ((k-2)2^{k-2})^2$ whenever there exists a Hadamard matrix of order $k$, other sporadic examples, as well as a recursive construction that produces perfect quantum strategies for infinitely many dimensions $d$ from any dimension $d'$ with a perfect quantum strategy. We identify their associated Bell inequalities and prove that they are not tight, which provides a second counterexample to a conjecture of 2007.

arXiv:2407.21473•Jul 31, 2024•0 citations
Perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage: a quantum system of dimension ddd satisfies every prescribed winning constraint, whereas a classical ddd-level message cannot. We establish two structural results for such forbidden-output support constraints. First, every binary-output support game reduces exactly to a conflict graph: perfect classical realization with a ddd-level message is equivalent to ddd-colorability, perfect ddd-dimensional quantum realization is equivalent to a ddd-dimensional orthogonal representation, and the minimum number of Bob inputs realizing a fixed conflict graph is its edge biclique-cover number. Second, for an arbitrary finite output alphabet, every perfect qubit strategy admits a perfect classical-bit realization. As a flagship application, the 131313-ray qutrit graph yields a compressed game (X,Y,B)=(13,8,2)(X,Y,B)=(13,8,2)(X,Y,B)=(13,8,2) with C3=39<Q3=S=40C_3=39<Q_3=S=40C3​=39<Q3​=S=40, and eight Bob inputs are minimal among all binary-output realizations of that graph. Graph extensions demonstrate the mechanism in every dimension, while Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime. These results connect exact communication, graph coloring, contextuality, state exclusion, and zero-error information theory.
In a nonlocal game of quantum value one that no finite-dimensional strategy wins, near-perfect play needs growing dimension, which separable states can have. We ask how much usable entanglement it needs: the demand at loss ε\varepsilonε is the least one-way distillable entanglement of the original state of a strategy of loss at most ε\varepsilonε. For synchronous games with tested diagonals and for constraint-variable consistency games, demand diverges exactly when no finite-dimensional strategy is perfect; then, for any number of Bell pairs and any fidelity below one, every sufficiently good mixed strategy yields that many at that fidelity by local isometries. For rational synchronous or binary constraint games, a loss guaranteeing this is computable under a promise, but boundedness of demand is undecidable among games of value one. Demand is at least logarithmic if near-winners have a sign relation and an even dilation mirrored by both players, as in a game from Abels' group. For agreement games the directions agree up to a factor three in loss, optimal among Bob-fixed deterministic local symmetrizations. The geometry of the group behind a game, not its presentation, sets the rates. Fixed games demand αlog⁡(1/ε)\alpha\log(1/\varepsilon)αlog(1/ε) for every α=12∑ilog⁡miqi\alpha=\frac12\sum_i\log_{m_i}q_iα=21​∑i​logmi​​qi​ with qi≥2q_i\ge2qi​≥2 a power of two dividing mim_imi​, a dense set containing all positive rationals and some transcendentals, such as 12log⁡62\frac12\log_6221​log6​2; a configuration-lamp game demands ε−1+o(1)\varepsilon^{-1+o(1)}ε−1+o(1); Pauli lamps on the points of Houghton's three rays give demand between ε−0.0690\varepsilon^{-0.0690}ε−0.0690 and ε−1/4\varepsilon^{-1/4}ε−1/4. If group relations hold exactly and Alice matches Bob to error eee, demand counts qubits addressable by short words: Θ(1/e)\Theta(1/e)Θ(1/e), Θ(e−k)\Theta(e^{-k})Θ(e−k) for integers k≥1k\ge1k≥1, or 2Θ(1/e)2^{\Theta(1/e)}2Θ(1/e). Conditional on our attainment and tail bounds, the I3322I_{3322}I3322​ optimum needs bounded usable entanglement.
A quantum system of any fixed dimension can be prepared in a continuum of states, yet it cannot be used to transmit an unlimited amount of classical information. Similarly, the correlations observed between measurement outcomes on separate parts of a shared quantum system can be stronger than classical correlations, but they cannot transmit information. These fundamental limitations suggest that the statistics observed from quantum communication and quantum correlations may admit a simulation using a finite amount of classical communication. This expectation is confirmed in the smallest nontrivial quantum dimension, with two classical bits being necessary and sufficient to exactly simulate qubit communication and all correlations between qubits. Despite significant efforts during the previous decades, this remained the only solved case. Here we resolve both problems for every quantum dimension. The solution reveals an unexpected qualitative transition starting at dimension four: no finite amount of classical communication can exactly simulate ququart communication nor all quantum correlations of two entangled ququarts, even with unlimited shared randomness. One might have expected this transition, if it existed, to appear already for qutrits. Instead, we construct an explicit protocol that exactly simulates qutrit communication using 357357357 classical bits, and consequently, all correlations of two entangled qutrits.
A bipartite perfect quantum strategy (BPQS) allows two players who cannot communicate with each other to always win a nonlocal game. BPQSs are rare but fundamental in light of some recent results in quantum information, computation, and foundations. A more than 40-year-old open problem is how many inputs (measurement settings) a BPQS requires. A related problem is how many inputs are needed if, in addition, the quantum system has minimum dimension. A third, apparently unrelated, problem is what is the connection between BPQSs and state-independent contextuality, which inspired the first BPQSs. Here, we solve the third problem: we prove that every BPQS defines a Kochen-Specker set. We use this result to identify the BPQS with the smallest number of inputs, both in the general case and in the case of minimum dimension, and solve some related problems. We conjecture that the BPQSs presented here are the solutions to the first two problems.
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.
Preparation contextuality is often manifested operationally through a quantitative advantage over preparation-noncontextual models in information-processing tasks, yet quantum theory typically falls short of perfect success. Here we introduce a parity-oblivious Hidden Matching task that instead yields an all-vs-nothing manifestation of preparation contextuality. Alice encodes an nnn-bit string so that her message reveals no information about any input parity other than the two-bit parities. Bob, given a perfect matching on the input positions, must output an edge of the matching together with the parity of its two bits. A quantum protocol using a single ⌈log⁡2n⌉\lceil\log_2 n\rceil⌈log2​n⌉-qubit message satisfies the parity-obliviousness constraint and succeeds with certainty. We prove that no preparation-noncontextual model achieves perfect success for any even n≥6n\ge6n≥6. The result holds for arbitrary ontic state spaces and assumes neither outcome determinism nor measurement noncontextuality. For n=6n=6n=6 and n=8n=8n=8, the optimal noncontextual success probabilities are 4/54/54/5 and 3/43/43/4, respectively, while asymptotically the optimal noncontextual success probability is 1/2+Θ(1/n)1/2+Θ(1/\sqrt n)1/2+Θ(1/n​). Our asymptotic upper bound follows from a Fourier-analytic sum rule derived via hypercontractivity on the Boolean hypercube. The resulting separation is qualitative rather than merely quantitative: quantum theory achieves perfect success, whereas preparation-noncontextual models cannot. We aslo show that at n=8n=8n=8 the noncontextual bound remains 3/43/43/4 even when Bob is restricted to just suitable 444 of the 105105105 possible perfect matchings, bringing the effect within experimental reach.
A perfect strategy is one that allows the mutually in-communicated players of a nonlocal game to win every trial of the game. Perfect strategies are basic tools for some fundamental results in quantum computation and crucial resources for some applications in quantum information. Here, we address the problem of producing qudit-qudit perfect quantum strategies with a small number of settings. For that, we exploit a recent result showing that any perfect quantum strategy induces a Kochen-Specker set. We identify a family of KS sets in even dimension d≥6d \ge 6d≥6 that, for many dimensions, require the smallest number of orthogonal bases known: d+1d+1d+1. This family was only defined for some ddd. We first extend the family to infinitely many more dimensions. Then, we show the optimal way to use each of these sets to produce a bipartite perfect strategy with minimum input cardinality. As a result, we present a family of perfect quantum strategies in any (2,d−1,d)(2,d-1,d)(2,d−1,d) Bell scenario, with d=2kpmd = 2^kp^md=2kpm for ppp prime, m≥k≥0m \geq k \geq 0m≥k≥0 (excluding m=k=0m=k=0m=k=0), d=8pd = 8pd=8p for p≥19p \geq 19p≥19, d=kpd=kpd=kp for p>((k−2)2k−2)2p > ((k-2)2^{k-2})^2p>((k−2)2k−2)2 whenever there exists a Hadamard matrix of order kkk, other sporadic examples, as well as a recursive construction that produces perfect quantum strategies for infinitely many dimensions ddd from any dimension d′d'd′ with a perfect quantum strategy. We identify their associated Bell inequalities and prove that they are not tight, which provides a second counterexample to a conjecture of 2007.