Convergence rates of Sum-of-Hermitian-Squares Hierarchies for the Pauli algebra

Moment/Sum-of-Hermitian-Squares relaxations for noncommutative polynomial optimization problems have become an important tool for analyzing problems within quantum theory. Despite their widespread success, little is known about their rate of convergence and, consequently, their accuracy. In this work, we develop explicit convergence rates for relaxations of noncommutative polynomial optimization problems generated from the Pauli algebra - covering applications to the ground state energy problem for n-qubit systems. In particular, we show that the rate of convergence can be bounded in terms of the smallest roots of a family of orthogonal polynomials known as Krawtchouk polynomials. Our result represents the first quantitative analysis of the rate of convergence for relaxations of noncommutative polynomial optimization problems.