  The Fourier expansion of the loss function in variational quantum algorithms
(VQA) contains a wealth of information, yet is generally hard to access. We
focus on the class of variational circuits, where constant gates are Clifford
gates and parameterized gates are generated by Pauli operators, which covers
most practical cases while allowing much control thanks to the properties of
stabilizer circuits. We give a classical algorithm that, for an $N$-qubit
circuit and a single Pauli observable, computes coefficients of all
trigonometric monomials up to a degree $m$ in time bounded by
$\mathcal{O}(N2^m)$. Using the general structure and implementation of the
algorithm we reveal several novel aspects of Fourier expansions in
Clifford+Pauli VQA such as (i) reformulating the problem of computing the
Fourier series as an instance of multivariate boolean quadratic system (ii)
showing that the approximation given by a truncated Fourier expansion can be
quantified by the $L^2$ norm and evaluated dynamically (iii) tendency of
Fourier series to be rather sparse and Fourier coefficients to cluster together
(iv) possibility to compute the full Fourier series for circuits of non-trivial
sizes, featuring tens to hundreds of qubits and parametric gates.
