Fourier expansion in variational quantum algorithms

The Fourier expansion of the loss function in variational quantum algorithms (VQAs) 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 parametrized gates are generated by Pauli operators, which covers most practical cases while allowing much control due 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 O (N2^m). Using the general structure and implementation of the algorithm, we reveal several aspects of Fourier expansions in Clifford plus Pauli VQAs such as (i) reformulating the problem of computing the Fourier series as an instance of the 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) the tendency of Fourier series to be rather sparse and Fourier coefficients to cluster together, and (iv) the possibility to compute the full Fourier series for circuits of nontrivial sizes, featuring tens to hundreds of qubits and parametric gates.