Entangled Games on Tree-Like Question Graphs

When two provers share quantum entanglement, playing a game in parallel many times no longer behaves the way computer scientists expect. In a two-prover game, a referee sends each prover a question and checks their answers against a rule; if the best winning probability is $1-\epsilon$, repeating the game $k$ times in parallel should drive the chance of winning every round down toward $(1-\epsilon)^k$. Classical provers cannot avoid this decay, and it is the engine behind most hardness-of-approximation results. But entangled provers can measure a shared quantum state across all rounds at once, and known proofs break: for general games, no direct parallel repetition theorem with clean exponential decay exists at all, and even computing the entangled value of a game is NP-hard to approximate. The strongest positive results hold only for special game shapes — projection games, unique games — and, notably, for expander question graphs.

This proposal asks what happens on the structural opposite of expanders: question graphs that are tree-like, meaning they have small treewidth — informally, they can be cut apart into a tree of small pieces. Treewidth is the workhorse parameter of fixed-parameter tractability, the paradigm where a problem, though NP-hard in general, becomes solvable in time $f(k)\cdot n^{O(1)}$ once some structural quantity $k$ is small. Almost nothing is known about entangled games in this regime. We propose to establish, in one direction or the other, whether bounded treewidth (together with alphabet size) makes general entangled games tractable, and whether tree structure gives the first parallel repetition theorem for general — not just projection — entangled games. Either answer is a real contribution: a positive answer yields algorithms and amplification for a natural class of structured quantum games; a negative answer extends the reach of quantum hardness into the regime where classical constraint problems become easy.

Core Claim

