Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.06451

Fourier Entropy Bounds via Approximations

Manaswi Paraashar, Nitin Saurabh

Published Nov 4, 2026• 0 citations
arXivHTMLPDF

Abstract

We establish upper bounds on the Shannon entropy $\mathbb H(\widehat f^{\,2})$ of the Fourier distribution of Boolean functions. We prove that $$ \mathbb H(\widehat f^{\,2}) =O\!\left(\log\bigl(1+\|\widehat f\|_{1,1/3}\bigr)\right), $$ where $\|\widehat f\|_{1,1/3}$ denotes the minimum spectral norm of a pointwise $1/3$-approximant to $f$. This implies $\mathbb H(\widehat f^{\,2})=O(\mathsf R^\oplus(f))$, where $\mathsf R^\oplus(f)$ is bounded-error randomized parity-query complexity. We also bound Fourier entropy by the smaller of the two one-sided average unambiguous parity-certificate complexities. More generally, for any exact representation of indicator of $f$ as $\sum_C w_C\mathbf1_C$, with nonnegative weights and affine subspaces $C$, we prove $$ \mathbb H(\widehat f^{\,2}) =O\!\left(\sum_C w_C\,2^{-k_C}k_C\right), \qquad k_C=\operatorname{codim}(C). $$ The quantity on the right is the average conical junta degree of the representation. These results strengthen earlier bounds of (Arunachalam et al. 2021) by extending approximation-based entropy estimates to Shannon entropy and allowing one-sided and overlapping exact representations. The proofs use an entropy bound from a sequence of increasingly accurate approximants of $f$ with \emph{small} spectral norm. Our techniques also find an application in quantum communication complexity, where it improves a lower bound for the bounded-error quantum communication complexity of XOR functions.

Related papers

Fourier Growth of Communication Protocols for XOR Functions

Uma Girish, Makrand Sinha, Avishay Tal +1 more

The level-k $\ell_{1}$-Fourier weight of a Boolean function refers to the sum of absolute values of its level-k Fourier coefficients. Fourier growth refers to the growth of these weights as k grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations.In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs x and y to Alice and Bob). If a protocol $\mathcal C$ computes an XOR function, then $\mathcal{C}(x, y)$ is a function of the parity $x \oplus y$. This motivates us to analyze the XOR-fiber of the communication protocol $\mathcal{C}$, defined as $h(z):=\mathbb{E}_{\boldsymbol{x}, \boldsymbol{y}}[\mathcal{C}(\boldsymbol{x}, \boldsymbol{y}) \mid \boldsymbol{x} \oplus \boldsymbol{y}=z]$.We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate d bits. For the first level, we show a tight $O(\sqrt{d})$ bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an $d^{3 / 2} \cdot \operatorname{polylog}(n)$ bound, which improves the previous $O\left(d^{2}\right)$ bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem.Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.

arXiv:2307.13926•Annual Symposium on Foundations of Computer Science•Nov 6, 2023•7 citations

The Spectrum of Small DeMorgan Formulas.

Anat Ganor, Ilan Komargodski, Ran Raz

We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size s is concentrated on coefficients of degree up to O( √ s). These results have several applications that apply to any function f that can be computed by a deMorgan formula of size s. First, we get that f can be approximated (in L2-norm) with constant error by a polynomial of degree O( √ s). Second, we show an upper bound of O( √ s) on the average sensitivity of f . Our main result stems from a generalization of Khrapchenko’s bound [Khr71], that might be of independent interest, and some Fourier analysis on the Boolean cube. Previous works prove that any function f : {0, 1}n → {0, 1} that can be computed by a deMorgan formula of size s, can be approximated point-wise by a polynomial of degree O(s/2+o(1)) with constant point-wise error. We note that this result can be easily extended to have a polynomial of degree O(t ·s/2+o(1)) that approximates f with point-wise error 2−t, for any t > 0. This was shown in a long line of results in quantum complexity, including [BBC+01] and [FGG08, ACR+07, RS08, Rei09].

Electronic colloquium on computational complexity•Jan 1, 2012•4 citations

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

Zekun Ye

We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This improves the previous $O(k^{3/2}\log^2 k)$ upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity $Θ(nk)$ by combining known sparse-recovery and lower-bound results.

quant-pharXiv:2610.17648•Oct 14, 2026•0 citations

One-Way Communication Complexity of Partial XOR Functions

Vladimir V. Podolskii, Dmitrii Sluch

