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.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/9904107Apr 29, 19991 citation

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

Hongwei Li, Li Yang

arXiv:1409.1416Quantum Information ProcessingMar 4, 201531 citations

On the Rational Degree of Boolean Functions and Applications

Vishnu Iyer, Siddhartha Jain, Robin Kothari +5 more

We study a natural complexity measure of Boolean functions known as the rational degree. Denoted $\textrm{rdeg}(f)$ , it is the minimal degree of a rational function that is equal to $f$ on the Boolean hypercube. For total functions $f$ , it is conjectured that $\textrm{rdeg}(f)$ is polynomially related to the Fourier degree of $f$ , $\textrm{deg}(f)$ . Towards this conjecture, we show that: - Symmetric functions have rational degree at least $Ω(\textrm{deg}(f))$ and unate functions have rational degree at least $\sqrt{\textrm{deg}(f)}$ . We observe that both of these lower bounds are asymptotically tight. - Read-once AC and TC formulae have rational degree at least $Ω(\sqrt{\textrm{deg}(f)})$ . If these formulae contain parity gates, we show a lower bound of $Ω(\textrm{deg}(f)^{1/2d})$ , where $d$ is the depth. - Almost every Boolean function on $n$ variables has rational degree at least $n/2 - O(\sqrt{n})$ . In contrast, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model. In addition, we show AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity.We study a natural complexity measure of Boolean functions known as the rational degree. Denoted $\textrm{rdeg}(f)$, it is the minimal degree of a rational function that is equal to $f$ on the Boolean hypercube. For total functions $f$, it is conjectured that $\textrm{rdeg}(f)$ is polynomially related to the Fourier degree of $f$, $\textrm{deg}(f)$. Towards this conjecture, we show that: - Symmetric functions have rational degree at least $Ω(\textrm{deg}(f))$ and unate functions have rational degree at least $\sqrt{\textrm{deg}(f)}$. We observe that both of these lower bounds are asymptotically tight. - Read-once AC and TC formulae have rational degree at least $Ω(\sqrt{\textrm{deg}(f)})$. If these formulae contain parity gates, we show a lower bound of $Ω(\textrm{deg}(f)^{1/2d})$, where $d$ is the depth. - Almost every Boolean function on $n$ variables has rational degree at least $n/2 - O(\sqrt{n})$. In contrast, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model. In addition, we show AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity.

arXiv:2310.08004Oct 12, 20230 citations

Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory

Rūsiņš Freivalds, Liva Garkaje

The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponential. On the other hand, we use a computerized exhaustive search to prove tightness of this bound.The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponential. On the other hand, we use a computerized exhaustive search to prove tightness of this bound.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)May 1, 20070 citations

Quantum Complexity of Boolean Matrix Multiplication and Related Problems

François Le Gall

Lecture notes in computer scienceJan 1, 20141 citation

We prove that, to compute a Boolean function

f

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.

We study a natural complexity measure of Boolean functions known as the rational degree. Denoted

\textrm{rdeg}(f)

, it is the minimal degree of a rational function that is equal to

f

on the Boolean hypercube. For total functions

f

, it is conjectured that

\textrm{rdeg}(f)

is polynomially related to the Fourier degree of

f

\textrm{deg}(f)

. Towards this conjecture, we show that: - Symmetric functions have rational degree at least

Ω(\textrm{deg}(f))

and unate functions have rational degree at least

\sqrt{\textrm{deg}(f)}

. We observe that both of these lower bounds are asymptotically tight. - Read-once AC and TC formulae have rational degree at least

Ω(\sqrt{\textrm{deg}(f)})

. If these formulae contain parity gates, we show a lower bound of

Ω(\textrm{deg}(f)^{1/2d})

, where

d

is the depth. - Almost every Boolean function on

n

variables has rational degree at least

n/2 - O(\sqrt{n})

. In contrast, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model. In addition, we show AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity.