Adversary Methods and Quantum Query Complexity — Examples

Let D={0,e_1,…,e_N}⊂{0,1}^N and f(x)=OR_N(x). For every i set v_{0,i}=N^{-1/4} and v_{e_j,i}=N^{1/4}δ_{ij} in the one-dimensional real space. If x=0,y=e_j, the only mismatch is coordinate j and the corresponding product is 1. If x=e_j,y=e_k with j≠k, the mismatch coordinates are j,k and both products vanish. Reverse pairs give the same real values. Thus all constraints in [F4] hold.

The cost on the unique 0-input is Σ_iN^{-1/2}=√N. On each 1-input e_j the cost is Σ_iN^{1/2}δ_{ij}=√N. Hence Adv±(OR_N)≤√N by [F4].

For the reverse bound, let Γ have Γ_{0,e_j}=Γ_{e_j,0}=1 for every j and all other entries zero. Its nonzero block is the all-ones 1×N matrix, whose singular value is √N, so ||Γ||=√N. For each i, Γ∘Δ_i retains only the two entries joining 0 and e_i and has norm 1. Therefore [F3] gives Adv±(OR_N)≥√N; equality follows.

Let f be the sorted four-bit function and define $f^{(1)}=f$ and $f^{(k+1)}=f\circ (f^{(k)},f^{(k)},f^{(k)},f^{(k)})$ on their natural block domains. Since $f$ is total on $\{0,1{\}}^4$ and nonconstant, induction shows every $f^{(k)}$ is total on $\{0,1{\}}^{4^k}$ and nonconstant: each outer bit string is realized by independently choosing a preimage of each bit under $f^{(k)}$, and outer strings with either $f$-value lift in the same way. Thus every composition domain is nonempty and both adversary bounds in [F2] apply. The signed matrix in [F1] and repeated composition in [F2] give ${\mathrm{Adv}}^{\pm }(f^{(k)})\ge {\mathrm{Adv}}^{\pm }(f{)}^k>(2.511486{)}^k$.

The base coordinate distributions in [F1] have mismatch overlap at least $\eta =2\mathrm{/}5$. If $P_X^{(k)}$ is a distribution over the $4^k$ input coordinates with cross-output overlap at least ${\eta }^k$, define for an input $X=(X_1,\dots ,X_4)$ to $f^{(k+1)}$ $P_X^{(k+1)}(j,r)=p_{\tilde{X}}(j)P_{X_j}^{(k)}(r),{\tilde{X}}_j=f^{(k)}(X_j)$. For opposite outputs of $f^{(k+1)}$, the outer strings $\tilde{X},\tilde{Y}$ have opposite $f$-values. For each $j$ with ${\tilde{X}}_j\mathrm{\ne }{\tilde{Y}}_j$, the inner pair $X_j,Y_j$ has opposite $f^{(k)}$-values and contributes overlap at least ${\eta }^k$. Summing those $j$ gives total overlap at least $\eta \cdot {\eta }^k={\eta }^{k+1}$; normalization follows by multiplying two probability distributions.

By induction and [F3], $\mathrm{Adv}(f^{(k)})\le {\eta }^{-k}=(5\mathrm{/}2{)}^k$. Since $2.511486>2.5$, the signed lower bound grows strictly faster than this nonnegative upper bound for every $k\ge 1$. Thus negative weights produce a strict adversary separation, and repeated composition amplifies it.