Fourier fishing
The largest separation there is: one quantum query against $\Omega(N/\log N)$ randomized ones -- impossible for a decision problem.
relation
relational
arity: a truth table $f:\{0,1\}^n \to \{-1,1\}$, so $N = 2^n$ input bits— also: Fourier sampling
Description
Write $\widehat f(z) = 2^{-n/2}\sum_x f(x)(-1)^{x\cdot z}$, so $\sum_z \widehat f(z)^2 = N$ and a typical $|\widehat f(z)|$ is $\Theta(1)$. Fourier fishing asks for any $z$ with $|\widehat f(z)| \ge 1$; the promise version restricts to $f$ on which one Hadamard-query-Hadamard round succeeds with probability at least $\mathrm{Succ}_Q - 1/n$, where $\mathrm{Succ}_Q = \tfrac{2}{\sqrt{2\pi}}\int_1^\infty x^2 e^{-x^2/2}dx \approx 0.801$, against $\mathrm{Succ}_R = \tfrac{2}{\sqrt{2\pi}}\int_1^\infty e^{-x^2/2}dx \approx 0.317$ for a uniformly random guess.
Its sibling Fourier sampling -- output a sample within total variation $\varepsilon$ of $D_f(y) = \widehat f(y)^2/N$ -- is a sampling problem, which the zoo's total/partial/relation vocabulary has no slot for; see the notes.
Formal definition
$\mathrm{FFish}_N = \{(f,z) : |\widehat f(z)| \ge 1\}$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(1\) | [AaronsonChen17, Lem. 6.3]: Hadamard, query, Hadamard, measure. It solves Fourier sampling exactly and fishing with probability $\ge 0.801 - 1/n$ on the promise. AaronsonChen17 AaronsonAmbainis18 |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Omega(N/\log N)\) | [AaronsonChen17, Thm. 6.4]: no $o(N/\log N)$-query randomized algorithm solves promise-fishing with probability $\mathrm{Succ}_R + \Omega(1)$. Note this is the relation; [AaronsonAmbainis18, Thm. 27] proves the analogous bound for the sampling problem and leaves the relation as a "plausible conjecture", which is what Aaronson-Chen discharge. AaronsonChen17 |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(N\) | Read everything. Nothing better is possible below $\Omega(N/\log N)$, and nothing better is known at all. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(1)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = 1$ here. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(N\) | Trivially, since $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D} = N$ and reading the whole truth table is non-adaptive. Adaptivity is worth nothing here, which is the mirror image of \(\mathrm{WT}_n\). |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(N)\) putative | Settled, unlike $\mathrm{R}$ itself: the $\log N$ window that is open for bounded error closes at zero error. Upper $\mathrm{R}_0 \le \mathrm{D} = N$. Lower: $\mathrm{C} = O(\mathrm{R}_0)$ (\(\mathrm{C}(f)\) vs \(\mathrm{R}_{0}(f)\)) -- fix the coins of a zero-error algorithm and the transcript it produces must force a valid answer, so it is a certificate -- and $\mathrm{C} \ge N/2$ by the row below. So $\mathrm{R}_0 \ge N/4$, and Fourier fishing separates $\mathrm{R}_0$ from $\mathrm{R}$ by at least the same $\log N$ that separates $\mathrm{R}$ from $\mathrm{D}$. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Omega(N/\log N),\ O(N)\) | Sandwiched between $\mathrm{R}_{\varepsilon} = \Omega(N/\log N)$ and $\mathrm{D}^{\mathrm{na}} = N$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Omega(N/\log N),\ O(N)\) | $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), so the expected-cost model does not escape the bound either. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Omega(N/\log N),\ O(N)\) | By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$. The maximising $\mu$ is the uniform distribution on truth tables: [AaronsonChen17, Thm. 6.4] proves its bound against a uniformly random $f$, so the statement is a $\mathrm{D}^\mu$ statement before it is an $\mathrm{R}$ statement. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(\Omega(N/\log N),\ O(N)\)· putative | Sharper than the generic $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R}$ would give. [AaronsonChen17, Thm. 6.4] argues against a uniformly random truth table, and the uniform distribution on $\{-1,1\}^N$ is a product distribution; the only caveat is that it is the uniform distribution conditioned on the promise, an event of probability $1-o(1)$, which is no longer literally a product. So the lower bound survives the restriction to product $\mu$ up to that conditioning. |
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(N)\) putative | At least $N/2$, so the one-query quantum answer is not even checkable cheaply. Fix $q$ cells; they contribute $S_{\mathrm{fix}}$ to $\widehat f(z) = N^{-1/2}\sum_x f(x)(-1)^{x\cdot z}$ with $|S_{\mathrm{fix}}| \le q/\sqrt N$, while the $N-q$ free cells contribute any value on the lattice $\{(N-q-2j)/\sqrt N\}$. If $q \le N/2$ then $(N-q)/\sqrt N \ge |S_{\mathrm{fix}}|$, so some completion has $|\widehat f(z)| \le 1/\sqrt N < 1$ and $z$ is not valid. The promise costs nothing: among uniformly random completions of the free cells $\widehat f(z)$ is essentially a standard Gaussian, so $\Pr[|\widehat f(z)|<1] = \Theta(1)$ while the promise holds with probability $1-o(1)$, and the two events intersect. Upper $\mathrm{C} \le \mathrm{D} = N$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^{\Theta(N)}\) putative | Every leaf is deep, so the tree is wide. A tree with $L$ leaves has one at depth $\le \log_2 L$ (Kraft), and a leaf at depth $t$ is a subcube on which one fixed $z$ is output, i.e. a certificate of size $t$; by the $\mathrm{C}$ row every certificate has size $\ge N/2$, so $\log_2 L \ge N/2$. Upper: the complete tree, $2^N$ leaves. Contrast $\mathrm{Q} = 1$: this is a $2^{\Omega(N)}$-versus-one-query gap, far past the $\mathrm{Q}_{2/5} = O(\sqrt{\mathrm{DTsize}})$ ceiling (\(\mathrm{DTsize}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), which of course only bounds $\mathrm{Q}$ from above. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(\Omega(N/\log N),\ O(N)\) putative | A depth-$d$ decision tree of rank $r$ has at most $\sum_{i \le r}\binom di \le (d+1)^r$ leaves [EhrenfeuchtHaussler89]. Here $d \le N$ and, by the $\mathrm{DTsize}$ row, every tree has at least $2^{N/2}$ leaves, so $(N+1)^r \ge 2^{N/2}$ and $r = \Omega(N/\log N)$. Upper: $\mathrm{rank} \le \mathrm{D} = N$ (\(\mathrm{rank}(f)\) vs \(\mathrm{D}(f)\)). Note that the whole $\log N$ of the window is the crudeness of $(d+1)^r$, not any slack in the certificate bound. EhrenfeuchtHaussler89 |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Omega(N/\log N),\ O(N)\) | Only the generic $\mathrm{R} \le \mathrm{psD} \le \mathrm{D}$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and the window is the same $\log N$ that is open for $\mathrm{R}$. Pseudo-determinism cannot help much here because $\mathrm{R}_0 = \Theta(N)$ already pins the top of the range. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\tilde\Theta(N)\) | Between $\mathrm{R} = \Omega(N/\log N)$ and $O(\mathrm{R}\log \mathrm{R}) = O(N\log N)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Theta(1)\)· | Still constant: $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) reads $O(1)$ at $\mathrm{Q} = 1$, and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = 1$. So the largest known relational speedup is not an artefact of a noiseless oracle. Medium confidence because the generic simulation is stated asymptotically and the constant-$\mathrm{Q}$ case needs the $O(\mathrm{Q})$ form of it. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\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$. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(1)\)· | Equal to $\mathrm{Adv}^{\pm} = \Theta(1)$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). Medium confidence only because $\gamma_2$ is listed as partially defined on relations. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(1)\)· | Between $\mathrm{Adv}^{\pm} = \Theta(1)$, which it dominates, and $\mathrm{Q} = 1$, which it is below. Same definedness caveat as $\gamma_2$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(\Theta(N)\) putative | Not just the worst input: every input is expensive. Certifying the answer $z$ means forcing $|\sum_x f(x)(-1)^{x\cdot z}|\ge\sqrt N$, and the unread cells can contribute $-(N-|S|)$ to that sum, so a certificate of size $|S|$ forces nothing unless $|S|\ge(N+\sqrt N)/2$. Hence $\mathrm{C}_{\min}\ge N/2$, matching $\mathrm{C}=\Theta(N)$. |
| \(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity | \(\Omega(\log N),\ O(N)\) putative | Upper: $\mathrm{D}^{\oplus}\le\mathrm{D}=N$. Lower: answer counting. For each $z$ the truth table $f=\chi_z$ has $z$ as its only valid answer, so a tree needs at least $N$ leaves and hence depth $\ge\log_2 N$. Whether parity queries actually help is open -- a parity of truth-table cells is not a Fourier coefficient. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(O(N)\) | $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon\le2\,\mathrm{D}=2N$ [JainKlauck10], stated for relations. The partition bound is a lower-bound technique for $\mathrm{R}$, so the recorded $\mathrm{R}=\Omega(N/\log N)$ says nothing about it from below. JainKlauck10 |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(O(N)\) | $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon=O(N)$ [JainKlauck10]. JainKlauck10 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(O(N)\) | $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon\le\mathrm{D}=N$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting). |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\Theta(1)\) | $1\le\mathrm{PostQ}\le\mathrm{Q}=1$: one Fourier sample already solves the problem, and no problem with a nonconstant answer is solved with zero queries. Post-selection has nothing left to buy -- the interest of this family is entirely on the classical side. |
Separations its values prove — computed, not recorded
Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 24 in total, strongest first.
-
\(\mathrm{D}^{\mathrm{prod}}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{prod}}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Q}_{\varepsilon}(f) = 1\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}^{\mathrm{rob}}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Q}^{\mathrm{rob}}(f) = \Theta(1)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Adv}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Omega(N/\log N)\) against \(\mathrm{Adv}(f) = \Theta(1)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Adv}^{\pm}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Adv}^{\pm}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{prod}}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}^{\mathrm{rob}}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{prod}}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Q}^{\mathrm{rob}}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Q}_{\varepsilon}(f) = 1\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Adv}^{\pm}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Omega(N/\log N)\) against \(\mathrm{Adv}^{\pm}(f) = \Theta(1)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Adv}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Adv}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{prod}}(f_n) \to \infty \ \text{ while } \ \mathrm{Adv}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{prod}}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Adv}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Adv}^{\pm}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Adv}^{\pm}(f) = \Theta(1)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Omega(N/\log N)\) against \(\mathrm{Q}_{\varepsilon}(f) = 1\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}^{\mathrm{rob}}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Q}^{\mathrm{rob}}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{prod}}(f_n) \to \infty \ \text{ while } \ \mathrm{Adv}^{\pm}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{prod}}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Adv}^{\pm}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Adv}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Omega(N/\log N),\ O(N)\) against \(\mathrm{Adv}(f) = \Theta(1)\)
… and 10 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
One quantum query against $\Omega(N/\log N)$ classical ones. For a partial decision problem this is impossible: $\mathrm{Q}(f) = k$ forces $\mathrm{R}(f) = O(N^{1-1/2k})$ [AaronsonAmbainis18], so at $\mathrm{Q}=1$ the ceiling is $O(\sqrt N)$ -- attained by \(\mathrm{forr}\).
Notes
The sampling sibling is settled and even stronger. [AaronsonChen17, Thm. 6.8]
gives the optimal $\Omega(N)$ for Fourier sampling at some constant $\varepsilon$,
and Thm. 6.7 gives $\Omega(N/\log N)$ for every
$\varepsilon < \mathrm{Succ}_Q - \mathrm{Succ}_R \approx 0.483$; [AaronsonAmbainis18,
Thm. 27] had $\Omega(N/\log N)$ at $\varepsilon = 0.01$. So sampling sits at
$\mathrm{R} = \Theta(N)$ against $\mathrm{Q} = 1$ -- the reason this problem is
quoted throughout the quantum-supremacy literature. If the zoo ever grows a
sampling setting, this is the motivating example.
Aaronson's Kolmogorov-complexity trick converts any sampling problem into a roughly equivalent relation, but it costs $\mathrm{Q} = 1 \to O(\log N)$, which is why the relation version had to be proved directly.
Open: whether $\mathrm{R}(\mathrm{FFish}_N)$ is $\Theta(N/\log N)$ or $\Theta(N)$ -- the $\Omega(N)$ proof is for sampling and does not transfer. Aaronson-Ambainis conjecture that $O(N/\log N)$ classical queries suffice for any one-query quantum sampling problem.