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

One-shot zero-error communication with normal entanglement is Σ⁰₂-complete

Seth Douglas, Nidhal Mghirbi

Published Nov 3, 2026• 1 citation
Publisher

Abstract

Can a finite classical channel require an infinite entangled resource to send a fixed number of messages without error? We classify the one-use feasibility problem for rational channels. With an arbitrary normal spatial resource it is Σ⁰₂-complete. The same classification holds when the resource must have finite marginal entropy. A separate channel admits a normal zero-error code, while every normal code achieving its specified message count has infinite marginal entropy on both sides. The proof extends Mančinska's finite-dimensional game-to-channel correspondence to trace-class operators. For the game's channel, a normal code attaining the clique bound (one message per local question) corresponds to perfect play with summable Schmidt amplitudes. Four successive constraints, each doubling a ratio of Schmidt weights, are critical and exclude such a code; five suffice for both reductions. As a corollary of Mančinska's finite-dimensional correspondence and MIP*=RE, we obtain Σ⁰₁-completeness for finite-dimensional resources. We also prove Π⁰₁-completeness for commuting operators. Our capacity statements are upper computability bounds; the hardness results concern one use.

DOI
10.5281/zenodo.23924868

Related papers

A trace costs one quantifier: the exact complexity of perfect play in nonlocal games

Seth Douglas, Nidhal Mghirbi

Given a finite nonlocal game, can the players win with certainty? We prove that the existence of a perfect normal spatial strategy is Σ⁰₂-complete, even when restricted to games of value one, so it cannot be decided even with an oracle for the halting problem. This is strictly harder than perfect play in the finite-dimensional and commuting-operator models, which are Σ⁰₁-complete and Π⁰₁-complete. Within the commuting model, the existence of a perfect normal strategy with a finite or semifinite von Neumann host is Σ⁰₂-complete, whereas for every fixed type III_λ subtype it has the same Π⁰₁-complete language as unrestricted commuting play. A trace thus costs one existential number quantifier: the hardness constructions force every perfect strategy to choose a finite clock period or a finite tree depth. The spatial classification persists when finite entanglement entropy is required, and it is formally verified in Lean, assuming only a special case of Tarski's decision theorem. We also prove Σ⁰₂-completeness for one-shot zero-error communication with normal entanglement, and construct a finite channel with zero-error codes of a given size every one of which needs infinite entanglement entropy.

arXiv:2611.10481•Nov 4, 2026•0 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•1 citation

Perfect play in a finite nonlocal game requires infinite entanglement entropy

Seth Douglas, Nidhal Mghirbi

How much infinity can a finite nonlocal game require? We construct a finite two-player game with classical questions, classical answers and a Boolean winning rule. It has a perfect strategy on a tensor product of separable Hilbert spaces. Every perfect normal spatial strategy contains, under local isometries, the same pure entangled state with infinite entropy. For mixed strategies, both marginal entropies are infinite and the pure state remains a tensor factor. Thus infinite dimension can be strengthened to infinite entropy without losing spatial attainment. The proof constructs a rational Bell functional whose perfect strategies contain a state with Catalan Schmidt multiplicities, and compiles it into Boolean tests. For either construction, the minimum marginal entropy at loss $\varepsilon$ is $\Theta(\log(1/\varepsilon))$. The lower bound holds for every normal spatial strategy, including mixed states and POVMs. It follows from polynomial decoding on the actual state and a finite-strip entropy estimate. Height and size cutoffs give the matching upper order. The sharp leading constant remains open.

•Nov 2, 2026•5 citations

Perfect play in a binary-scoring nonlocal game requires infinite dimension but only finite energy

Seth Douglas, Nidhal Mghirbi

A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile $D_\Gamma(\varepsilon)=10\log_2(1/\varepsilon)+O(\log\log(1/\varepsilon))$. Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, $5.362740278498934$ ebits, and least mean occupation, $275/18$ per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II$_1$ factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit $\Delta_* = \ln(7/6)-\ln(2)/7$. Type-II$_\infty$ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.

•Oct 29, 2026•0 citations

Perfect play in a binary-scoring nonlocal game requires infinite dimension but only finite energy

Seth Douglas, Nidhal Mghirbi

A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile $D_\Gamma(\varepsilon)=10\log_2(1/\varepsilon)+O(\log\log(1/\varepsilon))$. Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, $5.362740278498934$ ebits, and least mean occupation, $275/18$ per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II$_1$ factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit $\Delta_* = \ln(7/6)-\ln(2)/7$. Type-II$_\infty$ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.

•Oct 29, 2026•4 citations

Perfect play with spatial quantum strategies is Σ⁰₂-complete

Seth Douglas, Nidhal Mghirbi

When does a finite nonlocal game admit perfect spatial quantum play? We prove that this decision problem is complete for the second existential level of the arithmetical hierarchy. The same classification holds when a perfect strategy must have finite marginal entropy. Hardness persists among games whose finite-dimensional value is one and which have no finite-dimensional perfect strategy. A finite clock-phase order supplies the existential witness: normality forces a finite order on a nonzero sector, while the strategy chooses the order. For the upper bound, we normalize the largest Schmidt coefficient and use compact operator sandwiches. Fixing a lower bound on the largest Schmidt probability gives a co-recursively enumerable stratum. No computable bound selects a sufficient stratum for every game. Exact attainment of a rational Bell bound, of an unspecified supremum, and of a specified scalar value is also Sigma^0_2-complete. The hardness proof extends the modular-shift and rational-row toolkit of our earlier entropy-game paper to four calibrated bridges and a deterministic computation on rooted finite squares.

