Q The Query Complexity Zoo

Cost conventions: worst case, expected cost, zero error

Why R_0 must be an expected-cost measure, and when worst-case and expected cost differ.

Two orthogonal choices define a randomized measure:

  1. Error model. Zero error / one-sided error / bounded error / unbounded error. ($\mathsf{ZPP}$ / $\mathsf{RP}$ / $\mathsf{BPP}$ / $\mathsf{PP}$.)
  2. Cost model. Worst-case number of queries over all coin flips, or expected number of queries.

The zero-error trap

If you demand zero error and worst-case cost, you get $\mathrm{D}(f)$ exactly: fix the coins of an always-correct depth-$T$ algorithm and you have a deterministic depth-$T$ tree. So $\mathrm{R}_0$ and $\mathrm{Q}_0$ cannot be worst-case-cost measures with a forced answer.

There are two ways out, and they give the same measure up to a factor of two: charge the expected number of queries, or keep worst-case cost and allow the answer $\bot$ with probability $\le 1/2$. Markov truncation at twice the expected cost converts the first into the second; repeating until an answer appears converts the second into the first. The zoo takes $\mathrm{R}_0$ in the expected-cost form and $\mathrm{Q}_0$ in the $\bot$ form, purely because that is how each is usually written -- and applying the truncation to a classical Las Vegas algorithm gives $\mathrm{Q}_0(f)\le 2\,\mathrm{R}_0(f)$, for relations as much as for total functions. A $\mathrm{Q}_0$ value above the function's own $\mathrm{R}_0$ is therefore an error, not a convention clash.

One trap of its own: allowing $\bot$ weakens the polynomial method. A $T$-query zero-error algorithm makes $p_1$ vanish on $f^{-1}(0)$ rather than equal $f$, so it bounds $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$, not $\deg$: the floor is $\mathrm{rdeg}/2$, and $\deg/2$ is a floor for $\mathrm{Q}_{\mathrm{E}}$ only. On \(\bar{\wedge}\text{-tree}\) the two differ by a square.

The bounded-error case

$\bar{\mathrm{R}}_\varepsilon(f) \le \mathrm{R}_\varepsilon(f)$ always, and Markov + truncation gives $\mathrm{R}_{\varepsilon+\delta}(f)\le \bar{\mathrm{R}}_\varepsilon(f)/\delta$. So for constant error the two agree up to constants and nobody bothers to distinguish them.

They stop agreeing as $\varepsilon \to 0$, and this is not pedantry:

  • $\mathrm{R}(\mathrm{MAJ}_n\circ g^n)=\Theta(n\cdot\bar{\mathrm{R}}_{1/n}(g))$ [GoosMaystre21] -- the expected complexity at error $1/n$ is the right quantity, and converting to $\mathrm{R}_{1/n}$ would cost a factor $n$.
  • The strong direct sum $\bar{\mathrm{R}}_\varepsilon(f^k)=\Theta(k\bar{\mathrm{R}}_{\varepsilon/k}(f))$ [BlaisBrody19] is false for worst-case cost.
  • Yao's minimax question is about expected cost; see Yao's minimax and its failures.

Unbounded error

Letting $\varepsilon \to 1/2$ gives the $\mathsf{PP}$-flavoured measures: \(\mathrm{sdeg}(f)\) (sign degree), \(\mathrm{PostQ}_{\varepsilon}(f)\) (post-selected quantum), and \(\mathrm{rdeg}_{\varepsilon}(f)\). See param-adeg-eps.