Q The Query Complexity Zoo
\(\mathrm{Adv}(f)\)

Positive-weights adversary bound

The original quantum adversary lower bound; all positive-weight variants coincide.

also written: Ambainis adversary, spectral adversary SA(f), unweighted/weighted adversary

Definition

$$\mathrm{Adv}(f) \;=\; \max_{\Gamma \ge 0,\ \Gamma \ne 0} \frac{\|\Gamma\|}{\max_i \|\Gamma \circ D_i\|},$$ the maximum over entrywise-nonnegative adversary matrices $\Gamma$ supported on pairs $(x,y)$ with $f(x)\ne f(y)$, where $D_i$ is the 0/1 matrix indicating $x_i \ne y_i$. Špalek-Szegedy showed the spectral, weighted, Kolmogorov and minimax adversary variants are all equal.

Basic facts

  • $\mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$.
  • Certificate complexity barrier: $\mathrm{Adv}(f) \le \sqrt{\mathrm{C}^0(f)\,\mathrm{C}^1(f)}$ [SpalekSzegedy06, Zhang05]. Note it is the product that is capped: element distinctness has $\mathrm{C}^1 = 2$ but $\mathrm{C}^0 = n$, so the barrier only says $\mathrm{Adv} = O(\sqrt n)$. It is the property-testing promise problems, with both certificate complexities $O(1)$, on which the positive adversary collapses to $\mathrm{Adv} = O(1)$ — \(\mathrm{COL}_n\), \(\mathrm{SIMON}_n\) [HoyerSpalek05].
  • Sharper: $\mathrm{Adv}(f) \le \sqrt{\mathrm{RC}^0(f)\,\mathrm{RC}^1(f)}$, the randomized-certificate version of the barrier [KulkarniTal16].
  • $\lambda(f) \le \mathrm{Adv}(f)$ [ABKRT21 via BSS03].
  • For total search problems $\mathrm{Adv}$ can be exponentially smaller than $\widetilde{\deg}$ [BenDavidKundu24search].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Adv}(f)\). “\(\mathrm{Adv}(f)\) in terms of it” is the pair with \(\mathrm{Adv}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\mathrm{Adv}(f)\) in terms of it It in terms of \(\mathrm{Adv}(f)\)
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound total1,1 partial1,1 relation1,1 derived open pair → total2,6 partial∞ relation∞ open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1 partial1,1 relation1,1 derived open pair → total2,6 partial∞ relation∞ derived open pair →
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm total1,1 partial1,? derived open pair → total2,6 partial∞ derived open pair →
\(\lambda(f)\) Spectral sensitivity total1.0654,4 partial∞ open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{C}(f)\) Certificate complexity total1,1 partial1,1 relation1,? open pair → total4,4 partial∞ relation∞ derived open pair →
\(\mathrm{fbs}(f)\) Fractional block sensitivity total1,1 partial1,? open pair → total2,2 partial2,2 open pair →