•Nov 3, 2026•4 citations
Can a finite classical channel require an infinite entangled resource to send a fixed number of messages without error? We classify the one-use feasibility problem for rational channels. With an arbitrary normal spatial resource it is Σ⁰₂-complete. The same classification holds when the resource must have finite marginal entropy. A separate channel admits a normal zero-error code, while every normal code achieving its specified message count has infinite marginal entropy on both sides. The proof extends Mančinska's finite-dimensional game-to-channel correspondence to trace-class operators. For the game's channel, a normal code attaining the clique bound (one message per local question) corresponds to perfect play with summable Schmidt amplitudes. Four successive constraints, each doubling a ratio of Schmidt weights, are critical and exclude such a code; five suffice for both reductions. As a corollary of Mančinska's finite-dimensional correspondence and MIP*=RE, we obtain Σ⁰₁-completeness for finite-dimensional resources. We also prove Π⁰₁-completeness for commuting operators. Our capacity statements are upper computability bounds; the hardness results concern one use.
Given a finite nonlocal game, can the players win with certainty? We prove that the existence of a perfect normal spatial strategy is Σ⁰₂-complete, even when restricted to games of value one, so it cannot be decided even with an oracle for the halting problem. This is strictly harder than perfect play in the finite-dimensional and commuting-operator models, which are Σ⁰₁-complete and Π⁰₁-complete. Within the commuting model, the existence of a perfect normal strategy with a finite or semifinite von Neumann host is Σ⁰₂-complete, whereas for every fixed type III_λ subtype it has the same Π⁰₁-complete language as unrestricted commuting play. A trace thus costs one existential number quantifier: the hardness constructions force every perfect strategy to choose a finite clock period or a finite tree depth. The spatial classification persists when finite entanglement entropy is required, and it is formally verified in Lean, assuming only a special case of Tarski's decision theorem. We also prove Σ⁰₂-completeness for one-shot zero-error communication with normal entanglement, and construct a finite channel with zero-error codes of a given size every one of which needs infinite entanglement entropy.
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.
How much infinity can a finite nonlocal game require? We construct a finite two-player game with classical questions, classical answers and a Boolean winning rule. It has a perfect strategy on a tensor product of separable Hilbert spaces. Every perfect normal spatial strategy contains, under local isometries, the same pure entangled state with infinite entropy. For mixed strategies, both marginal entropies are infinite and the pure state remains a tensor factor. Thus infinite dimension can be strengthened to infinite entropy without losing spatial attainment. The proof constructs a rational Bell functional whose perfect strategies contain a state with Catalan Schmidt multiplicities, and compiles it into Boolean tests. For either construction, the minimum marginal entropy at loss ε\varepsilonε is Θ(log⁡(1/ε))\Theta(\log(1/\varepsilon))Θ(log(1/ε)). The lower bound holds for every normal spatial strategy, including mixed states and POVMs. It follows from polynomial decoding on the actual state and a finite-strip entropy estimate. Height and size cutoffs give the matching upper order. The sharp leading constant remains open.
A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile DΓ(ε)=10log⁡2(1/ε)+O(log⁡log⁡(1/ε))D_\Gamma(\varepsilon)=10\log_2(1/\varepsilon)+O(\log\log(1/\varepsilon))DΓ​(ε)=10log2​(1/ε)+O(loglog(1/ε)). Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, 5.3627402784989345.3627402784989345.362740278498934 ebits, and least mean occupation, 275/18275/18275/18 per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II1_11​ factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit Δ∗=ln⁡(7/6)−ln⁡(2)/7\Delta_* = \ln(7/6)-\ln(2)/7Δ∗​=ln(7/6)−ln(2)/7. Type-II∞_\infty∞​ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.
A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile DΓ(ε)=10log⁡2(1/ε)+O(log⁡log⁡(1/ε))D_\Gamma(\varepsilon)=10\log_2(1/\varepsilon)+O(\log\log(1/\varepsilon))DΓ​(ε)=10log2​(1/ε)+O(loglog(1/ε)). Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, 5.3627402784989345.3627402784989345.362740278498934 ebits, and least mean occupation, 275/18275/18275/18 per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II1_11​ factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit Δ∗=ln⁡(7/6)−ln⁡(2)/7\Delta_* = \ln(7/6)-\ln(2)/7Δ∗​=ln(7/6)−ln(2)/7. Type-II∞_\infty∞​ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.
When does a finite nonlocal game admit perfect spatial quantum play? We prove that this decision problem is complete for the second existential level of the arithmetical hierarchy. The same classification holds when a perfect strategy must have finite marginal entropy. Hardness persists among games whose finite-dimensional value is one and which have no finite-dimensional perfect strategy. A finite clock-phase order supplies the existential witness: normality forces a finite order on a nonzero sector, while the strategy chooses the order. For the upper bound, we normalize the largest Schmidt coefficient and use compact operator sandwiches. Fixing a lower bound on the largest Schmidt probability gives a co-recursively enumerable stratum. No computable bound selects a sufficient stratum for every game. Exact attainment of a rational Bell bound, of an unspecified supremum, and of a specified scalar value is also Sigma^0_2-complete. The hardness proof extends the modular-shift and rational-row toolkit of our earlier entropy-game paper to four calibrated bridges and a deterministic computation on rooted finite squares.