Olivier Lalonde, University of Waterloo
Quantum chromatic numbers, orthogonal representations, and the Hadamard’conjecture
Cameron, Montanaro, Newman, Severini and Winter gave a construction which shows that, for \(n \in \{2,4,8\}\) any graph G which admits a real \(n\)-dimensional orthogonal representation satisfies \(\chi_q(G) \leq n\).This result can be recast as the statement that \(\chi_q(S^{n-1}_\mathbb{R}) = n\) for these values of \(n\), where \(S^{n-1}_\mathbb{F}\) stands for the orthogonality graph of the unit sphere in \(\mathbb{F}^n\). We investigate possible extensions of their construction. We first show that their hypothesis that the orthogonal representation be real-valued is required by proving that \(\chi_q(S^{n-1}_\mathbb{C}) > n\) for all \(n \geq 3\). We also exhibit a finite subgraph \(G_{19}\) of \(S^{2}_\mathbb{C}\) and show that \(k+4 = \chi_q^{(1)}(G_{19} \vee K_k) >
\xi_{\mathbb{C}}(G_{19} \vee K_k) = k+3\) for all \(k\), so that the joins \(G_{19} \vee K_k\) form a family of finitary witnesses of the aforementioned separation for the special case of rank-one colorings. As a byproduct, we show that \(\xi_\mathbb{R}(G_{19}) = 4\), thereby separating the real and complex orthogonal ranks. For the case of the real sphere, we show that \(\chi_q(S^{n-1}_\mathbb{R}) > n\) whenever \(n \neq 2\) and \(n\) is not a multiple of 4. On the other hand, we show that \(\chi_q(S^{n-1}_\mathbb{R}) = n\) does does hold whenever a Hadamard matrix of order \(n\) exists. Hence, assuming the Hadamard conjecture, it follows that the CMNSW construction can be extended to real \(n\)-dimensional orthogonal representations if and only if \(n=2\) or \(n\) is a multiple of 4. Our method of proof involves showing the equivalence between the existence of such a construction and the ability to find a maximal code space for Clifford-algebraic errors given a clean ancilla, and we believe that the representation-theoretic techniques we use for tackling the latter problem could be of independent interest. It also follows from this equivalence that \(\chi^{(1)}_q(S^{n-1}_\mathbb{R}) = n\) if and only if \(n \in \{2,4,8\}\), thereby settling a conjecture of Zeng and Zhang.
QNC 1201