Operator solutions of linear systems and small cancellation

Abstract

We show that if a graph has minimum vertex degree at least d and girth at least g, where (d, g) is (3, 6) or (4, 4), then the incidence system of the graph has a (possibly infinite-dimensional) quantum solution over ${\mathbb{Z}}_p$ for every choice of vertex weights and integer $p\ge 2$. In particular, there are linear systems over ${\mathbb{Z}}_p$, for $p$ an odd prime, such that the corresponding linear system nonlocal game has a perfect commuting-operator strategy, but no perfect classical strategy.

18 pages. V2 fixes an error in the main theorem (Theorem 1.3): the entries of A are now required to be coprime to p. Results for graph incidence systems are unchanged