Q The Query Complexity Zoo
\(\mathrm{forr}_k\)

k-FORRELATION

Optimal $\mathrm{Q}$-vs-$\mathrm{R}$ separation for every $k$: $\mathrm{Q}=\lceil k/2\rceil$, $\mathrm{R}=\widetilde\Theta(n^{1-1/k})$.

partial quantum arity: $kn$ bits

Description

The $k$-fold generalisation: given $x^1,\dots,x^k$, decide whether $\langle x^1, H x^2, H x^3, \dots\rangle$-style alternating Hadamard/pointwise-product composition is large.

Formal definition

$$\Phi_k(x^1,\dots,x^k) = \frac{1}{n}\,\mathbf{1}^{\!\top} D_{x^1} H D_{x^2} H \cdots H D_{x^k}\, \mathbf{1},$$ where $H$ is the normalised Hadamard transform and $D_{x}$ is the diagonal matrix with $x$ on the diagonal. Accept if $\Phi_k \ge$ a constant, reject if $|\Phi_k|$ is small.

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\lceil k/2\rceil\) AaronsonAmbainis18
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\widetilde\Theta\!\big(n^{1-1/k}\big)\) Lower bound proved independently by [BansalSinha21] and [SSW21]; matches the Aaronson-Ambainis upper bound $\mathrm{R}=O(n^{1-1/(2\mathrm{Q})})$. BansalSinha21 SSW21
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(\lceil k/2\rceil)\) $\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) = \lceil k/2\rceil$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(\lceil k/2\rceil)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\mathrm{Adv}^{\pm}(f) = \Theta(\lceil k/2\rceil)$ and $\mathrm{Q}_{\varepsilon}(f) = \lceil k/2\rceil$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\widetilde\Theta\!\big(n^{1-1/k}\big)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and $\mathrm{R}_{\varepsilon}(f) = \widetilde\Theta(n^{1-1/k})$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\lceil k/2\rceil)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(\lceil k/2\rceil)$.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(O(k)\) $\widetilde{\deg} \le 2\mathrm{Q} = 2\lceil k/2 \rceil$. Independent of $n$, against $\mathrm{R} = \widetilde\Theta(n^{1-1/k})$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\widetilde\Theta\!\big(n^{1-1/k}\big)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R}$.
\(\mathrm{D}(f)\) Deterministic query complexity \(O(kn)\) Reading all $kn$ bits determines $\Phi_k$; on the other side $\mathrm{D} \ge \mathrm{R} = \widetilde\Omega(n^{1-1/k})$, so for constant $k$ the deterministic complexity is pinned to within $n^{1/k}$. No exact value is recorded in the literature; for $k=2$ see \(\mathrm{forr}\).
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(O(kn)\) The whole input, fixed in advance; and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\widetilde\Omega\!\big(n^{1-1/k}\big)\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}_0 \le \mathrm{D}$, i.e. between $\widetilde\Omega(n^{1-1/k})$ and $O(kn)$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\widetilde\Theta\!\big(n^{1-1/k}\big)\)· putative The randomized upper bound is an estimator built from coordinates sampled from the coins alone, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$. Adaptivity buys nothing here, exactly as for \(\mathrm{forr}\).
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(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})$.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\widetilde\Omega\!\big(n^{1-1/k}\big)\) Noise only makes the classical problem harder: $\mathrm{N}_p \ge \mathrm{R}$, and reading each sampled coordinate $O(1)$ times gives $\mathrm{N}_p = O(\mathrm{R})$ up to constants.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(O(k\log k)\) The generic robustification bound $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$ applied to $\mathrm{Q} = \lceil k/2\rceil$; and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q}$. Still independent of $n$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\widetilde O\!\big(n^{1-1/k}\big)\) From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\widetilde O\!\big(n^{1-1/k}\big)\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(O(k)\) An algorithm computing $f$ also verifies its input, so $\mathrm{QC} \le \mathrm{Q} = \lceil k/2\rceil$; and $\mathrm{QC} \ge 1$. Independent of $n$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(O(k^2)\) $\mathrm{fbs} = \Theta(\mathrm{QC}^2)$ for partial $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{RC}(f)\)), and $\mathrm{QC} = O(k)$. So the whole block-sensitivity family is capped by a function of $k$ alone, against $\mathrm{R} = \widetilde\Theta(n^{1-1/k})$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(O(k^2)\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(O(k^2)\) $\mathrm{RC} = \Theta(\mathrm{fbs}) = O(k^2)$.
\(\mathrm{bs}(f)\) Block sensitivity \(O(k^2)\) $\mathrm{bs} \le \mathrm{Adv}^2$ for partial $f$ (\(\mathrm{bs}(f)\) vs \(\mathrm{Adv}(f)\)), and $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(k)$. Also $\mathrm{bs} \le \mathrm{fbs}$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(O(k^2)\) See $\mathrm{bs}$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(O(k^2)\) See $\mathrm{bs}$.
\(\mathrm{sdeg}(f)\) Sign degree \(O(k)\) Sandwiched: $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(k)$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(O(k)\) At most $\widetilde{\deg} = O(k)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(k)\) A polynomial is a rational function with denominator $1$, so $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg} = O(k)$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(k)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(k)$: post-selection is worth no more than $O(k)$ queries here, while randomness is worth $\widetilde\Theta(n^{1-1/k})$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\widetilde O\!\big(n^{1-1/k}\big)\) Sandwiched between $\widetilde{\deg} = O(k)$ and $\mathrm{R}_\varepsilon = \widetilde\Theta(n^{1-1/k})$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\widetilde\Omega\!\big(n^{1-1/k}\big)\) Sandwiched: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, both $\widetilde\Omega(n^{1-1/k})$ here.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\widetilde\Omega\!\big(n^{1/2-1/(2k)}\big)\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ for every partial $f$; the upper end is $\mathrm{LR} \le \mathrm{R}$.
\(\bar{\chi}(f)\) Max-conflict complexity \(\widetilde\Omega\!\big(n^{1/2-1/(2k)}\big)\) $\bar\chi = \Omega(\sqrt{\mathrm{R}})$ even for partial $g$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R}$.
\(\chi(f)\) Conflict complexity \(\widetilde O\!\big(n^{1-1/k}\big)\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$ for partial $g$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\widetilde O\!\big(n^{1-1/k}\big)\) From $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R})$.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\widetilde O\!\big(n^{1-1/k}\big)\) $\mathrm{R}^{*} \le \mathrm{R}$; from below $\mathrm{R}^{*} = \Omega(\mathrm{LR}) = \widetilde\Omega(n^{1/2-1/(2k)})$.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\widetilde O\!\big(n^{1-1/k}\big)\) At most $\mathrm{R}$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\widetilde O\!\big(n^{1-1/k}\big)\) $\mathrm{CA} = O(\mathrm{R})$; from below only $\mathrm{CA} = \Omega(\mathrm{fbs}) = \Omega(1)$, so nothing pins it.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\widetilde O\!\big(n^{1-1/k}\big)\) Equal to $\Theta(\mathrm{CA})$; the public-coin, entangled and non-signaling games all collapse there. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\widetilde O\!\big(n^{1-1/k}\big)\) Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\widetilde O\!\big(n^{1-1/k}\big)\) Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants. CGLMSG23
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\widetilde\Theta\!\big(n^{1-1/k}\big)\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R})$, since the canonical solution function is forced to be $f$ itself.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(O(k^2)\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = O(k^2)$. GoosPitassi14
\(\mathrm{C}(f)\) Certificate complexity \(O(kn)\) At most the whole input. Note that the $k = 2$ argument of \(\mathrm{forr}\), which gives $\mathrm{C} = \Theta(n)$ there, does not transfer: for $k \ge 3$ a single bit of a middle block can move $\Phi_k$ by $\Theta(1)$ rather than $O(1/\sqrt n)$, since both $Hx^{\ell-1}$ and $Hx^{\ell+1}$ can spike at the same coordinate.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(O(kn)\) At most $\mathrm{C}$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(O(kn)\) At most $\mathrm{D} = O(kn)$; equal to $\mathrm{SP}$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(O(kn)\) Equal to $\mathrm{UC}$, and at most $\mathrm{D} = O(kn)$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(O(kn)\) At most $\mathrm{UC}$.
\(\mathrm{rank}(f)\) Decision tree rank \(O(kn)\) At most $\mathrm{D} = O(kn)$.
\(\deg(f)\) Exact degree \(O(kn)\) At most $\mathrm{D} = O(kn)$, against $\widetilde{\deg} = O(k)$: exact representation cannot use the gap between the two promise bands.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(O(kn)\) At most $\mathrm{C}^1 \le \mathrm{C} = O(kn)$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(O(kn)\) $\mathrm{NQ} = \lceil\mathrm{ndeg}/2\rceil$ and $\mathrm{ndeg} = O(kn)$. deWolf03
\(\mathrm{rdeg}(f)\) Rational degree \(O(kn)\) At most $\mathrm{C} = O(kn)$; from below $\mathrm{rdeg} \ge \widetilde{\mathrm{rdeg}} \ge 1$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(O(kn)\) At most $\mathrm{D} = O(kn)$, at least $\mathrm{Q} = \lceil k/2\rceil$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(O(kn)\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = O(kn)$.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(O(k^2n^2)\) putative Private coins: both players output a uniformly random one of the $kn$ positions and win whenever they collide on a position where the inputs differ, so the win probability is at least $1/(kn)^2$. The total-function ceiling $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ is not available on a promise problem. From below only $\mathrm{CG} \ge \mathrm{CG}^{\mathrm{pub}}$.

Separations it witnesses

Cited as a witness by