2019

The sum-of-squares hierarchy on the sphere, and applications in quantum information theory

Fang, Kun, Fawzi, Hamza

Understand

We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of Sum-of-Squares (SOS) relaxations.

  • Exploiting the polynomial kernel technique, we obtain a quadratic improvement of the known convergence rate by Reznick and Doherty & Wehner.
  • Specifically, we show that the rate of convergence is no worse than $O(d^2/\ell^2)$ in the regime $\ell \geq \Omega(d)$ where $\ell$ is the level of the hierarchy and $d$ the dimension, solving a problem left open in the recent paper by de Klerk & Laurent (arXiv:1904.08828).
  • Importantly, our analysis also works for matrix-valued polynomials on the sphere which has applications in quantum information for the Best Separable State problem.

Reading the bibliography…