Recursive Fourier sampling
The original superpolynomial oracle separation: $\mathrm{Q}_E = 2^\ell$ against $n^{\Omega(\log n)}$ classically at $\ell = \log n$.
partial quantum arity: an oracle on $(\{0,1\}^n)^\ell$; cost is counted in oracle calls, not in bits
Description
Fix a Boolean $g:\{0,1\}^n\to\{0,1\}$ that is not a parity; $g$ is known in advance and free to evaluate. Take a tree of height $\ell$ in which every internal vertex has $2^n$ children, one per string. Each vertex $v$ carries a secret $s_v \in \{0,1\}^n$, subject to the promise that $g(s_{v\cdot x}) = s_v\cdot x \bmod 2$ for every child $x$; the oracle answers $g(s_v)$ at the leaves. The task is to output $g(s_\varnothing)$ at the root. The canonical choice is $g_{\mathrm{mod}3}(s) = [\,|s| \equiv 0 \bmod 3\,]$.
Three inequivalent formulations circulate. This is [Aaronson03rfs, §1] with the per-node secrets made explicit as in [McKague12, §1.1]. [BernsteinVazirani97, §8.4] is genuinely different -- the string length halves at each level, so the height is forced to $\log n$, and there is no fixed $g$ -- and should not be described as "$\mathrm{RFS}^g_\ell$ with $\ell = \log n$".
Formal definition
$$g(s_{x_1\ldots x_k}) = s_{x_1\ldots x_{k-1}}\cdot x_k \bmod 2, \qquad A(x_1,\dots,x_\ell) = g(s_{x_1\ldots x_\ell}), \qquad \text{output } g(s_\varnothing).$$
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(2^\ell\) | One level costs two queries by the Bernstein-Vazirani kickback trick, and the recursion is exact: [Aaronson03rfs, Lem. 1] puts the language version in $\mathrm{EQP}^A$; [BernsteinVazirani97, Thm. 8.4.3] gives a polynomial-time quantum machine accepting with probability $1$, from the recursion $T(n) \le \mathrm{poly}(n) + 4T(n/2)$. Aaronson03rfs BernsteinVazirani97 |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(2^\ell) \text{ for } g = g_{\mathrm{mod}3}\) | [Aaronson03rfs, Thm. 5]: $\mathrm{Q}(\mathrm{RFS}^g_\ell) = \Omega\big((1-\mu(g))^{-\ell/2}\big)$, where $\mu(g)$ is the nonparity coefficient of Def. 2. Prop. 6 gives $\mu(g_{\mathrm{mod}3}) = 3/4 - O(1/n)$, hence $\Omega(2^\ell)$, matching the algorithm. Thm. 7: $\mu(g) < 0.146$ forces $g$ to be a parity, so any legal $g$ gives $\Omega(2^{0.113\ell})$. This was the first lower bound to need the adversary method rather than the polynomial method. Aaronson03rfs |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) | [BernsteinVazirani97, Thm. 8.4.6 / Cor. 8.4.7]: relative to a random legal oracle, with probability $1$, the language is not in $\mathrm{BPTime}(T(n))$ for any $T(n) = n^{o(\log n)}$; the explicit bound is $\tfrac1{12}\varphi(n/4)$ with $\varphi(n) = n(n/2)\cdots 1 > n^{(\log n)/2}$. So the separation is superpolynomial, not exponential. The often-quoted $\Theta(n^\ell)$ for general $\ell$ is a folklore extrapolation -- BV prove only the $\ell = \log n$ case. BernsteinVazirani97 |
| \(\mathrm{bs}(f)\) Block sensitivity | \(1\) putative | The promise is rigid enough that no block of the oracle can be flipped and stay inside it. Worth recording because it is precisely why the polynomial method says nothing here. Aaronson10 |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(2^{\ell})\) | $\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) = \Theta(2^{\ell})$ here for the base function $g = g_{\mathrm{mod}3}$. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(2^{\ell})\) | Same sandwich as \(\mathrm{Adv}^{\pm}(f)\): the multiplicative adversary is also a tight characterisation of $\mathrm{Q}$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Theta(2^{\ell}) \text{ for } g = g_{\mathrm{mod}3}\) | Squeezed to nothing: $\mathrm{Q}_{\varepsilon} \le \mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}}$, and both ends are $\Theta(2^{\ell})$ here -- the exact algorithm already matches the bounded-error lower bound, so error tolerance buys nothing at all on $\mathrm{RFS}$. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(2^{\ell}) \text{ for } g = g_{\mathrm{mod}3}\) | The approximate $\gamma_2$ norm equals $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), which is $\Theta(\mathrm{Q}_{\varepsilon}) = \Theta(2^{\ell})$ here. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Theta(2^{\ell}) \text{ for } g = g_{\mathrm{mod}3}\) | Unusually, the positive-weight adversary is already tight. The $\Omega(2^{\ell})$ of [Aaronson03rfs, Thm. 5] is proved with Ambainis' weighted adversary, which has non-negative weights, so it is a lower bound on $\mathrm{Adv}$ itself and not merely on $\mathrm{Q}$; the ceiling is $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = O(\mathrm{Q}) \le O(\mathrm{Q}_{\mathrm{E}}) = O(2^{\ell})$. Contrast \(\mathrm{TRI}_m\), where the certificate-complexity barrier pins $\mathrm{Adv}$ strictly below $\mathrm{Q}$. Note the $\mathrm{bs} = 1$ entry: the polynomial method cannot even get started, while the adversary method is exactly optimal. Aaronson03rfs |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(O(n^{\ell})\) putative | Upper: to learn $s_v$ it suffices to learn the $n$ bits $s_v\cdot x$ for $x = e_1,\dots,e_n$, and each of those is $g(s_{vx})$, one recursive call one level down; so $T(\ell) = n\,T(\ell-1)$ with $T(0) = 1$. Lower: $\mathrm{D} \ge \mathrm{R} = n^{\Omega(\log n)}$ at $\ell = \log n$, so at that setting the two meet and $\mathrm{D} = n^{\Theta(\log n)}$. For general $\ell$ only the upper bound is on record. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) | From $\mathrm{R}_{\varepsilon} \le \mathrm{R}_0$ and the [BernsteinVazirani97] bound on $\mathrm{R}$; capped above by $\mathrm{D} = O(n^{\ell})$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(n^{\Omega(\log n)} \text{ at } \ell = \log 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 allowing the classical algorithm to pay only in expectation does not rescue it. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) | From $\mathrm{R}_{\varepsilon} \le \mathrm{R}^{1}$; capped above by $\mathrm{D} = O(n^{\ell})$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) | By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$; and this is the form the bound is actually proved in -- [BernsteinVazirani97, Thm. 8.4.6] argues against a uniformly random legal oracle, so it is a $\mathrm{D}^\mu$ statement first and an $\mathrm{R}$ statement afterwards. BernsteinVazirani97 |
| \(\mathrm{s}(f)\) Sensitivity | \(0\) putative | Exactly zero, and this is the sharpest illustration in the zoo of the warning on the \(\mathrm{s}(f)\) page that sensitivity is useless on a promise. Group the leaves by their parent $v$: the oracle restricted to the $2^n$ children of $v$ is the linear function $x \mapsto s_v\cdot x$, because the promise says $g(s_{vx}) = s_v\cdot x$. Changing a single leaf value destroys linearity, so no single-bit flip of a legal oracle is legal, and there is nothing for $\mathrm{s}$ to count. Compare $\mathrm{bs} = 1$: the smallest legal-to-legal change flips a $2^{-\ell}$ fraction of the whole tree. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(0\) | Immediate from $\mathrm{s} = \max(\mathrm{s}^0,\mathrm{s}^1) = 0$. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(0\) | Immediate from $\mathrm{s} = \max(\mathrm{s}^0,\mathrm{s}^1) = 0$. |
| \(\lambda(f)\) Spectral sensitivity | \(0\) | The sensitivity graph is empty, since $\mathrm{s} = 0$: there is not a single pair of legal oracles at Hamming distance one with different answers. So $\lambda(f) = 0$, and the $\mathrm{Q} = \Omega(\lambda)$ route -- like every other combinatorial route -- says nothing at all here. This is the case the \(\lambda(f)\) page's partial-setting warning is about. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(1\) putative | Both sides attain the recorded $\mathrm{bs} = 1$. Given any legal oracle $A$ and any $s'_\varnothing$ with $g(s'_\varnothing) \ne g(s_\varnothing)$, one can build a legal $A'$ realising it (choose the subtree secrets top-down), and $B = \{\text{leaves where } A \ne A'\}$ is a sensitive block; so $\mathrm{bs}_x \ge 1$ at every input, of either answer. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(1\) putative | Same construction as $\mathrm{bs}^0$, run from a $1$-input. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(O(n^{\ell})\) putative | Adaptivity buys nothing: the $O(n^{\ell})$ deterministic algorithm of the $\mathrm{D}$ entry is already non-adaptive. Its query set is fixed in advance -- the $n^{\ell}$ leaves $(e_{i_1},\dots,e_{i_\ell})$ whose every path component is a standard basis vector -- and the recursion $s_v\cdot e_i = g(s_{v e_i})$ then reconstructs every secret bottom-up. So $\mathrm{D} \le \mathrm{D}^{\mathrm{na}} \le n^{\ell}$, and at $\ell = \log n$ both are $n^{\Theta(\log n)}$. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}_{\varepsilon}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R} = n^{\Omega(\log n)}$ and $\mathrm{D}^{\mathrm{na}} = O(n^{\ell})$ here, so at $\ell = \log n$ the two ends meet at $n^{\Theta(\log n)}$. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) | At least $\mathrm{R} = n^{\Omega(\log n)}$, and at most $O(\mathrm{R}\log \mathrm{R})$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), which changes nothing at this scale. Noise is not what makes recursive Fourier sampling hard classically. |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Omega(2^{\ell}),\ O(\ell\,2^{\ell})\) | Sandwiched by the generic $\mathrm{Q}(f) \le \mathrm{Q}^{\mathrm{rob}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) around $\mathrm{Q} = \Theta(2^{\ell})$ at $g = g_{\mathrm{mod}3}$. Whether the $\ell$ is needed is open: the Bernstein-Vazirani kickback is exact and has no error to amplify, but the recursion must re-run it $\ell$ levels deep. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(O(2^{\ell})\) | From $\widetilde{\deg}(f) \le 2\,\mathrm{Q}(f)$, which survives the passage to partial functions (\(\widetilde{\deg}_{\varepsilon}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(2^{\ell})$ at $g = g_{\mathrm{mod}3}$. No lower bound is recorded because none is available: with $\mathrm{s} = 0$ and $\mathrm{bs} = 1$ every symmetrisation argument starts from nothing, which is exactly why [Aaronson03rfs] had to invent an adversary proof. Aaronson03rfs |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) | $\mathrm{LR}(f)=\Omega(\sqrt{\mathrm{R}(f)})$ and $\mathrm{LR}(f)\le\mathrm{R}(f)$ (\(\mathrm{LR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), both for partial $f$) [BBGM22]. A square root does not dent $n^{\Omega(\log n)}$, so the linearised measure is superpolynomial too; capped above by $\mathrm{D}=O(n^{\ell})$. BBGM22 |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(O(2^{\ell})\) | $\mathrm{rdeg}_\varepsilon(f)\le\widetilde{\deg}_\varepsilon(f)$ (\(\mathrm{rdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\)), and the \(\widetilde{\deg}_{\varepsilon}(f)\) entry gives $O(2^{\ell})$ at $g=g_{\mathrm{mod}3}$. No lower bound: the polynomial method is blind here, which is the whole point of the $\mathrm{bs}=1$ entry. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O(2^{\ell})\) | Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=\Theta(2^{\ell})$; equivalently $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] and \(\mathrm{rdeg}_{\varepsilon}(f)\) is $O(2^{\ell})$. MahadevdeWolf15 |
Separations it witnesses
-
Superpolynomial: $\mathrm{Q}_E = \mathrm{poly}$ against $\mathrm{R} = n^{\Omega(\log n)}$ at $\ell = \log n$ -- the first such separation, and it is exact quantum versus randomized.
Notes
$\mathrm{RFS}$ was the original candidate for $\mathrm{BQP}\not\subset\mathrm{PH}$, a role Forrelation eventually filled: it does give $\mathrm{BQP}^A \not\subset \mathrm{NP}^A, \mathrm{MA}^A$, but at $\ell = \log n$ it is in $\mathrm{PH}$ [Aaronson10], and whether some setting of the parameters escapes $\mathrm{PH}$ (or $\mathrm{AM}$) is open.