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

$$C_{ef}=\mathbb E[\alpha_e\beta_f],$$

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

$$\prod_{e\ni v}s_e=(-1)^{b(v)}\quad \forall v.$$

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

$$A_1=Z,\qquad A_2=-\tfrac12Z+\tfrac{\sqrt3}{2}X,\qquad A_3=-\tfrac12Z-\tfrac{\sqrt3}{2}X,$$

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

$$\tfrac12\operatorname{Tr}(A_iA_j)=-\tfrac12\quad (i\ne j).$$

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,

$$\langle\Omega,A_e\otimes A_e^T\Omega\rangle=1,$$

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

$$\begin{pmatrix} 1&-1/2&-1/2\\ -1/2&1&-1/2\\ -1/2&-1/2&1 \end{pmatrix}.$$

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

$$s(e_i)=s(f_i)=:\varepsilon_i,\qquad s(h_1)=s(h_2)=1,$$

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,

$$\varepsilon_1\varepsilon_2+\varepsilon_1\varepsilon_3+\varepsilon_2\varepsilon_3\ge -1,$$

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.