Q The Query Complexity Zoo
\(\mathrm{rdeg}_{\varepsilon}(f)\)

Approximate rational degree

Bounded-error version of rational degree; equals post-selected bounded-error quantum query complexity.

Definition

The $\varepsilon>0$ case of \(\mathrm{rdeg}(f)\); $\mathrm{rdeg}_{1/3}$ is the standard choice.

Parameters

\(\varepsilon\) (eps) default \(1/3\)

Basic facts

  • $\mathrm{PostQ}_\varepsilon(f)=\Theta(\mathrm{rdeg}_\varepsilon(f))$ [MahadevdeWolf15].
  • $\mathrm{rdeg}_\varepsilon(f)\le\mathrm{rdeg}(f)$ and $\mathrm{rdeg}_\varepsilon(f)\le\widetilde{\deg}_\varepsilon(f)$.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{rdeg}_{\varepsilon}(f)\). “\(\mathrm{rdeg}_{\varepsilon}(f)\) in terms of it” is the pair with \(\mathrm{rdeg}_{\varepsilon}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\mathrm{rdeg}_{\varepsilon}(f)\) in terms of it It in terms of \(\mathrm{rdeg}_{\varepsilon}(f)\)
\(\mathrm{rdeg}(f)\) Rational degree total1,1 partial1,1 open pair → total∞ partial∞ derived open pair →
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity total1,1 partial1,1 derived open pair → total1,1 partial1,1 open pair →
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total1,1 partial1,1 open pair → total∞ partial∞ derived open pair →
\(\mathrm{ndeg}(f)\) Nondeterministic degree total1,? partial1,? derived open pair → total∞ partial∞ derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(1\) The single rational function $r(x) = \dfrac{n\sum_i x_i}{1 + n\sum_i x_i}$ has numerator and denominator of degree $1$, is $0$ at $0^n$, and is $\ge \tfrac{n}{n+1} \ge \tfrac23$ at every $1$-input. So one degree of freedom suffices where $\widetilde{\deg} = \Theta(\sqrt n)$ is needed for polynomials -- the cleanest illustration that rational approximation is a strictly different resource. MahadevdeWolf15
AND total \(1\) Dual to \(\mathrm{OR}_n\): $1 - r(\bar x)$ for the same degree-$1$ rational $r$. MahadevdeWolf15
PARITY total \(n\) Rational approximation does not help at all here. Suppose $p/q$ approximates $\mathrm{PARITY}$ to within $1/3$ with $\deg p, \deg q \le d$ and $q > 0$ on the cube. Symmetrising over the slices, $P(k) - \tfrac12 Q(k)$ is a univariate polynomial of degree $\le d$ whose sign alternates at $k = 0,1,\dots,n$, so it has $\ge n$ roots and $d \ge n$. Contrast $\mathrm{rdeg}(\mathrm{MAJ}) = \Theta(\log n)$: parity is the function on which postselection buys nothing. MahadevdeWolf15
MAJORITY total \(\Theta(\log n)\) Newman's degree-$O(\log(1/\varepsilon))$ rational approximation to $|x|$, rescaled to the slices $k = 0,\dots,n$, approximates the sign of $k - n/2$ with degree $O(\log n)$; the matching $\Omega(\log n)$ is in [MahadevdeWolf15]. Compare $\widetilde{\deg}(\mathrm{MAJ}) = \Theta(n)$: rational approximation is exponentially cheaper than polynomial approximation here, which is exactly what makes majority the canonical postselection example. Newman64 MahadevdeWolf15
Threshold total \(O(\log n)\) Newman's degree-$O(\log(1/\delta))$ rational approximation to $\mathrm{sign}$ on $[-1,-\delta]\cup[\delta,1]$, applied after the affine map $j \mapsto (j-k+\tfrac12)/n$ so that $\delta = \Theta(1/n)$. Recorded as an upper bound only, because the truth genuinely depends on $k$: it is $\Theta(\log n)$ at $k = n/2$ [MahadevdeWolf15] but only $1$ at $k=1$, where $2|x|/(1+2|x|)$ already separates $|x|=0$ from $|x|\ge1$. Newman64 MahadevdeWolf15
EXACT-HALF total \(O(1)\) putative Degree $2$ suffices: $r(x) = \big(1 + 2(\sum_i x_i - n/2)^2\big)^{-1}$ equals $1$ on the middle slice and is at most $1/3$ everywhere else, since $|\sum_i x_i - n/2| \ge 1$ off it. This is the sharpest gap in the zoo between rational and polynomial approximation: $\widetilde{\deg} = \Theta(n)$ and even $\mathrm{rdeg} = \Theta(n)$ (exact rational representation), yet approximate rational degree is constant. Recorded as $O(1)$ because $\ge 2$ is not proved -- only $\ge 1$ from non-constancy. MahadevdeWolf15
ODD-MAX-BIT total \(1\) putative Degree $1$ suffices, as for \(\mathrm{OR}_n\). Take $N(x) = \sum_{i \text{ odd}} 10^i x_i$ and $D(x) = 1 + \sum_i 10^i x_i$, both of degree $1$, and let $h$ be the highest position with $x_h = 1$ (with $h=0$ for $x = 0^n$, where $N/D = 0$). Then $10^h \le D \le 1 + \tfrac{10}{9}(10^h-1) < 1.112\cdot 10^h$. If $h$ is odd then $10^h \le N \le \tfrac{100}{99}10^h$, so $N/D \ge 0.899$; if $h$ is even then $N \le \tfrac{100}{99}10^{h-1}$, so $N/D \le 0.102$. Hence $|N/D - \mathrm{OMB}| \le 0.102$ everywhere, for every $n$ (the true maximum is $0.092$). Compare $\widetilde{\deg} = \Theta(\sqrt n)$ and $\mathrm{D} = n$. MahadevdeWolf15
ADDRESS / multiplexer total \(\Theta(k)\) putative Upper: $\mathrm{rdeg}_{\varepsilon} \le \mathrm{rdeg} = O(k)$. Lower: the same restriction to $\mathrm{PARITY}_k$, whose approximate rational degree is $\Theta(k)$. So postselection does not help the multiplexer at all. MahadevdeWolf15
Binary tree navigation total \(\Theta(k)\) putative Upper: $\mathrm{rdeg}_{\varepsilon} \le \mathrm{rdeg} = O(k)$. Lower: a rational approximation survives the substitution of the \(\widetilde{\deg}_{\varepsilon}(f)\) line, so $\mathrm{rdeg}_{\varepsilon}(\mathrm{Nav}_k) \ge \mathrm{rdeg}_{\varepsilon}(\mathrm{PARITY}_{k-1}) = \Omega(k)$. Postselection is useless here, unlike for \(\mathrm{MAJ}_n\) where it gives an exponential saving. MahadevdeWolf15
TRIBES total \(O(\log n)\) putative Upper bound only, and it is $w$: put $S(x) = \sum_j \prod_{i \in T_j} x_i$, of degree $w$, and take $r = 3S/(1+3S)$. On $0$-inputs no tribe is all-ones, so $S = 0$ and $r = 0$; on $1$-inputs $S \ge 1$ and $r \ge 3/4$. No lower bound beyond the trivial $1$ is known -- the restriction to a single tribe only gives $\mathrm{rdeg}_{\varepsilon}(\wedge_w) = 1$, as at \(\mathrm{AND}_n\). MahadevdeWolf15
AND-OR tree (depth 2) total \(O(n)\) Approximate rational degree is at most both $\mathrm{rdeg} = n$ and $\widetilde{\deg} = \Theta(n)$. No matching lower bound is available: $\mathrm{rdeg}_{1/3}$ is not known to be bounded below by any of $\mathrm{bs}$, $\lambda$ or $\mathrm{Q}$.
NAND tree (balanced AND-OR formula) total \(O(\sqrt N)\) At most both $\mathrm{rdeg} = \Theta(\sqrt N)$ and $\widetilde{\deg} = \Theta(\sqrt N)$.
Recursive MAJORITY-of-3 total \(O(2^d)\) At most both $\mathrm{rdeg} \le 2^d$ and $\widetilde{\deg} = \Theta(2^d)$.
Kushilevitz's function (iterated) total \(O(N^{0.6131})\) At most $\widetilde{\deg} = O(N^{0.6131})$, and also at most $\mathrm{rdeg} \le 3^k$.
Rubinstein's function total \(O(\sqrt N)\) At most $\widetilde{\deg} = \Theta(\sqrt N)$; the competing bound $\mathrm{rdeg} \le N/2$ is far weaker.
Ambainis-Sun function total \(O(N^{3/4})\) At most $\widetilde{\deg} = O(N^{3/4})$; the competing bound $\mathrm{rdeg} \le \mathrm{C} = \Theta(N)$ is weaker.
AND composed with NOT-EXACT-HALF total \(O(n) = O(\sqrt N)\) Approximate rational degree is at most the exact rational degree, and the recorded $\mathrm{rdeg} = \Theta(n)$ is already a full power below $\widetilde{\deg} = \tilde\Theta(n^{3/2})$ and two powers below $\deg = \Theta(n^2)$. This is exactly the point of the function: rational approximation is cheap here even though polynomial approximation is not. IJKKKSWW23
Meiburg's tournament-subcube function total \(\le 7923.9^{\,d}\) putative $\mathrm{rdeg}_{1/3} \le \widetilde{\deg} \le \deg \le 7923.9^{\,d}$.
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $\tilde h_{1,m,m}$: $\mathrm{rdeg}_{1/3}\le\widetilde{\deg}=\widetilde O(n^{1/4})$ (a polynomial is a rational function with denominator $1$).
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{rdeg}_{1/3}\le\min\{\mathrm{rdeg},\widetilde{\deg}\}=\widetilde O(\sqrt n)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n^{2/3})\) Squeeze: $\mathrm{rdeg}_{1/3}\le\min\{\mathrm{rdeg},\widetilde{\deg}\}=\widetilde O(n^{2/3})$.
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{rdeg}_{1/3}\le\min\{\mathrm{rdeg},\widetilde{\deg}\}=\widetilde O(\sqrt n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) Squeeze: $\mathrm{rdeg}_{1/3}\le\min\{\mathrm{rdeg},\widetilde{\deg}\}=\widetilde O(n^{1/3})$.
Ambainis' exact-quantum function total \(O(2^d)\) Squeeze: $\mathrm{rdeg}_{1/3}\le\mathrm{rdeg}_0\le\deg=2^d$; approximation only helps.
FORRELATION partial \(\Theta(1)\) A polynomial is a rational function with denominator $1$, so $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg} = O(1)$; and at least $1$.
k-FORRELATION partial \(O(k)\) A polynomial is a rational function with denominator $1$, so $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg} = O(k)$.
Simon's problem partial \(O(n)\) At most $\widetilde{\deg} = O(n)$, a rational function with denominator $1$.
Deutsch-Jozsa partial \(1\) At most $\mathrm{rdeg} = 1$, and at least $1$.
Unique search partial \(1\) $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} = 1$. Against $\widetilde{\deg} = \Theta(\sqrt n)$ this is an unbounded partial-function separation of approximate rational degree from approximate degree -- rational approximation is not required to stay bounded off the promise, and here that is worth a quadratic factor. IJKKKSWW23
Two-or-none search partial \(1\) $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} = 1$.
Marked bit partial \(1\) $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} = 1$. IJKKKSWW23
Dense marked bit partial \(1\) $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} = 1$. IJKKKSWW23
Gap-Majority partial \(O(\min(n, 1/\delta))\) $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg}_\varepsilon = O(\min(n,1/\delta))$. Contrast the exact $\mathrm{rdeg} = \Theta(n)$.
Gap-Majority at constant gap partial \(O(1)\) $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg} = O(1)$. Contrast the exact $\mathrm{rdeg} = \Theta(n)$: on partial functions the two versions of rational degree are unboundedly far apart.
Approximate index partial \(\Theta(1)\) $\mathrm{rdeg}_\varepsilon \le \mathrm{rdeg} = \Theta(1)$.
Collision problem partial \(O(n^{1/3})\) $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg}_\varepsilon = O(n^{1/3})$.
Element distinctness total \(O(n^{2/3})\) $\mathrm{rdeg}_{\varepsilon} \le \widetilde{\deg}_{\varepsilon} = O(n^{2/3})$. The exact rational degree is much bigger -- see \(\mathrm{rdeg}(f)\) -- so allowing error is what buys the $n^{1/3}$ factor.
Ambainis-Belovs function partial \(O(1)\) $\mathrm{rdeg}_{\varepsilon} \le \mathrm{rdeg} = O(1)$.
Surjectivity total \(\tilde\Omega(\sqrt n),\ \tilde O(n^{3/4})\) putative Upper: $\mathrm{rdeg}_\varepsilon\le\widetilde{\deg}_\varepsilon$ (\(\mathrm{rdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\)). Lower: if $p/q$ approximates $f$ to $1/3$ with $q>0$, then $p-q/2$ has the sign of $f-1/2$ everywhere, so $\mathrm{sdeg}\le\mathrm{rdeg}_{1/3}$; and $\mathrm{sdeg}=\tilde\Theta(\sqrt n)$. MahadevdeWolf15
$k$-distinctness total \(O\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) $\mathrm{rdeg}_\varepsilon\le\widetilde{\deg}_\varepsilon$ (\(\mathrm{rdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\)), and the recorded approximate degree upper bound is the tight quantum one. No lower bound is recorded: the sign degree of $k$-distinctness is not known here, so the $\mathrm{sdeg}\le\mathrm{rdeg}_{1/3}$ route gives nothing.
Triangle finding total \(O(m^{5/4})\) $\mathrm{rdeg}_\varepsilon\le\widetilde{\deg}_\varepsilon=O(m^{5/4})$ (\(\mathrm{rdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\)). The $\mathrm{sdeg}\le\mathrm{rdeg}_{1/3}$ route gives no lower bound here, since no sign-degree bound is recorded for triangle finding.
Recursive Fourier sampling partial \(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.
Ordered search partial \(1\) $1\le\mathrm{rdeg}_{1/3}\le\mathrm{rdeg}=1$. Note the contrast with $\widetilde{\deg}=\Omega(\log n/(\log\log n)^2)$: approximate degree demands boundedness off the promise, rational approximation does not.
Inner product mod 2 total \(\Theta(n)\) putative Lower: a rational $1/3$-approximation $p/q$ makes $(p - q/2)\,q$ a sign-representing polynomial of degree $\le 2\,\mathrm{rdeg}_{\varepsilon}$, so $\mathrm{rdeg}_{\varepsilon}(f) \ge \mathrm{sdeg}(f)/2 = \Omega(n)$. Upper: $\mathrm{rdeg}_{\varepsilon} \le \widetilde{\deg} = \Theta(n)$. Post-selection buys nothing on the bent function.
Minsky-Papert one-in-a-box total \(\Omega(m),\ O(m^{3/2})\) Lower: a rational $1/3$-approximation $p/q$ makes $(p - q/2)\,q$ a sign-representing polynomial of degree $\le 2\,\mathrm{rdeg}_{\varepsilon}$, so $\mathrm{rdeg}_{\varepsilon}(f) \ge \mathrm{sdeg}(f)/2 = \Omega(m)$ by [MinskyPapert69]. Upper: $\mathrm{rdeg}_{\varepsilon} \le \widetilde{\deg} = O(m^{3/2})$. Rational approximation famously does not compose -- the outer rational function is evaluated at perturbed inputs where its denominator can vanish -- so the $O(\log)$ rational approximations of the individual $\mathrm{AND}$ and $\mathrm{OR}$ gates give nothing for the tree. MinskyPapert69