  We consider the sum-of-squares hierarchy of approximations for the problem of
minimizing a polynomial $f$ over the boolean hypercube
$\mathbb{B}^{n}=\{0,1\}^n$. This hierarchy provides for each integer $r \in
\mathbb{N}$ a lower bound $f_{(r)}$ on the minimum $f_{\min}$ of $f$, given by
the largest scalar $\lambda$ for which the polynomial $f - \lambda$ is a
sum-of-squares on $\mathbb{B}^{n}$ with degree at most $2r$. We analyze the
quality of these bounds by estimating the worst-case error $f_{\min} - f_{(r)}$
in terms of the least roots of the Krawtchouk polynomials. As a consequence,
for fixed $t \in [0, 1/2]$, we can show that this worst-case error in the
regime $r \approx t \cdot n$ is of the order $1/2 - \sqrt{t(1-t)}$ as $n$ tends
to $\infty$. Our proof combines classical Fourier analysis on $\mathbb{B}^{n}$
with the polynomial kernel technique and existing results on the extremal roots
of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies
on a connection between the hierarchy of lower bounds $f_{(r)}$ and another
hierarchy of upper bounds $f^{(r)}$, for which we are also able to establish
the same error analysis. Our analysis extends to the minimization of a
polynomial over the $q$-ary cube $(\mathbb{Z}/q\mathbb{Z})^{n}$.
