Mutually unbiased bases as a commuting polynomial optimization problem

We consider the problem of mutually unbiased bases as a polynomial optimization problem over the reals. After greatly reducing it by using known symmetries, we then explore it using two methods, combining a number of optimization techniques. The first of these is a search for bases using Lagrange multipliers that converges rapidly in case of mutually unbiased bases' (MUB) existence, while the second combines a hierarchy of semidefinite programs with branch-and-bound techniques to perform a global search. We demonstrate that such an algorithm would eventually solve the open question in dimension six with finite memory, although it still remains intractable. We then investigate the idea that, to show the inexistence of bases, it often suffices to search for orthonormal vector sets of smaller sizes, rather than full bases (an idea sometimes referred to as ``constellations'' in the literature). We use our two methods to conjecture the minimum set sizes required to show infeasibility, as well as proving it via global search for dimension three . The fact that such subproblems seem to also be infeasible heavily reduces the number of variables, by 66% in the case of the open problem, potentially providing a significant speedup for other algorithms and bringing them into the realm of tractability.