The central object is a two-prover game $\mathcal{G}$ with question graph $G$ (vertices are questions, edges carry the verifier's predicates), alphabet size $q$, and entangled value $\mathrm{val}^*(\mathcal{G})$. We claim the pair $(t, q)$, where $t$ is the treewidth of $G$, is the right parameterization for entangled games, and we will prove one of two statements:

$$\text{Either } \quad \mathrm{val}^*(\mathcal{G}) \text{ is approximable within additive } \epsilon \text{ in } f(t,q,1/\epsilon)\cdot n^{O(1)} \text{ time,}$$

or the problem remains NP-hard (or $W[1]$-hard in $q$) even at constant treewidth — a dichotomy that, to our knowledge, nobody has established. The algorithmic route runs through the multiplicative relaxation $\mathrm{val}^*_+$ of A parallel repetition theorem for entangled projection games and Analytical Approach to Parallel Repetition, which is perfectly multiplicative under tensor products but is computed by a semidefinite program whose size grows with the whole game. Our hypothesis is that on a tree decomposition of $G$, the operator variables of the relaxation factorize bag by bag, so dynamic programming over the decomposition computes the relaxation — and, we conjecture, the true value — with only $f(t,q)$-sized pieces.

The repetition half of the claim targets the gap that makes general games hard: rounding from $\mathrm{val}^*_+$ back to $\mathrm{val}^*$. On expanders, A parallel repetition theorem for entangled projection games controls this gap via spectral mixing and quantum correlated sampling, giving decay $(1-\epsilon^c)^{k/2}$ with $c \le 12$, and the optimal $c=1$ on expanders. We aim to show that on tree-like graphs the gap can instead be controlled by a tree-decomposition argument, yielding for general (non-projection) games a decay of the form

$$\mathrm{val}^*(\mathcal{G}^{\otimes k}) \le \bigl(1 - \epsilon/h(t,q)\bigr)^{\Omega(k)}$$

for an explicit function $h$. This would be the first unmodified parallel repetition theorem for general entangled games under any structural restriction other than expansion — birthday repetition, the main current alternative, modifies the game by sending question sets A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs.

Research Program

Workstream one is the tractability dichotomy. The positive side needs a tensor-factorization lemma: if the question graph has treewidth $t$, any entangled strategy achieving value above a threshold admits a decomposition along the tree decomposition into per-bag operators of dimension bounded by a function of $t$ and $q$, so that a dynamic program over bags — in the spirit of classical constraint solving on bounded treewidth — can search the strategy space. The template for choosing the parameter carefully comes from parameterized complexity itself: On the Parameterized Complexity of Belief Revision shows that treewidth alone fails ($para$-coNP-hard) for a reasoning problem with global consistency constraints, while the number of shared variables succeeds — a caution we take seriously, and the reason we parameterize by $(t,q)$ jointly rather than treewidth alone. The negative side, if the lemma fails, would embed the hardness construction of Entangled Games Are Hard to Approximate into bounded-treewidth question graphs. Either way the dichotomy gets settled.

Workstream two is the repetition theorem. Perfect multiplicativity of $\mathrm{val}^*_+$ Analytical Approach to Parallel Repetition means the entire question is the rounding gap, and on tree-like graphs the natural tool is conditioning along the decomposition rather than spectral expansion. A crucial calibration point, which we confront rather than hide: the line game analyzed in No Strong Parallel Repetition with Entangled and Non-signaling Provers lives on a path — treewidth one — and its entangled value is $1-\Theta(1/n)$, remaining a positive constant even after $n^2$ repetitions. So treewidth cannot restore strong repetition (decay like $(1-\epsilon)^k$); the honest target is the weaker bound above, and the line game becomes our primary stress test: our theorem must be tight enough to reproduce its stalling behavior rather than predict decay that does not happen.

Workstream three is the empirical prototype described below, which exists to falsify the two theory claims early and cheaply.

Baselines

The do-nothing reference point is the unrepeated game: soundness error stays at $\epsilon$ no matter how the verifier samples, and for computation there is simply no algorithm — this is what any hardness-amplification or FPT result must beat. The strongest existing method for computing entangled values is the semidefinite-programming hierarchy applied to the full instance, in the tradition of Limitations of semidefinite programs for separable states and entangled games, which reports that the sum-of-squares hierarchy requires $\Omega(n)$ levels for separability and $\Omega(\log d/\mathrm{poly}\log\log d)$ levels for the $2\to4$ norm — the best characterization of how this baseline scales that exists in the file; no reported runtime result found on Lacuna for the SDP hierarchy on tree-like game instances, which is precisely the gap our experiments measure. Its strongest success story is Unique Games with Entangled Provers Are Easy, which uses an SDP plus quantum rounding to approximate unique entangled games within an additive $6\epsilon$ — the best polynomial-time guarantee on any entangled-game subclass. We will run this hierarchy as our main competitor on identical instances, identical accuracy targets, and an equal per-instance time budget, tuning the hierarchy level to the best achievable accuracy within that budget. For repetition, the baseline is the expander bound of A parallel repetition theorem for entangled projection games, which reports repeated value at most $(1-\epsilon^c)^{k/2}$ with $c\le12$ (and $c=1$ on expanders), plus the classical birthday-repetition decay $\exp(-\Omega(\epsilon kl/n))$ from A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs on dense instances. Finally, the key ablation isolates the treewidth ingredient: we run our full dynamic-programming pipeline with a trivial one-bag decomposition (effectively $t=n$), which degenerates to the flat SDP baseline — any speedup that survives this ablation is attributable to tree structure, not to implementation. A second abation drops the general-game rounding and restricts to projection games, separating the algorithmic contribution from the repetition-theoretic one.

Why not just…?

Why not just run flat SDP relaxations? Because for general games they are ruled out twice over: approximating the value within $1-\epsilon$ is NP-hard Entangled Games Are Hard to Approximate, which forbids polynomial-sized relaxations unless P = NP, and the failure is unconditional at the hierarchy level — Limitations of semidefinite programs for separable states and entangled games reports $\Omega(n)$ levels for separability. The honest caveat is that for unique games, the SDP plus rounding of Unique Games with Entangled Provers Are Easy already achieves additive $6\epsilon$, so on unique instances we expect parity, not victory; our experiments include unique instances precisely to show where the parameterized approach stops helping, and general instances to show where it separates.

Why not just make the question graph an expander? If one controls the verifier's design, this genuinely works: A parallel repetition theorem for entangled projection games gets optimal decay on expanders. But it answers a different question. Expanding the question distribution changes the game — inflating question sets and alphabets — and it says nothing about computing values of the many games whose structure is given and tree-like, a regime documented, for example, by Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures. And off expanders the same paper's exponent degrades to $c \le 12$ and the proof needs embezzlement-state machinery, so even for repetition the tree-like regime is not covered by expander techniques. If our experiments show expander-transformed games beat our direct algorithms at equal budget on tree-like instances, we will report that as a finding, but it cannot be a general answer for games one does not get to redesign.

Why not just transfer classical kernelization and repetition theorems? Classical data reduction has no reason to preserve quantum correlations. The line game of No Strong Parallel Repetition with Entangled and Non-signaling Provers is a path where every vertex has degree at most two and degrees are uniform — there are no "heavy hitters" of the kind A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation exploits to shrink kernels — yet entangled provers hold a constant winning probability across $n^2$ repetitions. Similarly, A three-player coherent state embezzlement game shows winning probability $1-\epsilon$ can require entanglement of local dimension $\Omega(\epsilon^{-\alpha})$ with $\alpha \approx 1/32$, a quantity invisible to any vertex-degree-based pruning. The transfer of classical parallel repetition fares no better: entangled provers measure across copies, which is exactly why Holenstein's $(1-\epsilon^2)^\ell$ bound is tight for line games with alphabet $q \ge 3$.

Proposed Experiments

We will build a prototype that computes $\mathrm{val}^*$ (and $\mathrm{val}^*_+$) by dynamic programming over tree decompositions, and test it on the benchmark games present in the file: CHSH, the Magic Square and GHZ-style games underlying the 3EMB construction of A three-player coherent state embezzlement game, and — most importantly — line-game instances of growing length, where the known value $1-\Theta(1/n)$ from No Strong Parallel Repetition with Entangled and Non-signaling Provers serves as ground truth. To generate tree-like instances at scale we will use the PACE competition solvers, treating treewidth computation with PACE Solver Description: Touiouidth and heuristic reduction with PACE Solver Description: DreyFVS to certify the treewidth of every test graph; no reported result found on Lacuna for PACE solver runtimes, so these serve only as decomposition tools, not as competitors. Three measurements are decisive. First, scaling: at fixed $(t,q)$, our runtime should grow polynomially in $n$ while the SDP hierarchy baseline, tuned within an equal budget, should need levels growing with $n$ — consistent with the $\Omega(n)$-level separability requirement reported in Limitations of semidefinite programs for separable states and entangled games. Second, values: agreement with the known line-game value and with flat-SDP values on small instances, within solver tolerance. Third, decay: for small games we compute $\mathrm{val}^*(\mathcal{G}^{\otimes k})$ for $k \le 4$ directly by SDP and check whether the measured decay tracks our tree-structure prediction, the expander baseline $(1-\epsilon^c)^{k/2}$ with $c\le12$, or the stalling regime — the gap $\mathrm{val}^*_+ - \mathrm{val}^*$ on tree-like versus expander instances is the quantity that tells us which.

Risks and Decisive Checks

The main technical risk is that the tensor-factorization lemma is false: global quantum consistency may not decompose along a tree, and the file gives two reasons for worry — the non-closure behavior of multipartite entangled strategies in A three-player coherent state embezzlement game, and the sum-of-squares separability gaps in Limitations of semidefinite programs for separable states and entangled games. We treat this risk as the point of the proposal rather than a defect: if the lemma fails, the failure itself becomes the NP-hardness-at-constant-treewidth side of the dichotomy, and the prototype experiments are designed to surface it within months, not years. The second risk is that the repetition bound, once proven, is quantitatively vacuous on interesting instances; the line-game stress test is the check, since a correct theorem must be tight enough to reproduce its documented stalling. The broader payoff, on either outcome, is a principled answer to where quantum hardness lives: expansion, the regime where the strongest repetition theorems hold, is exactly where classical structure is most global — and tree-like graphs, where all classical hard problems capitulate, are where we will learn whether quantum correlations can be tamed at all.