Degree-Four Vector-Coordinate SoS Cannot Detect the MUB Upper Bound

Abstract

We prove a degree-four Sum-of-Squares lower bound for the standard vector-coordinate formulations of mutually unbiased bases. For every dimension $d$ and every proposed number $m$ of bases, we construct a degree-four pseudoexpectation satisfying the orthonormality constraints and the cross-unbiasedness constraints in the quartic equality formulation. The construction is expectation over $m$ independent Haar-random orthonormal bases. We also prove that the same pseudoexpectation satisfies the degree-four localizing constraints for the natural $2\times 2$ Hermitian semidefinite formulation of the cross-coherence inequalities. Consequently, degree-four vector-coordinate SoS cannot refute the existence of $m$ mutually unbiased bases, even when $m>d+1$. In particular, under the two vector-coordinate encodings explicitly described in Randomstrasse101 Open Problem 23, degree-four SoS cannot prove that seven mutually unbiased bases do not exist in ${\mathbb{C}}^6$. We contrast this with a centered projector-coordinate Gram formulation, where degree-four SoS already recovers the elementary upper bound $m\le d+1$, giving a simple separation between vector-coordinate and projector-coordinate degree-four relaxations.

12 pages