Periodic Fourier representation of Boolean functions

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(\pi\sum_{S\subseteq[n]}\phi_S \prod_{i\in S} x_i). 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 NMQCp. 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 \NMQCp. Periodic Fourier representations are not unique, and can be directly obtained both from the Fourier representation and the F_2-polynomial representation. In this work, we first show that Boolean functions related to ZZZZ-polynomial have small periodic Fourier sparsities. Second, we show that the periodic Fourier sparsity is at least 2^{\deg_{\mathbb{F}_2}(f)}-1, which means that NMQCp efficiently computes a Boolean function $f$ if and only if F_2-degree of f is small. Furthermore, we show that any symmetric Boolean function, e.g., AND_n, Mod^3_n, Maj_n, etc, can be exactly computed by depth-2 NMQCp using a polynomial number of qubits, that implies exponential gaps between NMQCp and depth-2 NMQCp.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(\pi\sum_{S\subseteq[n]}\phi_S \prod_{i\in S} x_i). 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 NMQCp. 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 \NMQCp. Periodic Fourier representations are not unique, and can be directly obtained both from the Fourier representation and the F_2-polynomial representation. In this work, we first show that Boolean functions related to ZZZZ-polynomial have small periodic Fourier sparsities. Second, we show that the periodic Fourier sparsity is at least 2^{\deg_{\mathbb{F}_2}(f)}-1, which means that NMQCp efficiently computes a Boolean function $f$ if and only if F_2-degree of f is small. Furthermore, we show that any symmetric Boolean function, e.g., AND_n, Mod^3_n, Maj_n, etc, can be exactly computed by depth-2 NMQCp using a polynomial number of qubits, that implies exponential gaps between NMQCp and depth-2 NMQCp.

arXiv:1803.09947Quantum Information and ComputationMay 1, 20192 citations

Testing Booleanity and the Uncertainty Principle

Tom Gur, Omer Tamuz

Let f:{-1,1}^n -> R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in {-1,1}. We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most k terms must either be Boolean, or output values different than -1 or 1 for a fraction of at least 2/(k+2)^2 of its domain. It follows that given oracle access to f, together with the guarantee that its representation as a multilinear polynomial has at most k terms, one can test Booleanity using O(k^2) queries. We show an Ω(k) queries lower bound for this problem. Our proof crucially uses Hirschman's entropic version of Heisenberg's uncertainty principle.Let f:{-1,1}^n -> R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in {-1,1}. We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most k terms must either be Boolean, or output values different than -1 or 1 for a fraction of at least 2/(k+2)^2 of its domain. It follows that given oracle access to f, together with the guarantee that its representation as a multilinear polynomial has at most k terms, one can test Booleanity using O(k^2) queries. We show an Ω(k) queries lower bound for this problem. Our proof crucially uses Hirschman's entropic version of Heisenberg's uncertainty principle.

arXiv:1204.0944Chicago Journal of Theoretical Computer ScienceApr 4, 20124 citations

Boolean Algebra and Its Applications

Weng-Long Chang, Athanasios V. Vasilakos

Studies in big dataDec 21, 202024 citations

Parity Decision Tree Complexity is Greater Than Granularity

Anastasiya Chistopolskaya, Vladimir V. Podolskii

We prove a new lower bound on the parity decision tree complexity $\mathsf{D}_{\oplus}(f)$ of a Boolean function $f$ . Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$ . We show that $\mathsf{D}_{\oplus}(f)\geq k+1$ . This lower bound is an improvement of lower bounds through the sparsity of $f$ and through the degree of $f$ over $\mathbb{F}_2$ . Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority and recursive majority. For majority the complexity is $n - \mathsf{B}(n)+1$ , where $\mathsf{B}(n)$ is the number of ones in the binary representation of $n$ . For recursive majority the complexity is $\frac{n+1}{2}$ . Finally, we provide an example of a function for which our lower bound is not tight. Our results imply new lower bound of $n - \mathsf{B}(n)$ on the multiplicative complexity of majority.We prove a new lower bound on the parity decision tree complexity $\mathsf{D}_{\oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $\mathsf{D}_{\oplus}(f)\geq k+1$. This lower bound is an improvement of lower bounds through the sparsity of $f$ and through the degree of $f$ over $\mathbb{F}_2$. Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority and recursive majority. For majority the complexity is $n - \mathsf{B}(n)+1$, where $\mathsf{B}(n)$ is the number of ones in the binary representation of $n$. For recursive majority the complexity is $\frac{n+1}{2}$. Finally, we provide an example of a function for which our lower bound is not tight. Our results imply new lower bound of $n - \mathsf{B}(n)$ on the multiplicative complexity of majority.

arXiv:1810.08668Oct 19, 20184 citations

f

if and only if F_2-degree of f is small. Furthermore, we show that any symmetric Boolean function, e.g., AND_n, Mod^3_n, Maj_n, etc, can be exactly computed by depth-2 NMQCp using a polynomial number of qubits, that implies exponential gaps between NMQCp and depth-2 NMQCp.

We prove a new lower bound on the parity decision tree complexity

\mathsf{D}_{\oplus}(f)

of a Boolean function

f

. Namely, granularity of the Boolean function

f

is the smallest

k

such that all Fourier coefficients of

f

are integer multiples of

1/2^k

. We show that

\mathsf{D}_{\oplus}(f)\geq k+1

. This lower bound is an improvement of lower bounds through the sparsity of

f

and through the degree of

f

over

\mathbb{F}_2

. Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority and recursive majority. For majority the complexity is

n - \mathsf{B}(n)+1

, where

\mathsf{B}(n)

is the number of ones in the binary representation of

n

. For recursive majority the complexity is

\frac{n+1}{2}

. Finally, we provide an example of a function for which our lower bound is not tight. Our results imply new lower bound of

n - \mathsf{B}(n)

on the multiplicative complexity of majority.