Boolean function $F(x,y)$ for $x,y \in \{0,1\}^n$ is an XOR function if $F(x,y)=f(x\oplus y)$ for some function $f$ on $n$ input bits, where $\oplus$ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known that deterministic communication complexity of $F$ is closely related to parity decision tree complexity of $f$. Montanaro and Osbourne (2009) observed that one-sided communication complexity $D_{cc}^{\rightarrow}(F)$ of $F$ is exactly equal to nonadaptive parity decision tree complexity $NADT^{\oplus}(f)$ of $f$. Hatami et al. (2018) showed that unrestricted communication complexity of $F$ is polynomially related to parity decision tree complexity of $f$. We initiate the studies of a similar connection for partial functions. We show that in case of one-sided communication complexity whether these measures are equal, depends on the number of undefined inputs of $f$. On the one hand, if $D_{cc}^{\rightarrow}(F)=t$ and $f$ is undefined on at most $O(\frac{2^{n-t}}{\sqrt{n-t}})$, then $NADT^{\oplus}(f)=t$. On the other hand, for a wide range of values of $D_{cc}^{\rightarrow}(F)$ and $NADT^{\oplus}(f)$ (from constant to $n-2$) we provide partial functions for which $D_{cc}^{\rightarrow}(F) < NADT^{\oplus}(f)$. In particular, we provide a function with an exponential gap between the two measures. Our separation results translate to the case of two-sided communication complexity as well, in particular showing that the result of Hatami et al. (2018) cannot be generalized to partial functions. Previous results for total functions heavily rely on Boolean Fourier analysis and the technique does not translate to partial functions. For the proofs of our results we build a linear algebraic framework instead. Separation results are proved through the reduction to covering codes.

arXiv:2310.20606•Leibniz international proceedings in informatics•Oct 31, 2023•1 citation

Lower Bounds for Quantum Communication Complexity

Hartmut Klauck

We prove lower bounds on the bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by Raz [Comput. Complexity, 5 (1995), pp. 205–221] to the quantum case. Applying this method, we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other lower bound methods based on the Fourier transform, notably showing that $\sqrt{\bar{s}(f)/\log n}$, for the average sensitivity $\bar{s}(f)$ of a function f, yields a lower bound on the bounded error quantum communication complexity of $f((x \wedge y)\oplus z)$, where x is a Boolean word held by Alice and $y,z$ are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, the only previously applied general lower bound method based on discrepancy yields bounds that are $O(\log n)$.

arXiv:quant-ph/0106160•SIAM Journal on Computing•Jan 1, 2007•127 citations

Lower bounds of quantum black-box complexity and degree of approximation polynomials by influence of Boolean variables

Yaoyun Shi

We prove that, to compute a Boolean function $f$ on $N$ variables with error probability $ε$, any quantum black-box algorithm has to query at least $\frac{1 - 2\sqrtε}{2} ρ_f N = \frac{1 - 2\sqrtε}{2} \bar{S}_f$ times, where $ρ_f$ is the average influence of variables in $f$, and $\bar{S}_f$ is the average sensitivity. It's interesting to contrast this result with the known lower bound of $Ω(\sqrt{S_f})$, where $S_f$ is the sensitivity of $f$. This lower bound is tight for some functions. We also show for any polynomial $\tilde{f}$ that approximates $f$ with error probability $ε$, $deg(\tilde{f}) \ge 1/4 (1 - \frac{3 ε}{1 + ε})^2 ρ_f N$. This bound can be better than previous known lower bound of $Ω(\sqrt{BS_f})$ for some functions. Our technique may be of intest itself: we apply Fourier analysis to functions mapping $\{0, 1\}^N$ to unit vectors in a Hilbert space. From this viewpoint, the state of the quantum computer at step $t$ can be written as $\sum_{s\in \{0, 1\}^N, |s| \le t} \hatϕ_s (-1)^ {s \cdot x}$, which is handy for lower bound analysis.