The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(\sqrt{n})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = \sqrt{n}$ and $\mathrm{Adv}^{\pm}(f) = \Theta(\sqrt{n})$ here.
AND total \(\Theta(\sqrt{n})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = \sqrt{n}$ and $\mathrm{Adv}^{\pm}(f) = \Theta(\sqrt{n})$ here.
PARITY total \(\Theta(n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
MAJORITY total \(\Theta(n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = (n+1)/2$ and $\mathrm{Adv}^{\pm}(f) = \Theta(n)$ here. The positive-weight adversary is already tight for majority, unlike for \(\mathrm{AND}_n \circ \mathrm{OR}_n\)-style functions where the certificate barrier bites.
Threshold total \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) putative Lower: Ambainis' unweighted adversary with $A$ the weight-$(k-1)$ inputs, $B$ the weight-$k$ inputs and Hamming distance $1$ gives $m = n-k+1$, $m' = k$, $\ell = \ell' = 1$ and hence $\sqrt{mm'/\ell\ell'} = \sqrt{k(n-k+1)}$. Upper: $\mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$, which is the same quantity. So the positive-weight adversary is already tight on the whole threshold family -- the certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1}$ is met with equality. Ambainis02
Symmetric functions (general) total \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) putative Squeezed: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = \Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)$ from the line above and $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$ the same quantity. The positive-weight adversary is therefore tight on the whole symmetric class; no symmetric function can witness the certificate barrier.
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with both ends $\Theta(n)$ here.
ODD-MAX-BIT total \(\Theta(\sqrt n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with both ends $\Theta(\sqrt n)$ here.
ADDRESS / multiplexer total \(\Theta(k)\) Between $\sqrt{\mathrm{bs}^0\,\mathrm{bs}^1} = k+1$ and $\mathrm{Q} = O(k)$.
Binary tree navigation total \(\Theta(k)\) Squeezed: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = \Theta(k)$ and $\mathrm{Adv}^{\pm}(f) = \Theta(k)$ here. Note $\sqrt{\mathrm{C}^0\mathrm{C}^1} = k$, so the certificate barrier is met with equality and the positive-weight adversary is already optimal.
TRIBES total \(\Theta(\sqrt n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with both ends $\Theta(\sqrt n)$ here.
AND-OR tree (depth 2) total \(\Theta(n) = \Theta(\sqrt N)\) Sandwiched: $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, with $\lambda = n$ and $\mathrm{Q} = \Theta(n)$ here.
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = \sqrt{N}$ and $\mathrm{Adv}^{\pm}(f) = \Theta(\sqrt{N})$ here.
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) Sandwiched: $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, with $\lambda = 2^d$ and $\mathrm{Q} = \Theta(2^d)$ here. The positive-weight adversary is therefore already optimal on recursive majority.
Kushilevitz's function (iterated) total \(\Omega(\sqrt N),\ O(N)\) Not pinned, for the same reason as \(\mathrm{Q}_{\varepsilon}(f)\): $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$ with $\lambda = \sqrt N$, and the certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = N$ is no better than the trivial ceiling here.
Rubinstein's function total \(\Theta(\sqrt N) = \Theta(n)\) Sandwiched: $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, with $\lambda = \sqrt N$ and $\mathrm{Q} = \Theta(\sqrt N)$ here. Note $\mathrm{Adv}^2 = \Theta(N) = \Theta(\mathrm{bs})$: the basic adversary bound is exactly tight against block sensitivity on Rubinstein's function.
Ambainis-Sun function total \(\Omega(\sqrt N),\ O(N^{3/4})\) putative Lower: $\mathrm{Adv} \ge \sqrt{\mathrm{bs}} = \Theta(\sqrt N)$ (\(\mathrm{bs}(f)\) vs \(\mathrm{Adv}(f)\)). Upper: $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = O(N^{3/4})$. The certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = O(N^{3/4})$ gives the same ceiling. Ambainis02
AND composed with NOT-EXACT-HALF total \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) Sandwiched: $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, with $\lambda = \Theta(n^{3/2})$ and $\mathrm{Q} = \Theta(n^{3/2})$ here. The certificate barrier $\sqrt{\mathrm{C}^0\mathrm{C}^1} = \sqrt{n\cdot(n^2/2+n)} = \Theta(n^{3/2})$ sits at exactly the same place, so the positive adversary is maximal for this function.
Meiburg's tournament-subcube function total \(\Omega(118.3^{\,d})\) putative Ambainis' basic adversary bound at a maximally block-sensitive input gives $\mathrm{Adv} \ge \sqrt{\mathrm{bs}}$ (\(\mathrm{bs}(f)\) vs \(\mathrm{Adv}(f)\)), i.e. $\ge 14011^{\,d/2}$. This is what supplies the $\mathrm{Q}$ entry, since $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$. Ambainis02
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $f_{2m,m}$: $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})=\widetilde O(n^{1/4})$. Note the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\widetilde O(\sqrt n)$ is the weaker of the two bounds here.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) The certificate-complexity barrier: $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\widetilde O(\sqrt n)$, while $\mathrm{Q}=\widetilde\Theta(n)$. So the positive-weight adversary is quadratically too weak to certify the quantum complexity of this function -- one of the cleanest total-function instances of that barrier, and the reason $\mathrm{Adv}^{\pm}$ rather than $\mathrm{Adv}$ appears in the row above.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\widetilde\Omega(n)$. The certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}$ gives no ceiling here because neither one-sided certificate complexity is bounded above, and $\lambda\le\mathrm{Adv}$ gives no floor because $\lambda$ is only bounded above. Ambainis02
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3}),\ \widetilde O(n^{3/2})\) Floor $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\widetilde\Omega(n^{4/3})$. Ceiling: the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\sqrt{\widetilde\Theta(n^2)\cdot\widetilde O(n)}=\widetilde O(n^{3/2})$. The strong asymmetry of the certificate complexities is what makes the barrier bite here. Ambainis02
Gilmer-Saks-Srinivasan functions total \(\Omega(\sqrt n),\ O(n^{3/2})\) Floor $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\Theta(n)$; ceiling the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\sqrt{\Theta(n^2)\cdot n}=O(n^{3/2})$. Ambainis02
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n^{3/4})\) Floor $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\widetilde\Theta(\sqrt n)$; ceiling the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\sqrt{\widetilde\Theta(n)\cdot\widetilde O(\sqrt n)}=\widetilde O(n^{3/4})$. Ambainis02
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6}),\ \widetilde O(\sqrt n)\) Floor $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\widetilde\Theta(n^{1/3})$; ceiling the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\sqrt{\widetilde\Theta(n^{2/3})\cdot\widetilde O(n^{1/3})}=\widetilde O(\sqrt n)$. Ambainis02
Ambainis' exact-quantum function total \(O(2.1213^d)\) Squeeze: $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})=\Theta(2.1213^d)$. The floor is $\mathrm{Adv}\ge\sqrt{\mathrm{bs}}=3^{d/2}$ (equally $\mathrm{Adv}\ge\lambda$), so the positive adversary is pinned between $1.7320^d$ and $2.1213^d$ here.
FORRELATION partial \(\Theta(1)\) A lower bound on $\mathrm{Q} = 1$.
k-FORRELATION partial \(O(k)\) The positive adversary is a lower bound on $\mathrm{Q} = \lceil k/2\rceil$, so it is $O(k)$ -- independent of $n$, and useless against $\mathrm{R} = \widetilde\Theta(n^{1-1/k})$.
Simon's problem partial \(O(1)\) Both certificate complexities are $O(1)$ under the promise -- exhibiting one colliding pair $x \ne y$ with $f(x)=f(y)$ settles the question -- so the positive adversary gives $O(1)$ against $\mathrm{Q} = \Theta(n)$. The largest known gap between $\mathrm{Adv}$ and $\mathrm{Q}$. HoyerSpalek05
Deutsch-Jozsa partial \(\Theta(1)\) A lower bound on $\mathrm{Q} = 1$.
Bernstein-Vazirani partial \(1\) Sandwiched: $1 \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = 1$.
Two-or-none search partial \(\Theta(\sqrt n)\) putative Take $X = \{0^n\}$, $Y = \{e_i + e_j\}$ and relate everything to everything. Then $m = \binom n2$, $m^{\prime} = 1$, $\ell = n-1$ (from $0^n$, the pairs differing at a fixed $i$ are those containing $i$) and $\ell^{\prime} = 1$, so Ambainis' bound gives $\Omega\big(\sqrt{mm^{\prime}/\ell\ell^{\prime}}\big) = \Omega(\sqrt n)$. The ceiling is $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = O(\sqrt n)$. Ambainis02
Marked bit partial \(\Theta(1)\) The certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = 1$, which holds for partial $f$ too. So the positive-weight adversary proves nothing about a function whose $\mathrm{Q}$ is $\Theta(\sqrt n)$ -- and the barrier is not the usual property-testing shape here, since a $1$-input and a $0$-input can be a Hamming distance $2$ apart. SpalekSzegedy06 Zhang05
Dense marked bit partial \(\Theta(1)\) The certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = 1$, and $\mathrm{Adv} \ge 1$. SpalekSzegedy06
Unstructured search (relation) relation \(\Theta(\sqrt n)\) The positive adversary is tight for unstructured search -- it is the original application of the method -- so $\mathrm{Adv} = \Theta(\sqrt n) = \Theta(\mathrm{Q})$. Contrast \(\mathrm{SIMON}_n\) and \(\mathrm{COL}_n\), where the positive adversary collapses to $O(1)$. BBBV97
FIND-1 under a density promise relation \(\Theta(1)\) A lower bound on $\mathrm{Q} = \Theta(1)$, and at least $1$.
Approximate Hamming weight relation \(\Theta(1)\) A lower bound on $\mathrm{Q} = \Theta(1)$, and at least $1$.
SearchCNF relation \(\Theta(1)\) A lower bound on $\mathrm{Q} = \Theta(1)$.
Gap-Majority partial \(O(\min(n, 1/\delta))\) $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(\min(n,1/\delta))$. The positive adversary is not obstructed here the way it is at \(\mathrm{COL}_n\) -- the certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \Theta(n)$ is not binding -- but no matching lower bound is recorded.
Gap-Majority at constant gap partial \(O(1)\) $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$.
Parity-labelled FIND-1 partial \(O(1)\) $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(1)$.
Approximate index partial \(\Theta(1)\) The certificate barrier is decisive: $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \Theta(1)$, an inequality that does hold for partial $f$ [SpalekSzegedy06, Zhang05]. So the positive adversary method proves nothing about this function, whatever $\mathrm{Q}$ turns out to be. Consistent with $\mathrm{bs} \le \mathrm{Adv}^2$, since $\mathrm{bs} = 1$. SpalekSzegedy06 Zhang05
Collision problem partial \(O(1)\) The certificate complexity barrier at its sharpest: a collision pair certifies a $2$-to-$1$ input with $2$ queries, and the promise means $O(1)$ queries also certify $1$-to-$1$-ness against the promise, so $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = O(1)$ while $\mathrm{Q} = \Theta(n^{1/3})$. No positive-weight adversary matrix can prove anything here -- this promise problem is the reason the negative-weights version had to be invented. HoyerSpalek05 SpalekSzegedy06
Element distinctness total \(O(\sqrt n)\) A colliding pair is a $2$-query certificate, but distinctness itself needs all $n$ values: with the convention $\mathrm{ED}_n = 1$ on all-distinct inputs, $\mathrm{C}^1 = n$ and $\mathrm{C}^0 = 2$. The barrier caps the product, so $\mathrm{Adv} \le \sqrt{2n} = O(\sqrt n)$ -- short of $\mathrm{Q} = \Theta(n^{2/3})$, but not the $O(1)$ that a one-sided reading of the barrier would suggest. See \(\mathrm{COL}_n\) for the case where the collapse really is total. SpalekSzegedy06 Zhang05 HoyerSpalek05
Ambainis-Belovs function partial \(O(1)\)· putative The positive-weight adversary is at most quadratic in the exact degree even for partial functions (Anshu, Ben-David and Kundu), so $\mathrm{Adv} = O(\deg^2) = O(1)$ while $\mathrm{Q} = \Omega(n^{1/3})$. This is exactly why the paper cannot use the positive adversary, and it makes the function a second \(\mathrm{Adv}(f)\)-vs-\(\mathrm{Q}_{\varepsilon}(f)\) witness alongside \(\mathrm{SIMON}_n\) and \(\mathrm{COL}_n\).
Yamakawa-Zhandry problem relation \(\mathrm{poly}(n)\) A lower bound on $\mathrm{Q} = \mathrm{poly}(n)$.
Surjectivity total \(O(n/\sqrt{\log n})\) putative The certificate-complexity barrier: $\mathrm{Adv}(f) \le \sqrt{\mathrm{C}^0(f)\,\mathrm{C}^1(f)}$ for total $f$, and here that is $\sqrt{N \cdot n/2} = \Theta(n/\sqrt{\log n})$. Only a $\sqrt{\log n}$ factor short of $\mathrm{Q}$, so unlike \(\mathrm{ED}_n\) and \(\mathrm{COL}_n\) the positive-weights adversary is not badly broken on surjectivity -- but it cannot reach $\mathrm{Q} = \tilde\Theta(n)$ either. A floor: $\mathrm{Adv} \ge \lambda \ge \sqrt{\mathrm{s}} = \Omega(\sqrt n)$.
$k$-distinctness total \(O(\sqrt n)\) putative The certificate barrier $\mathrm{Adv}(f) \le \sqrt{\mathrm{C}^0 \mathrm{C}^1} = \sqrt{nk} = O(\sqrt n)$ for constant $k$ -- so the positive-weights adversary cannot even reach the $\Omega(n^{2/3})$ of \(\mathrm{ED}_n\), let alone the true exponent. This is why every lower bound in the row above goes through the polynomial method or a compressed oracle.
Triangle finding total \(\Theta(m)\) putative Pinned exactly, and it is the barrier in the $\mathrm{C}^1$ note made into a value. Upper: $\mathrm{Adv}(f) \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \sqrt{3\binom m2} = O(m)$. Lower: restrict to $K_{\lceil m/2\rceil,\lfloor m/2\rfloor}$ with the $2\binom{\lfloor m/2\rfloor}{2} = \Theta(m^2)$ within-side pairs left free; adding any one of them closes a triangle, so the restriction is $\mathrm{OR}$ on $\Theta(m^2)$ variables, and $\mathrm{Adv}$ is monotone under restriction, giving $\mathrm{Adv} \ge \mathrm{Adv}(\mathrm{OR}_{\Theta(m^2)}) = \Omega(m)$. So the positive-weights adversary is stuck at the trivial bound for a structural reason, and any improvement on $\Omega(m)$ needs negative weights or a different method entirely.
Recursive Fourier sampling partial \(\Theta(2^{\ell}) \text{ for } g = g_{\mathrm{mod}3}\) Unusually, the positive-weight adversary is already tight. The $\Omega(2^{\ell})$ of [Aaronson03rfs, Thm. 5] is proved with Ambainis' weighted adversary, which has non-negative weights, so it is a lower bound on $\mathrm{Adv}$ itself and not merely on $\mathrm{Q}$; the ceiling is $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = O(\mathrm{Q}) \le O(\mathrm{Q}_{\mathrm{E}}) = O(2^{\ell})$. Contrast \(\mathrm{TRI}_m\), where the certificate-complexity barrier pins $\mathrm{Adv}$ strictly below $\mathrm{Q}$. Note the $\mathrm{bs} = 1$ entry: the polynomial method cannot even get started, while the adversary method is exactly optimal. Aaronson03rfs
Welded trees relation \(O(n)\) $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(n)$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). The positive-weight bound cannot be much smaller than $\mathrm{Q}=\Theta(n)$ here either, but no matching lower bound is recorded: the certificate structure is trivial ($\mathrm{C}=\Theta(1)$), which is exactly the regime where the positive adversary is weak.
Local search on the hypercube relation \(O(2^{n/3}n^{1/6})\) $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(2^{n/3}n^{1/6})$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). No lower bound is recorded here: the $\Omega(2^{n/3}n^{1/6})$ of [Aaronson06] and [Zhang09localsearch] is a relational adversary argument, which is the \(\mathrm{CA}(f)\) and \(\mathrm{Adv}^{\pm}(f)\) family rather than the positive-weight quantum bound.
Local search on the grid relation \(O(k^{d/3})\ (d \ge 6)\) $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(k^{d/3})$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). As on \(\mathrm{LS}(\{0,1\}^n)\), the known lower bound is a relational adversary argument rather than a positive-weight quantum one.
Fourier fishing relation \(\Theta(1)\) At most $\mathrm{Adv}^{\pm} = \Theta(1)$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), and at least $1$ since the problem is not trivial. The positive-weights bound is useless here for a reason that has nothing to do with the certificate barrier: $\mathrm{Q}$ itself is $1$.
Ordered search partial \(\Theta(1)\) putative Decision version, like the rest of the combinatorial column here. The certificate barrier applies: two queries $\{x_k = 0,\ x_{k+1} = 1\}$ pin the boundary, so $\mathrm{C}^0 = \mathrm{C}^1 = 2$ and $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = 2$. Against $\mathrm{Adv}^{\pm} = \widetilde\Theta(\log n)$ this is one of the cleanest positive-vs-negative-weight gaps in the zoo, and it is not the usual property-testing shape -- the promise is as far from a testing promise as it gets. For the $(n+1)$-valued reconstruction version the picture inverts: [ChildsLee08] compute the exact optimum of the adversary bound as $\tfrac1\pi\ln n + O(1)$, matching Hoyer-Neerbek-Shi, so the method is optimal there. The barrier is a theorem about Boolean output and does not survive the larger alphabet -- see \(\mathrm{Adv}(f)\) vs \(\mathrm{C}(f)\). ChildsLee08 SpalekSzegedy06
Tseitin search on an expander relation \(O(\sqrt n)\) $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=O(\sqrt n)$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)).
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$, with $\lambda = n/\sqrt2$ and $\mathrm{Q} = \Theta(n)$. Comfortably below the certificate barrier $\sqrt{\mathrm{C}^0\mathrm{C}^1} = \Theta(n)$, which is also $\Theta(n)$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$, with $\lambda = m^{3/2}$ and $\mathrm{Q} = \Theta(m^{3/2})$. The positive-weights adversary is tight here, and sits exactly at its certificate barrier $\sqrt{\mathrm{C}^0\mathrm{C}^1} = \sqrt{m^2\cdot m} = m^{3/2}$.
Sink of a tournament total \(\Omega(\sqrt m),\ O(m)\) Lower: $\lambda(f) \le \mathrm{Adv}(f)$ with $\lambda = \Theta(\sqrt m)$. Upper: $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \sqrt{m(m-1)} = \Theta(m)$, the certificate barrier, which here coincides with $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = O(m)$.
Scorpion graphs total \(\Omega(\sqrt m),\ O(m)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$, with $\lambda = \Omega(\sqrt m)$ below and $\mathrm{Q} = O(m)$ above. Note $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \Theta(m)$ anyway, so the positive adversary cannot prove more than $\Theta(m)$ here even in principle.
Graph connectivity total \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) The recorded $\Omega(m^{3/2})$ lower bound for \(\mathrm{Q}_{\varepsilon}(f)\) is an adversary bound [DHHM06], so $\mathrm{Adv} = \Omega(m^{3/2})$; and $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = O(m^{3/2})$. The positive adversary is exactly optimal here, and it meets its own certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \Theta(m^{3/2})$ -- connectivity is one of the cleanest total functions where that barrier is attained rather than obstructive. DHHM06