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:1409.1416 · Quantum Information Processing

A quantum algorithm for approximating the influences of Boolean functions and its applications

Hongwei Li, Li Yang

Published Mar 4, 2015• 32 citations
arXivHTMLPDF
DOI
10.1007/s11128-015-0954-8

Related papers

On quantum algorithms

CleveRichard, EkertArtur, HendersonLea +2 more

Complexity•Sep 1, 1998•0 citations

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +2 more

The Total Influence ( Average Sensitivity ) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function, which we denote by I [ f ]. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of (1 ± ε ) by performing O (√ n I [ f ] poly(1/ ε )) queries. We also prove a lower bound of Ω (√ n log n · I [ f ]) on the query complexity of any constant factor approximation algorithm for this problem (which holds for I [ f ]= Ω (1)), hence showing that our algorithm is almost optimal in terms of its dependence on n . For general functions, we give a lower bound of Ω ( n I [ f ]), which matches the complexity of a simple sampling algorithm.

arXiv:1101.5345•ACM Transactions on Computation Theory•Nov 1, 2012•29 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

On quantum algorithms

Richard Cleve, ARTUR K. EKERT, Leah Henderson +2 more

Complexity•Sep 1, 1998•28 citations

Quantum Algorithms and Applications

Melinda Andrews, Joseph Stephen Dulny, Andrew N. Glaudell +6 more

•Sep 1, 2020•0 citations

Deterministic Approximate Counting for Degree-222 Polynomial Threshold Functions

De, Anindya, Diakonikolas, Ilias, Rocco A. Servedio

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates \[ \Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0] \] to within an additive $\pm \eps$ in time $\poly(n,2^{\poly(1/\eps)})$. Note that it is NP-hard to determine whether the above probability is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. This is the first deterministic algorithm for this counting problem in which the running time is polynomial in $n$ for $\eps= o(1)$. For "regular" polynomials $p$ (those in which no individual variable's influence is large compared to the sum of all $n$ variable influences) our algorithm runs in $\poly(n,1/\eps)$ time. The algorithm also runs in $\poly(n,1/\eps)$ time to approximate $\Pr_{x \sim N(0,1)^n}[p(x) \geq 0]$ to within an additive $\pm \eps$, for any degree-2 polynomial $p$. As an application of our counting result, we give a deterministic FPT multiplicative $(1 \pm \eps)$-approximation algorithm to approximate the $k$-th absolute moment $\E_{x \sim \{-1,1\}^n}[|p(x)^k|]$ of a degree-2 polynomial. The algorithm's running time is of the form $\poly(n) \cdot f(k,1/\eps)$.

arXiv:1311.7105•Nov 27, 2013•5 citations
The Total Influence ( Average Sensitivity ) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function, which we denote by I [ f ]. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of (1 ± ε ) by performing O (√ n I [ f ] poly(1/ ε )) queries. We also prove a lower bound of Ω (√ n log n · I [ f ]) on the query complexity of any constant factor approximation algorithm for this problem (which holds for I [ f ]= Ω (1)), hence showing that our algorithm is almost optimal in terms of its dependence on n . For general functions, we give a lower bound of Ω ( n I [ f ]), which matches the complexity of a simple sampling algorithm.
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.
We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-222 polynomial threshold function. Given a degree-2 input polynomial p(x1,…,xn)p(x_1,\dots,x_n)p(x1​,…,xn​) and a parameter $\eps > 0$, the algorithm approximates Pr⁡x∼{−1,1}n[p(x)≥0] \Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0] Prx∼{−1,1}n​[p(x)≥0] to within an additive $\pm \eps$ in time $\poly(n,2^{\poly(1/\eps)})$. Note that it is NP-hard to determine whether the above probability is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. This is the first deterministic algorithm for this counting problem in which the running time is polynomial in nnn for $\eps= o(1)$. For "regular" polynomials ppp (those in which no individual variable's influence is large compared to the sum of all nnn variable influences) our algorithm runs in $\poly(n,1/\eps)$ time. The algorithm also runs in $\poly(n,1/\eps)$ time to approximate Pr⁡x∼N(0,1)n[p(x)≥0]\Pr_{x \sim N(0,1)^n}[p(x) \geq 0]Prx∼N(0,1)n​[p(x)≥0] to within an additive $\pm \eps$, for any degree-2 polynomial ppp. As an application of our counting result, we give a deterministic FPT multiplicative $(1 \pm \eps)$-approximation algorithm to approximate the kkk-th absolute moment $\E_{x \sim \{-1,1\}^n}[|p(x)^k|]$ of a degree-2 polynomial. The algorithm's running time is of the form $\poly(n) \cdot f(k,1/\eps)$.