  In this work, we consider a new type of Fourier-like representation of
Boolean function $f\colon\{+1,-1\}^n\to\{+1,-1\}$ \[ f(x) =
\cos\left(\pi\sum_{S\subseteq[n]}\phi_S \prod_{i\in S} x_i\right). \] This
representation, which we call the periodic Fourier representation, of Boolean
function is closely related to a certain type of multipartite Bell inequalities
and non-adaptive measurement-based quantum computation with linear
side-processing ($\mathrm{NMQC}_\oplus$). The minimum number of non-zero
coefficients in the above representation, which we call the periodic Fourier
sparsity, is equal to the required number of qubits for the exact computation
of $f$ by $\mathrm{NMQC}_\oplus$. Periodic Fourier representations are not
unique, and can be directly obtained both from the Fourier representation and
the $\mathbb{F}_2$-polynomial representation. In this work, we first show that
Boolean functions related to $\mathbb{Z}/4\mathbb{Z}$-polynomial have small
periodic Fourier sparsities. Second, we show that the periodic Fourier sparsity
is at least $2^{\mathrm{deg}_{\mathbb{F}_2}(f)}-1$, which means that
$\mathrm{NMQC}_\oplus$ efficiently computes a Boolean function $f$ if and only
if $\mathbb{F}_2$-degree of $f$ is small. Furthermore, we show that any
symmetric Boolean function, e.g., $\mathsf{AND}_n$, $\mathsf{Mod}^3_n$,
$\mathsf{Maj}_n$, etc, can be exactly computed by depth-2
$\mathrm{NMQC}_\oplus$ using a polynomial number of qubits, that implies
exponential gaps between $\mathrm{NMQC}_\oplus$ and depth-2
$\mathrm{NMQC}_\oplus$.
