Query lower bound for Majority function using the quantum adversary method

Question

Using the quantum adversary lower bound technique, how can one calculate lower bound for Majority function $f:\{0,1\}^n \to \{0,1\}$ such that $f(x)=0$ if $|x|\leq n/2$ else $f(x)=1$, $|x|$ is the hamming weight of $x$)?

Answer 1

First, note that for functions that do not change their value upon permutation of their inputs—or in other words, functions that only depend on the Hamming weight $|x|$ of the input—it is known that the polynomial method tightly characterizes the query complexity, see Beals et al. In particular, this can be applied to the majority function $MAJ(x_1, \ldots, x_n)$ to obtain a tight $\Theta(n)$ bound of the query complexity.

As you asked specifically for a derivation of the $\Omega(n)$ lower bound via the adversary method, one can proceed as follows, following Ambainis’ initial paper about the adversary method (note that ever since, there were numerous further developments regarding the adversary method, see for instance Belov’s thesis and the references cited therein):

Theorem 2 in Ambainis' paper asserts that a lower bound can be shown if one can identify a hard distribution for the function $f$. Technically, this means to find two sets of inputs $X, Y\subseteq \{0,1\}^n$ that lead to different evaluations of the function (i.e., $f(x)\not= f(y)$ for all $x\in X$ and $y \in Y$) and a relation $R \subset X \times Y$ (which makes sure that the two distributions are close in a suitable sense), such that the following hold:

• For every $x\in X$, there are at least $m$ different $y \in Y$ such that $(x,y) \in R$,
• for every $y \in Y$, there are at least $m’$ different $x \in X$ such that $(x,y) \in R$,
• for every $x \in X$ and $i \in \{1, \ldots, n\}$, there are at most $\ell$ different $y\in Y$ such that $(x,y)\in R$ and $x_i\not= y_i$, and
• for every $y \in Y$ and $i \in \{1, \ldots, n\}$, there are at most $\ell’$ different $x\in X$ such that $(x,y)\in R$ and $x_i\not= y_i$.

If all this holds, then the query complexity of $f$ can be lower bounded by $\Omega\left(\sqrt{\frac{m m’}{\ell \ell’}}\right)$.

For $MAJ$, one can define an adversary as follows: let $X = \{x : |x|=n/2\}$, $Y = \{y : |y|=n/2+1\}$, and define the relation as $R = \{ (x,y) : |x \oplus y|=1\}$. Then clearly each fixed $x$ can be extended in at least $n/2$ ways to obtain an element in $Y$ that is related to $x$, i.e., $m\geq n/2$. Similarly, $m’ \geq n/2$. For a fixed $x$, and a fixed location $i\in \{1, \ldots, n\}$ there can be at most one bit-vector $y$ that has Hamming distance $1$ from $x$ (namely, this happens precisely when $i$ is not in the support of $x$), so $\ell=1$. By a similar argument, $\ell’=1$. Putting is all together yields the lower bound of $\Omega\left(\sqrt{\frac{n/2 \cdot n/2}{1 \cdot 1}}\right) = \Omega(n)$.