FORRELATION
One quantum query vs $\widetilde\Theta(\sqrt n)$ randomized queries -- the maximal possible gap at $\mathrm{Q}=1$.
partial
quantum
arity: $2n$ bits (two strings $x,y \in \{\pm1\}^n$)— also: Fourier correlation, 2-forrelation
Description
Decide whether $y$ is highly correlated with the Fourier transform of $x$.
Formal definition
For $x, y \in \{-1,1\}^n$ with $n=2^m$, let $$\Phi(x,y) \;=\; \frac{1}{n^{3/2}}\sum_{i,j\in\{0,1\}^m} x_i\,(-1)^{i\cdot j}\,y_j \;=\; \frac{1}{\sqrt n}\,\langle \hat x, y\rangle .$$ $\mathrm{forr}(x,y) = 1$ if $\Phi(x,y) \ge 3/5$, $= 0$ if $|\Phi(x,y)| \le 1/100$, and undefined otherwise.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(1\) | Prepare uniform superposition, query $x$, Hadamard, query $y$, Hadamard, measure. AaronsonAmbainis18 |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(O(1)\) | $\widetilde{\deg}\le 2\mathrm{Q} = 2$. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\widetilde\Theta(\sqrt n)\) | Lower bound $\Omega(\sqrt n/\log n)$ [AaronsonAmbainis18], improved to $\widetilde\Omega(\sqrt n)$ via Fourier growth of decision trees [Tal20]. Matching $O(\sqrt n)$ upper bound. AaronsonAmbainis18 Tal20 |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\Theta(n)\) | |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(0\) putative | The support of a product distribution is a combinatorial rectangle $\prod_i S_i$, and no rectangle inside the promise can meet both sides. Flipping one bit of $x$ or $y$ moves $\Phi$ by at most $2/\sqrt n$, since $|\partial\Phi/\partial x_i| = n^{-3/2}\big|\sum_j (-1)^{i\cdot j}y_j\big| \le n^{-1/2}$. So if the rectangle held a $1$-input ($\Phi \ge 3/5$) and a $0$-input ($|\Phi| \le 1/100$) one could walk between them inside the rectangle one bit at a time, and for $n \ge 16$ some intermediate point -- also in the rectangle -- would have $\Phi$ in the forbidden band $(1/100, 3/5)$, off the promise. Hence every product $\mu$ is one-sided and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \widetilde\Theta(\sqrt n)$. This collapse is generic for promise problems, not special to forrelation: it recurs at \(\mathrm{SIMON}_n\), \(\mathrm{BV}_n\), \(\mathrm{COL}_n\), \(\mathrm{GapMaj}^{\delta}_{n}\) and \(\mathrm{ApproxIndex}_k\), and it is why $\mathrm{RS}(g) = \widetilde\Omega(\mathrm{D}^{\mathrm{prod}}(g))$ is stated only for total $g$. |
| \(\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{MAdv}(f)\) Multiplicative adversary | \(\Theta(1)\) | Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\mathrm{Adv}^{\pm}(f) = \Theta(1)$ and $\mathrm{Q}_{\varepsilon}(f) = 1$ here. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\widetilde\Theta(\sqrt n)\) | $\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(\sqrt n)$ here. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(1)\) | $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Theta(1)\) | A lower bound on $\mathrm{Q} = 1$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\widetilde\Theta(\sqrt n)\) | By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \widetilde\Theta(\sqrt n)$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(\Theta(n)\) | Between $\mathrm{D} = \Theta(n)$ and the trivial $2n$. |
| \(\mathrm{s}(f)\) Sensitivity | \(0\) putative | The promise gap is wider than one flip. Flipping a single $x_i$ changes $\Phi$ by $\tfrac{2}{n^{3/2}}\big|\sum_j (-1)^{i\cdot j} y_j\big| \le 2/\sqrt n$, and the same bound holds for a $y_j$; the two promise regions are separated by $3/5 - 1/100$. So for $n \ge 12$ no single flip stays inside the promise with a different value, and $\mathrm{s}^0 = \mathrm{s}^1 = 0$ while $\mathrm{D} = \Theta(n)$. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(0\) putative | See $\mathrm{s}$. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(0\) putative | See $\mathrm{s}$. |
| \(\lambda(f)\) Spectral sensitivity | \(0\) putative | The sensitivity graph on the promise has no edges (see $\mathrm{s} = 0$), so the adjacency matrix is zero. Spectral sensitivity lower-bounds $\mathrm{Q}$ for total functions and says nothing at all here. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(O(1)\) | Two arguments, the second much sharper. Counting: flipping $m$ coordinates moves $\Phi$ by at most $2m/\sqrt n$, so every sensitive block has $\Omega(\sqrt n)$ coordinates and at most $O(\sqrt n)$ of them are disjoint. Adversary: $\mathrm{bs}(f) \le \mathrm{Adv}(f)^2$ holds for partial $f$ as well (\(\mathrm{bs}(f)\) vs \(\mathrm{Adv}(f)\) -- disjointness of the blocks is all the proof uses), and $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$ here. So block sensitivity is constant against $\mathrm{D} = \Theta(n)$, and it does not even see the $\widetilde\Theta(\sqrt n)$ scale of $\mathrm{R}$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(O(1)\) | See $\mathrm{bs}$: $\mathrm{bs}^0 \le \mathrm{bs} = O(1)$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(O(1)\) | See $\mathrm{bs}$: $\mathrm{bs}^1 \le \mathrm{bs} = O(1)$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(O(1)\) | The fractional relaxation is constant too, by the quantum certificate route rather than by counting: $\mathrm{fbs}(f) = \Theta(\mathrm{RC}(f)) = \Theta(\mathrm{QC}(f)^2)$ for partial $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{RC}(f)\)), and $\mathrm{QC} \le \mathrm{Q} = 1$ since an algorithm computing $f$ also verifies its input. The load count of the $\mathrm{bs}$ entry only gives $O(\sqrt n)$; this is the right answer. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(O(1)\) | Equal to $\mathrm{fbs}$ by LP duality. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(O(1)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = O(1)$. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(1)\) | An algorithm computing $f$ also verifies it, so $\mathrm{QC} \le \mathrm{Q} = 1$; and $\mathrm{QC} \ge 1$ for a non-constant $f$. This is what forces $\mathrm{fbs} = O(1)$ above, via $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(\Theta(1)\) | Sandwiched: $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(1)$, and at least $1$. Every degree measure below $\widetilde{\deg}$ is constant here while $\mathrm{R} = \widetilde\Theta(\sqrt n)$. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(\Theta(1)\) | Sandwiched between $\mathrm{sdeg} = \Theta(1)$ and $\widetilde{\deg} = O(1)$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(\Theta(1)\) | A polynomial is a rational function with denominator $1$, so $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg} = O(1)$; and at least $1$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\Theta(1)\) | $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(1)$. Post-selection is of no use on a problem already solved by one query. |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\widetilde O(\sqrt n)\) | Sandwiched: $\widetilde{\deg} \le \mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon$, i.e. between $O(1)$ and $\widetilde\Theta(\sqrt n)$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\widetilde O(\sqrt n)\) | The classical adversary lower-bounds $\mathrm{R} = \widetilde\Theta(\sqrt n)$ (via $\mathrm{CA} \le \mathrm{prt}_\varepsilon + \log(1/\varepsilon) \le 2\mathrm{R}_\varepsilon + O(1)$). It is at least $\Omega(\mathrm{fbs})$, which is only $\Omega(1)$ here, so nothing pins it further. |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\widetilde O(\sqrt n)\) | The public-coin, entangled and non-signaling certificate games all collapse to $\Theta(\mathrm{CA})$ (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)). CGLMSG23 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\widetilde O(\sqrt n)\) | Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants; see \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\). CGLMSG23 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\widetilde O(\sqrt n)\) | Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants; see \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\). CGLMSG23 |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\widetilde\Omega(\sqrt n)\) | Sandwiched: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, both $\widetilde\Omega(\sqrt n)$ here. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\widetilde O(\sqrt n)\) | From the partial-function chain $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R})$. Nothing pins it from below: $\mathrm{CA} \le \mathrm{RS}$ is the only lower bound available and $\mathrm{CA}$ itself is unpinned here. |
| \(\chi(f)\) Conflict complexity | \(\widetilde O(\sqrt n)\) | $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$ for partial $g$. The familiar lower bound $\chi = \Omega(\mathrm{bs})$ is a total-function statement [Li18] and gives only $\Omega(1)$ here in any case, since $\mathrm{bs} = O(1)$. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\widetilde O(\sqrt n)\) | $\mathrm{R}^{*} \le \mathrm{R}$ for partial $f$; from below $\mathrm{R}^{*} = \Omega(\mathrm{LR}) = \widetilde\Omega(n^{1/4})$ and $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(1)$, so the composition-friendly version of $\mathrm{R}$ is still polynomially far above the single quantum query. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\widetilde O(\sqrt n)\) | At most $\mathrm{R}$. The reverse direction is only $\mathrm{R} = 2^{\Omega(\mathrm{noisyR})}$, which permits $\mathrm{noisyR}$ to be as small as $\Omega(\log n)$; cf. \(\mathrm{ApproxIndex}_k\), where that exponential gap is realised. |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Theta(1)\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$, and $\mathrm{Q} = 1$. So even an oracle whose every answer is only a bounded-error bit is beaten by $O(1)$ quantum queries, against $\mathrm{R} = \widetilde\Theta(\sqrt n)$ and $\mathrm{N}_p = \widetilde\Theta(\sqrt n)$ classically. |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\widetilde\Omega(n^{1/4})\) | $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ for every partial $f$, and $\mathrm{R} = \widetilde\Theta(\sqrt n)$; the upper end is $\mathrm{LR} \le \mathrm{R}$. Even the linearised measure, which charges $1/\gamma$ instead of $1/\gamma^2$ for bias $\gamma$, stays polynomially above $\mathrm{Q} = 1$. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\widetilde\Omega(n^{1/4})\) | $\mathrm{R} = O(\bar\chi^2)$ for partial $g$, so $\bar\chi = \Omega(\sqrt{\mathrm{R}}) = \widetilde\Omega(n^{1/4})$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R}$. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\widetilde\Theta(\sqrt n)\)· putative | The $O(\sqrt n)$ algorithm samples coordinates of $x$ and $y$ from its coins and forms an estimator of $\langle\hat x, y\rangle$, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \widetilde\Theta(\sqrt n)$. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\widetilde\Omega(\sqrt n)\) | Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}_0 \le \mathrm{D}$, i.e. between $\widetilde\Theta(\sqrt n)$ and $\Theta(n)$. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\widetilde\Theta(\sqrt n)\) | At least $\mathrm{R}$, and at most $O(\mathrm{R})$ by reading each sampled coordinate $O(1)$ times and majority-voting. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\widetilde O(\sqrt n)\) | From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\widetilde O(\sqrt n)\) | From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\widetilde\Theta(\sqrt n)\) | Degenerate on a partial Boolean function: there is only one correct answer, so the canonical solution function is forced to be $f$ itself and reproducibility is free. Hence $\mathrm{psD} = \Theta(\mathrm{R}) = \widetilde\Theta(\sqrt n)$ -- see the \(\mathrm{psD}(S)\) entry. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(O(1)\) | Degenerate on a Boolean function: every input is critical and the solution function is forced, so $\mathrm{cbs} = \mathrm{bs} = O(1)$. GoosPitassi14 |
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(n)\) putative | Upper: $\mathrm{C} \le 2n$. Lower, from one explicit $1$-input. Take $n = 2^m$ with $m$ even and let $x$ be a bent function on $m$ bits, so $\hat x_j = \pm n^{-1/2}$ for every $j$; put $y_j = \sqrt n\,\hat x_j \in \{\pm1\}$. Then $\Phi = \tfrac{1}{\sqrt n}\sum_j \hat x_j y_j = 1$, a $1$-input. Dually $\hat y_i = x_i/\sqrt n$, so $\Phi = \tfrac{1}{\sqrt n}\sum_i x_i \hat y_i$ and flipping any single $x_i$ lowers $\Phi$ by exactly $2/n$; flipping $t$ of them gives $\Phi = 1 - 2t/n$ exactly. Choosing $t$ near $n/2$ lands in $|\Phi| \le 1/100$, a $0$-input. So a certificate at this input must fix all but at most $0.51n$ of the $n$ coordinates of $x$, i.e. $\mathrm{C}^1 \ge 0.49n$. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(\Theta(n)\) putative | The lower bound recorded under \(\mathrm{C}(f)\) is witnessed at a $1$-input, so $\mathrm{C}^1 = \Theta(n)$ as well. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\Theta(n)\) putative | Take the same bent $x$ and $y = \chi_{j_0}$, i.e. $y_j = (-1)^{j\cdot j_0}$. Then $\sum_j \hat x_j y_j = x_{j_0} = \pm1$, so $|\Phi| = 1/\sqrt n \le 1/100$ and this is a $0$-input. Since $\sum_j |\hat x_j| = \sqrt n$ and $\sum_j \hat x_j y_j = \pm 1$, the number of $j$ with $y_j \ne \mathrm{sign}(\hat x_j)$ is $n/2 \pm \sqrt n/2$, and flipping any one of them raises $\Phi$ by exactly $2/n$. Flipping $0.31n$ of them reaches $\Phi \ge 3/5$, so a certificate must fix at least $n/2 - \sqrt n - 0.31n \ge 0.18n$ of the $y$-coordinates. With $\mathrm{C}^0 \le 2n$ this gives $\Theta(n)$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(\Theta(n)\)· putative | Every certificate, at every promise input, fixes $\Omega(n)$ coordinates. Suppose one fixes fewer than $10^{-3}n$; then at least $0.999n$ coordinates of $x$ and $0.999n$ of $y$ are free, and by Cauchy--Schwarz the fixed $y$-positions carry $\sum_{\text{fixed } j}|\hat x_j| \le \sqrt{10^{-3}n} \le 0.032\sqrt n$. At a $1$-input, $\Phi \ge 3/5$ forces $\sum_j |\hat x_j| \ge 0.6\sqrt n$; setting every free $y_j$ to $-\mathrm{sign}(\hat x_j)$ drives $\Phi$ below $-0.5$, and reverting those bits one at a time back to their original values moves $\Phi$ in steps of $2|\hat x_j|/\sqrt n \le 2/\sqrt n < 1/50$ up to $\Phi \ge 3/5$, so some intermediate assignment has $|\Phi| \le 1/100$ -- a $0$-input consistent with the certificate. At a $0$-input, set the free $x$-coordinates uniformly at random: then $\sum_j |\hat x_j| \ge 0.7\sqrt n$ with high probability, and setting every free $y_j$ to $\mathrm{sign}(\hat x_j)$ gives $\Phi \ge 0.7 - 2(0.032) > 3/5$, a $1$-input consistent with the certificate. Either way the set was not a certificate. With $\mathrm{C}_{\min} \le \mathrm{C} \le 2n$ this pins $\Theta(n)$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(\Theta(n)\) | Squeezed: $\mathrm{C} \le \mathrm{SP} = \mathrm{UC} \le \mathrm{D}$, and both ends are $\Theta(n)$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(\Theta(n)\) | Equal to $\mathrm{UC}$ exactly, and squeezed between $\mathrm{C} = \Theta(n)$ and $\mathrm{D} = \Theta(n)$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(\Theta(n)\) | Squeezed between $\mathrm{C}_{\min} = \Theta(n)$ and $\mathrm{UC} = \Theta(n)$. Note this is the one-sided minimum $\min\{\mathrm{UC}^0,\mathrm{UC}^1\}$, and both sides are already $\Theta(n)$ here. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(\Theta(n)\) | A tree of rank $r$ has a leaf at depth $\le r$, so $\mathrm{C}_{\min} \le \mathrm{rank} \le \mathrm{D}$; both ends are $\Theta(n)$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^{\Theta(n)}\) | At least $2^{\mathrm{C}_{\min}}$ and at most $2^{\mathrm{D}+1}$, and $\mathrm{C}_{\min} = \Theta(\mathrm{D}) = \Theta(n)$. Unlike \(\mathrm{DJ}_n\), no small tree exists: the promise here has no cheap side. |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(O(n^{3/4})\) putative | Exhibiting a weighting directly, as one must off the promise ($\mathrm{EC} \le \mathrm{C}$ needs totality). Flipping one bit of $x$ or $y$ moves $\Phi$ by at most $2/\sqrt n$, so two promise inputs of opposite value differ in at least $(3/5-1/100)\sqrt n/2 \ge 0.29\sqrt n$ coordinates. Put $w^x_i = (0.29\sqrt n)^{-1/2}$ at every input and every coordinate: then $\sum_{i: x_i \ne y_i} w^x_i w^y_i \ge 1$, and the cost is $2n \cdot \Theta(n^{-1/4}) = \Theta(n^{3/4})$. This beats the trivial $\mathrm{EC} \le \mathrm{C} = \Theta(n)$; from below only $\mathrm{EC} \ge \mathrm{FC} = O(1)$ is available. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(O(n^{3/2})\) putative | Private coins, so no shared index is available and the total-function ceiling $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ is not licensed here. Both players output a uniformly random one of the $2n$ positions; since opposite-valued promise inputs differ in $\ge 0.29\sqrt n$ positions the win probability is $\ge 0.29\sqrt n/(2n)^2$, so $\mathrm{CG} = O(n^{3/2})$. From below $\mathrm{CG} \ge \mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA})$, which is only $\Omega(1)$ here. |
| \(\deg(f)\) Exact degree | \(O(n)\) | At most $\mathrm{D} = \Theta(n)$. Nothing smaller is known: unlike $\widetilde{\deg} = O(1)$, exact representation cannot exploit the gap between the two promise bands. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(O(n)\) | At most $\mathrm{C}^1 = \Theta(n)$: the sum over $1$-certificates of their indicator polynomials is a nondeterministic polynomial. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(O(n)\) | $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ and $\mathrm{ndeg} = O(n)$. deWolf03 |
| \(\mathrm{rdeg}(f)\) Rational degree | \(O(n)\) | At most $\mathrm{C} = \Theta(n)$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(O(n)\) | At most $\mathrm{D} = \Theta(n)$, at least $\mathrm{Q} = 1$. The $\mathrm{Q}_E \ge \deg/2$ bound gives nothing, since $\deg$ itself is only known to be $O(n)$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(O(n)\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = O(n)$. |
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. 379 in total, strongest first.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\mathrm{D}(f) = \Theta(n)\) against \(\mathrm{s}(f) = 0\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = 2^{\Theta(n)}\) against \(\mathrm{bs}(f) = O(1)\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{C}(f) = \Theta(n)\) against \(\mathrm{s}^0(f) = 0\)
-
\(\mathrm{C}^0(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{C}^0(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = 0\)
-
\(\mathrm{C}^1(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{C}^1(f) = \Theta(n)\) against \(\mathrm{s}^1(f) = 0\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^0(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = \Theta(n)\) against \(\mathrm{bs}^0(f) = O(1)\)
-
\(\mathrm{UC}(f_n) \to \infty \ \text{ while } \ \mathrm{fbs}(f_n) = O(1)\)from \(\mathrm{UC}(f) = \Theta(n)\) against \(\mathrm{fbs}(f) = O(1)\)
-
\(\mathrm{UC}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{RC}(f_n) = O(1)\)from \(\mathrm{UC}_{\min}(f) = \Theta(n)\) against \(\mathrm{RC}(f) = O(1)\)
-
\(\mathrm{SP}(f_n) \to \infty \ \text{ while } \ \mathrm{FC}(f_n) = O(1)\)from \(\mathrm{SP}(f) = \Theta(n)\) against \(\mathrm{FC}(f) = O(1)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^1(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \widetilde\Theta(\sqrt n)\) against \(\mathrm{bs}^1(f) = O(1)\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{rank}(f) = \Theta(n)\) against \(\mathrm{cbs}(S) = O(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = \Theta(n)\) against \(\mathrm{Q}_{\varepsilon}(f) = 1\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \widetilde\Theta(\sqrt n)\) against \(\mathrm{PostQ}_{\varepsilon}(f) = \Theta(1)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{QC}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \widetilde\Theta(\sqrt n)\) against \(\mathrm{QC}(f) = \Theta(1)\)
… and 365 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{Q} = 1$ against $\mathrm{R} = \widetilde\Theta(\sqrt n)$ -- a single quantum query beats every classical algorithm making $n^{1/2-o(1)}$. This is the $\mathrm{Q}=1$ case of the Aaronson-Ambainis trade-off $\mathrm{R} = O(n^{1-1/(2\mathrm{Q})})$, shown optimal by [Tal20]; see \(\mathrm{forr}_k\) for the whole curve. There is no polynomial relation between $\mathrm{R}$ and $\mathrm{Q}$ for partial functions.
-
$\widetilde{\deg} = O(1)$ but $\mathrm{R}=\widetilde\Omega(\sqrt n)$.
Cited as a witness by
-
\(\mathrm{Q}(\mathrm{Forrelation}_n)=1,\ \ \mathrm{R}(\mathrm{Forrelation}_n)=\tilde\Theta(\sqrt n)\)
Notes
Aaronson-Ambainis also proved the matching upper bound: any partial $f$ with $\mathrm{Q}(f)=k$ has $\mathrm{R}(f) = O(n^{1-1/(2k)})$. So Forrelation is optimal, and $k$-Forrelation extends this to every $k$.