Q The Query Complexity Zoo
\(\mathrm{FFish}_N\)

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

MeasureValueNotes
\(\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.

… and 10 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses

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.