Forbidden graph minors, Arkhipov's theorem, and linear system games

NEW

Problem: Reconstructed conjecture: for every connected loopless multigraph $G$ with vertex colouring $b:V(G)\to\mathbb Z_2$, all perfect quantum strategies of the graph-incidence linear-system game $\mathcal G(G,b)$ have classical edge-correlation matrices iff $b$ has even parity, i.e. $\sum_{v\in V(G)}b(v)=0$. Here a perfect strategy’s edge-correlation matrix is

with $\alpha_e,\beta_f\in\{\pm1\}$, and “classical” means lying in the convex hull of matrices $ss^T$ coming from deterministic perfect edge assignments $s:E(G)\to\{\pm1\}$ satisfying

This formalizes the poster statement “all perfect strategies of $\mathcal G(G,b)$ have classical correlation matrices iff $b$ has even parity.” The literal wording “Can we find the minors?” is ambiguous, but the quoted conjectural characterization is the substantive mathematical claim.

Result: The conjecture is false, even non-vacuously with $G$ connected and $b\equiv0$.

Let $G$ have vertices $u_i,v_i$, $i=1,2,3$. Between $u_i$ and $v_i$ put two parallel edges $e_i,f_i$. Add bridge edges $h_1:v_1u_2$ and $h_2:v_2u_3$. Let $b\equiv0$. Then $G$ is connected and $b$ has even parity.

Define real self-adjoint unitaries on $\mathbb C^2$:

where $Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$, $X=\begin{pmatrix}0&1\\1&0\end{pmatrix}$. Then $A_i^2=I$ and

Use the maximally entangled state $\Omega=(|00\rangle+|11\rangle)/\sqrt2$. Assign observable $A_i$ to both $e_i$ and $f_i$, and $I$ to both bridges. At every vertex the incident observables commute and multiply to $I$, so the parity constraint $b=0$ is satisfied. Since the same real observable is used on both endpoints of each edge,

so the consistency test is won perfectly. Thus this is a perfect quantum strategy.

Its correlation submatrix on $e_1,e_2,e_3$ is

Now consider any deterministic perfect classical assignment. The vertex equations force

with arbitrary $\varepsilon_i\in\{\pm1\}$. Hence any classical correlation submatrix on $e_1,e_2,e_3$ has entries $r_{ij}=\mathbb E[\varepsilon_i\varepsilon_j]$. For every deterministic triple,

so every classical convex combination satisfies $r_{12}+r_{13}+r_{23}\ge -1$. The quantum matrix gives $-3/2$, contradiction.

Therefore $b$ can have even parity while a perfect quantum strategy has a nonclassical correlation matrix. The proposed parity characterization, and hence the corresponding parity-only forbidden-minor answer, is false.

Citation: Context and terminology: Paddock–Russo–Silverthorne–Slofstra, “Arkhipov’s theorem, graph minors, and linear system nonlocal games,” arXiv:2205.04645. The counterexample above is supplied here.