Periodic Fourier representation of Boolean functions

Abstract

In this work, we consider a new type of Fourier-like representation of Boolean function $f:\{+1,-1{\}}^n\to \{+1,-1\}$ \[ f(x) = \cos\left(π\sum_{S\subseteq[n]}ϕ_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}}_n^3$, ${\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 }$.

18 pages, 2 figures, 2 tables

References in corpus (2)

• Computational power of correlations
• The computational landscape of general physical theories