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

• 成果类型: Article
• 署名作者: Fang, Kun; Fawzi, Hamza
• 署名单位: University of Cambridge
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01537-7
• 发表日期: 2021
• 页码: 331-360
• 关键词: Optimization; separability; POLYNOMIALS; forms; zeros

摘要

We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of sum-of-squares relaxations. Exploiting the polynomial kernel technique, we obtain a quadratic improvement of the known convergence rate by Reznick and Doherty and Wehner. Specifically, we show that the rate of convergence is noworse than O(d(2)/l(2)) in the regime l = Omega(d) where l is the level of the hierarchy and d the dimension, solving a problem left open in the recent paper by de Klerk and 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. By exploiting the duality relation between sums of squares and the Doherty-Parrilo-Spedalieri hierarchy in quantum information theory, we show that our result generalizes to nonquadratic polynomials the convergence rates of Navascues, Owari and Plenio.