arXiv:quant-ph/9904107•Apr 29, 1999•7 citations
We establish upper bounds on the Shannon entropy H(f^ 2)\mathbb H(\widehat f^{\,2})H(f​2) of the Fourier distribution of Boolean functions. We prove that H(f^ 2)=O ⁣(log⁡(1+∥f^∥1,1/3)),\mathbb H(\widehat f^{\,2}) =O\!\left(\log\bigl(1+\|\widehat f\|_{1,1/3}\bigr)\right),H(f​2)=O(log(1+∥f​∥1,1/3​)), where ∥f^∥1,1/3\|\widehat f\|_{1,1/3}∥f​∥1,1/3​ denotes the minimum spectral norm of a pointwise 1/31/31/3-approximant to fff. This implies H(f^ 2)=O(R⊕(f))\mathbb H(\widehat f^{\,2})=O(\mathsf R^\oplus(f))H(f​2)=O(R⊕(f)), where R⊕(f)\mathsf R^\oplus(f)R⊕(f) is bounded-error randomized parity-query complexity. We also bound Fourier entropy by the smaller of the two one-sided average unambiguous parity-certificate complexities. More generally, for any exact representation of indicator of fff as ∑CwC1C\sum_C w_C\mathbf1_C∑C​wC​1C​, with nonnegative weights and affine subspaces CCC, we prove H(f^ 2)=O ⁣(∑CwC 2−kCkC),kC=codim⁡(C).\mathbb H(\widehat f^{\,2}) =O\!\left(\sum_C w_C\,2^{-k_C}k_C\right), \qquad k_C=\operatorname{codim}(C).H(f​2)=O(∑C​wC​2−kC​kC​),kC​=codim(C). The quantity on the right is the average conical junta degree of the representation. These results strengthen earlier bounds of (Arunachalam et al. 2021) by extending approximation-based entropy estimates to Shannon entropy and allowing one-sided and overlapping exact representations. The proofs use an entropy bound from a sequence of increasingly accurate approximants of fff with \emph{small} spectral norm. Our techniques also find an application in quantum communication complexity, where it improves a lower bound for the bounded-error quantum communication complexity of XOR functions.
The level-k ℓ1\ell_{1}ℓ1​-Fourier weight of a Boolean function refers to the sum of absolute values of its level-k Fourier coefficients. Fourier growth refers to the growth of these weights as k grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations.In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs x and y to Alice and Bob). If a protocol C\mathcal CC computes an XOR function, then C(x,y)\mathcal{C}(x, y)C(x,y) is a function of the parity x⊕yx \oplus yx⊕y. This motivates us to analyze the XOR-fiber of the communication protocol C\mathcal{C}C, defined as h(z):=Ex,y[C(x,y)∣x⊕y=z]h(z):=\mathbb{E}_{\boldsymbol{x}, \boldsymbol{y}}[\mathcal{C}(\boldsymbol{x}, \boldsymbol{y}) \mid \boldsymbol{x} \oplus \boldsymbol{y}=z]h(z):=Ex,y​[C(x,y)∣x⊕y=z].We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate d bits. For the first level, we show a tight O(d)O(\sqrt{d})O(d​) bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an d3/2⋅polylog⁡(n)d^{3 / 2} \cdot \operatorname{polylog}(n)d3/2⋅polylog(n) bound, which improves the previous O(d2)O\left(d^{2}\right)O(d2) bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem.Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.
We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size s is concentrated on coefficients of degree up to O( √ s). These results have several applications that apply to any function f that can be computed by a deMorgan formula of size s. First, we get that f can be approximated (in L2-norm) with constant error by a polynomial of degree O( √ s). Second, we show an upper bound of O( √ s) on the average sensitivity of f . Our main result stems from a generalization of Khrapchenko’s bound [Khr71], that might be of independent interest, and some Fourier analysis on the Boolean cube. Previous works prove that any function f : {0, 1}n → {0, 1} that can be computed by a deMorgan formula of size s, can be approximated point-wise by a polynomial of degree O(s/2+o(1)) with constant point-wise error. We note that this result can be easily extended to have a polynomial of degree O(t ·s/2+o(1)) that approximates f with point-wise error 2−t, for any t > 0. This was shown in a long line of results in quantum complexity, including [BBC+01] and [FGG08, ACR+07, RS08, Rei09].
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most kkk nonzero Fourier coefficients. We give a learner with near-optimal O~(k)\widetilde{O}(k)O(k) sample complexity independent of the input length nnn. The learner uses only separate measurements of individual examples. This improves the previous O(k3/2log⁡2k)O(k^{3/2}\log^2 k)O(k3/2log2k) upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity Θ(nk)Θ(nk)Θ(nk) by combining known sparse-recovery and lower-bound results.
Boolean function F(x,y)F(x,y)F(x,y) for x,y∈{0,1}nx,y \in \{0,1\}^nx,y∈{0,1}n is an XOR function if F(x,y)=f(x⊕y)F(x,y)=f(x\oplus y)F(x,y)=f(x⊕y) for some function fff on nnn input bits, where ⊕\oplus⊕ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known that deterministic communication complexity of FFF is closely related to parity decision tree complexity of fff. Montanaro and Osbourne (2009) observed that one-sided communication complexity Dcc→(F)D_{cc}^{\rightarrow}(F)Dcc→​(F) of FFF is exactly equal to nonadaptive parity decision tree complexity NADT⊕(f)NADT^{\oplus}(f)NADT⊕(f) of fff. Hatami et al. (2018) showed that unrestricted communication complexity of FFF is polynomially related to parity decision tree complexity of fff. We initiate the studies of a similar connection for partial functions. We show that in case of one-sided communication complexity whether these measures are equal, depends on the number of undefined inputs of fff. On the one hand, if Dcc→(F)=tD_{cc}^{\rightarrow}(F)=tDcc→​(F)=t and fff is undefined on at most O(2n−tn−t)O(\frac{2^{n-t}}{\sqrt{n-t}})O(n−t​2n−t​), then NADT⊕(f)=tNADT^{\oplus}(f)=tNADT⊕(f)=t. On the other hand, for a wide range of values of Dcc→(F)D_{cc}^{\rightarrow}(F)Dcc→​(F) and NADT⊕(f)NADT^{\oplus}(f)NADT⊕(f) (from constant to n−2n-2n−2) we provide partial functions for which Dcc→(F)<NADT⊕(f)D_{cc}^{\rightarrow}(F) < NADT^{\oplus}(f)Dcc→​(F)<NADT⊕(f). In particular, we provide a function with an exponential gap between the two measures. Our separation results translate to the case of two-sided communication complexity as well, in particular showing that the result of Hatami et al. (2018) cannot be generalized to partial functions. Previous results for total functions heavily rely on Boolean Fourier analysis and the technique does not translate to partial functions. For the proofs of our results we build a linear algebraic framework instead. Separation results are proved through the reduction to covering codes.
We prove lower bounds on the bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by Raz [Comput. Complexity, 5 (1995), pp. 205–221] to the quantum case. Applying this method, we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other lower bound methods based on the Fourier transform, notably showing that sˉ(f)/log⁡n\sqrt{\bar{s}(f)/\log n}sˉ(f)/logn​, for the average sensitivity sˉ(f)\bar{s}(f)sˉ(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f((x∧y)⊕z)f((x \wedge y)\oplus z)f((x∧y)⊕z), where x is a Boolean word held by Alice and y,zy,zy,z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, the only previously applied general lower bound method based on discrepancy yields bounds that are O(log⁡n)O(\log n)O(logn).
We prove that, to compute a Boolean function fff on NNN variables with error probability εεε, any quantum black-box algorithm has to query at least 1−2ε2ρfN=1−2ε2Sˉf\frac{1 - 2\sqrtε}{2} ρ_f N = \frac{1 - 2\sqrtε}{2} \bar{S}_f21−2ε​​ρf​N=21−2ε​​Sˉf​ times, where ρfρ_fρf​ is the average influence of variables in fff, and Sˉf\bar{S}_fSˉf​ is the average sensitivity. It's interesting to contrast this result with the known lower bound of Ω(Sf)Ω(\sqrt{S_f})Ω(Sf​​), where SfS_fSf​ is the sensitivity of fff. This lower bound is tight for some functions. We also show for any polynomial f~\tilde{f}f~​ that approximates fff with error probability εεε, deg(f~)≥1/4(1−3ε1+ε)2ρfNdeg(\tilde{f}) \ge 1/4 (1 - \frac{3 ε}{1 + ε})^2 ρ_f Ndeg(f~​)≥1/4(1−1+ε3ε​)2ρf​N. This bound can be better than previous known lower bound of Ω(BSf)Ω(\sqrt{BS_f})Ω(BSf​​) for some functions. Our technique may be of intest itself: we apply Fourier analysis to functions mapping {0,1}N\{0, 1\}^N{0,1}N to unit vectors in a Hilbert space. From this viewpoint, the state of the quantum computer at step ttt can be written as ∑s∈{0,1}N,∣s∣≤tϕ^s(−1)s⋅x\sum_{s\in \{0, 1\}^N, |s| \le t} \hatϕ_s (-1)^ {s \cdot x}∑s∈{0,1}N,∣s∣≤t​ϕ^​s​(−1)s⋅x, which is handy for lower bound analysis.