Periodic Fourier representation of boolean functions
share
In this work, we consider a new type of Fourier-like representation of boolean function f{+1,-1}^n→{+1,-1} f(x) = cos(π∑_S⊆[n]ϕ_S ∏_i∈ S x_i). This representation, which we call a 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 (NMQC_⊕). The minimum number of non-zero coefficients in the above representation, which we call a periodic Fourier sparsity, is equal to the number of qubits required for an exact computation of f by NMQC_⊕. Periodic Fourier representations are not unique, and can be directly obtained both from a Fourier representation and an F_2-polynomial representation. In this work, we first show that a boolean function related to Z/4Z-polynomial has a small periodic Fourier sparsity. From this construction, we obtain a cubic improvement on periodic Fourier sparsity against other periodic Fourier representations obtained by a Fourier representation and an F_2-polynomial representation. This cubic gap is currently the largest known gap. We also show that Mod^3_n and Maj_n have exponential periodic Fourier sparsities. Furthermore, we show that AND_n, Mod^3_n and Maj_n can be exactly computed by depth-2 NMQC_⊕ using polynomial number of qubits, that implies exponential gaps between NMQC_⊕ and depth-2 NMQC_⊕. For arbitrary given NMQC_⊕ using polynomial number of qubits, there is generally no AC^0_⊕ circuit whose output is in a support of the given NMQC_⊕ since AC^0_⊕ circuit cannot compute Maj_n.
READ FULL TEXT