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.
The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |