The authors might have meant that cross-terms like $x \sqrt{1-x^2}$ can improve the ability of the quantum circuit to approximate $f$ beyond what could be done with just an $N$-th order polynomial.
Using the authors' notation we can write the input state as $\rho(x) = \sum_k a_k(x) P_k$ with $P_k \in \{I, X, Y, Z\}^N$. Specifically, $a_I(x) = 1$, $a_X(x) = x$, and $a_Z(x) = \sqrt{1-x^2}$, and we define $a_{PP'}(x) = a_P(x) a_{P'}(x)$. After applying a parameterized unitary $U(\theta)$ and measuring an arbitrary observable we'll have an output of the form
$$
\hat{f}(x) = \sum_{k } b_{k}(\theta) a_k(x) \tag{1}
$$
where $b_k(\theta)$ absorbs the components of the observable as well as the action of $U(\theta)$. For simplicity lets assume the coefficients $b_k$ can be arbitrary. An $N$-th order polynomial has the form
$$
g_N(x) = c_0 + c_1 x + c_2 x^2 + \cdots + c_N x^N \tag{2}
$$
If we take the case where $N=2$, $g_2(x) = c_0 + c_1 x + c_2 x^2$ but Eq. (1) contains terms like $a_{XZ}(x) = x\sqrt{1-x^2}$ and $a_{IZ} = \sqrt{1-x^2}$. Writing $b_k := b_k(\theta)$ and rewriting subscripts $I$, $X$, $XZ$, as integers for brevity, the circuit therefore produces functions of the form
\begin{align}
\hat{f}(x) &= b_0 + b_1 x + b_2 x^2 + b_3 \sqrt{1-x} + b_4 x\sqrt{1-x^2}\tag{3}
\\&= b_0 + b_1 x + b_2x^2 + b_3 \left(1 - \frac{1}{2} x^2 - \frac{1}{8} x^4 +\cdots \right) + b_4 \left(x - \frac{1}{2} x^3 - \frac{1}{8} x^5 +\cdots \right) \tag{4}
\\&= (b_0 + b_3) + (b_1 + b_4)x + \left(b_2 - \frac{b_3}{2}\right) x^2 -\frac{b_4}{2}x^3 - \frac{b_3}{8} x^4 + \cdots \tag{5}
\end{align}
where I've used the Maclaurin series expansion for $\sqrt{1-x^2}$. So this function is strictly more expressive than Eq. (2) as we can recover an arbitrary second order polynomial $g_2(x)$ by choosing $\theta$ such that $b_3=b_4=0$ and $b_k = c_k$ otherwise. Conversely, keeping these additional terms might greatly improve the convergence rate (with respect to $N$) of $\hat{f}$ for approximating certain functions compared to $g_N$ (e.g. when $f(x)$ contains terms like $\sqrt{1-x^2}$).
