\(\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
| Measure | Value | Notes |
|---|---|---|
| \(\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
-
In this entry's own parameter: $\mathrm{Q} = \lceil k/2\rceil$ and $\mathrm{R} = \widetilde\Theta(n^{1-1/k})$, i.e. $\mathrm{R} = \widetilde\Theta\!\big(n^{1-1/(2\mathrm{Q})}\big)$ for even $k$. Optimal -- it matches the Aaronson-Ambainis upper bound $\mathrm{R} = O(n^{1-1/(2\mathrm{Q})})$ and so settles the partial-function R-vs-Q trade-off at every $\mathrm{Q}$.
-
Composed with cheat sheets, gives a total function with $\mathrm{R} = \widetilde\Omega(\mathrm{Q}^3)$ -- the best known total separation.
Cited as a witness by
-
\(\mathrm{R}(f_n) = \widetilde\Omega(\mathrm{Q}(f_n)^3)\)
-
\(\mathrm{Q}(k\text{-}\mathrm{Forrelation})=\lceil k/2\rceil,\ \mathrm{R}=\tilde\Theta(n^{1-1/k})\)