  We establish a link between stabilizer states, stabilizer rank, and
higher-order Fourier analysis -- a still-developing area of mathematics that
grew out of Gowers's celebrated Fourier-analytic proof of Szemer\'edi's theorem
\cite{gowers1998new}. We observe that $n$-qudit stabilizer states are so-called
nonclassical quadratic phase functions (defined on affine subspaces of
$\mathbb{F}_p^n$ where $p$ is the dimension of the qudit) which are fundamental
objects in higher-order Fourier analysis. This allows us to import tools from
this theory to analyze the stabilizer rank of quantum states. Quite recently,
in \cite{peleg2021lower} it was shown that the $n$-qubit magic state has
stabilizer rank $\Omega(n)$. Here we show that the qudit analog of the
$n$-qubit magic state has stabilizer rank $\Omega(n)$, generalizing their
result to qudits of any prime dimension. Our proof techniques use explicitly
tools from higher-order Fourier analysis. We believe this example motivates the
further exploration of applications of higher-order Fourier analysis in quantum
information theory.
