Q The Query Complexity Zoo
\(\mathrm{DJ}_n\)

Deutsch-Jozsa

Exact quantum: 1 query vs $N/2+1$ deterministic queries (but $\mathrm{R}=O(1)$).

partial quantum arity: $N=2^n$ bits

Description

Promise: $x$ is constant or exactly balanced. Decide which.

Formal definition

$\mathrm{DJ}(x) = 0$ if $|x| = 0$ or $|x| = N$; $=1$ if $|x| = N/2$; undefined otherwise.

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(1\) DeutschJozsa92
\(\mathrm{D}(f)\) Deterministic query complexity \(N/2+1\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(O(1)\) Two random samples suffice with bounded error -- so this is an exact-quantum-vs-deterministic separation only.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(1\) $\mathrm{Q} \le \mathrm{Q}_E = 1$, and one query is needed.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(1\) Same: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = 1$.
\(\mathrm{s}(f)\) Sensitivity \(0\) putative For $N \ge 4$ no single flip stays inside the promise: a constant input becomes weight $1$ or $N-1$, a balanced one weight $N/2 \pm 1$. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ while $\mathrm{D} = N/2+1$. The extreme illustration of why sensitivity says nothing about partial functions.
\(\mathrm{bs}(f)\) Block sensitivity \(2\) putative At $0^N$ the sensitive blocks are exactly the $\binom{N}{N/2}$ half-sized sets, and two disjoint halves fit; at a balanced $x$ they are exactly $\mathrm{supp}(x)$ and its complement, again two disjoint blocks. Three disjoint blocks of size $N/2$ do not fit in $N$ coordinates, so $\mathrm{bs}^0=\mathrm{bs}^1=2$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(2\) putative The fractional relaxation buys nothing: every sensitive block has size exactly $N/2$, so a feasible weighting has $\tfrac N2\sum_B w_B = \sum_i \mathrm{load}(i) \le N$.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(N/2+1\) putative Fixing $|S|$ coordinates to $0$ still admits a balanced input whenever $|S| \le N/2$, so a $0$-certificate needs $N/2+1$ zeros -- and that many suffice.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(2\) putative Every other domain point consistent with "one $0$ here, one $1$ there" is balanced, hence also a $1$-input. Nothing needs to be pinned down beyond killing the two constants.
\(\mathrm{C}(f)\) Certificate complexity \(N/2+1\) putative From $\mathrm{C}^0$. With $\mathrm{fbs}=2$ this is a much cleaner unbounded $\mathrm{C}$-vs-$\mathrm{fbs}$ witness than any total function can give.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(2\) putative Attained on the balanced inputs.
\(\deg(f)\) Exact degree \(2\) putative On the promise $f$ is the symmetric function $t \mapsto [t = N/2]$ of $t=|x|$ restricted to $t \in \{0, N/2, N\}$, and $(1 - (1-2t/N)^2)$ interpolates it. Degree $1$ is impossible since $p(0)=p(N)=0$ forces $p \equiv 0$. So $\mathrm{deg} = 2 = 2\,\mathrm{Q}_E$: Deutsch-Jozsa makes $\mathrm{deg} \le 2\mathrm{Q}_E$ tight.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(2\) putative Symmetrise: a degree-$1$ univariate with $|q(0)|,|q(N)| \le 1/3$ has $q(N/2) = \tfrac12(q(0)+q(N))$, which cannot reach $2/3$. So approximation does not help either.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(N/2+1\) putative Adaptivity is worthless here: any fixed $N/2+1$ positions contain a $0$ and a $1$ of every balanced input (which has exactly $N/2$ of each), so reading them decides. And $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(N/2+1\) putative Zero error means every run ends on a certificate, and on a constant input that is $N/2+1$ queries; $\mathrm{R}_0 \le \mathrm{D}$ gives the match. So the $\mathrm{R}=O(1)$ upper bound is entirely a bounded-error phenomenon -- a clean $\mathrm{R}_0$ vs $\mathrm{R}$ separation of unbounded ratio for a partial function.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(1)\) putative Read $10$ fixed positions and answer "balanced" iff they are not all equal; a balanced input fools this with probability $2^{-9}$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(1)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(1\) Sandwiched: $\mathrm{Q} \le \mathrm{Adv}^{\pm} \le \mathrm{Q}_E$, with both ends $1$.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(1\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}_E$, with both ends $1$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(1)\) Sandwiched between $\mathrm{Q}$ and $\mathrm{R} = O(1)$.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(1)\) Sandwiched: $\mathrm{RC} \le \mathrm{R} = O(1)$, and every measure here is at least $1$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(1)\) Equal to $\mathrm{fbs} = 2$ by LP duality; also $\le \mathrm{R} = O(1)$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(1)\) Sandwiched between $\widetilde{\deg} = 2$ and $\mathrm{R} = O(1)$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(1)\) Sandwiched: $\mathrm{prt}_\varepsilon \le \mathrm{R} = O(1)$, and at least $1$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(1)\) Sandwiched: $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{R} = O(1)$, and at least $1$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(0\) putative See $\mathrm{s}$: no single flip of a constant input stays in the promise.
\(\mathrm{s}^1(f)\) 1-sensitivity \(0\) putative See $\mathrm{s}$: flipping one bit of a balanced input gives weight $N/2 \pm 1$, outside the promise.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(2\) putative At $0^N$ the sensitive blocks are exactly the $N/2$-sized sets, and two disjoint ones fit.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(2\) putative At a balanced $x$ the sensitive blocks are exactly $\mathrm{supp}(x)$ and its complement.
\(\lambda(f)\) Spectral sensitivity \(0\) putative The sensitivity graph of $\mathrm{DJ}$ on its promise has no edges at all (see $\mathrm{s}=0$), so its adjacency matrix is zero. Spectral sensitivity, which for total functions satisfies $\deg \le \lambda^2$ and lower-bounds $\mathrm{Q}$, degenerates completely: $\lambda = 0$ while $\deg = 2$ and $\mathrm{D} = N/2+1$.
\(\mathrm{rank}(f)\) Decision tree rank \(2\) putative Query $x_1, x_2, \dots$ and stop as soon as two different values appear (answer "balanced") or $N/2+1$ equal values appear (answer "constant"). Each of the root's two subtrees is a caterpillar, hence of rank $1$, so the tree has rank $2$; and $\mathrm{rank} \ge \mathrm{C}_{\min} = 2$. So rank sees none of the $\Theta(N)$ depth -- all of it is caterpillar.
\(\mathrm{DTsize}(f)\) Decision tree size \(\Theta(N)\) putative The tree above has one leaf per stopping point on each of its two branches, so $O(N)$; and a tree of depth $d$ has more than $d$ leaves, so $\Omega(N)$ from $\mathrm{D} = N/2+1$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(N/2+1\) putative Squeezed: $\mathrm{C} \le \mathrm{UC} \le \mathrm{D}$, with both ends $N/2+1$. (The leaves of the tree above are an unambiguous family of exactly this width.)
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(O(N)\) Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = N/2 + 1$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs, so the width-$2$ certificates on the balanced side do not give $O(1)$: a balanced input has $N^2/4$ disagreeing pairs, and an unambiguous family must still name one of them, which is the same obstruction that forces $\mathrm{UC} = \Omega(N)$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(N/2+1\) putative Squeezed: $\mathrm{C} \le \mathrm{SP} \le \mathrm{D}$, with both ends $N/2+1$; the tree's leaves are the subcube partition.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(\sqrt N)\) putative A genuinely intermediate value, strictly between $\mathrm{fbs} = 2$ and $\mathrm{C} = N/2+1$. Upper: put $w^x_i = 1/\sqrt N$ at the two constant inputs and $w^y_i = 2/\sqrt N$ everywhere at each balanced $y$; a constant $x$ and a balanced $y$ differ on $N/2$ coordinates, giving $\sum_{i : x_i \ne y_i} w^x_i w^y_i = (N/2)(2/N) = 1$, and every weight vector sums to at most $2\sqrt N$. Lower: at $x = 0^N$, for each balanced $y$ we need $1 \le \sum_{i \in \mathrm{supp}(y)} w^x_i w^y_i \le k \max_{i \in \mathrm{supp}(y)} w^x_i$, so fewer than $N/2$ coordinates can have $w^x_i < 1/k$; hence $k \ge \sum_i w^x_i \ge N/(2k)$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(1)\) A lower bound on $\mathrm{Q} = 1$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(1)\) An algorithm computing $f$ also verifies it, so $\mathrm{QC} \le \mathrm{Q} = 1$. Compare $\mathrm{C} = N/2+1$: this is the extreme case of quantum certificates beating classical ones.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(1)\) A lower bound on $\mathrm{R} = O(1)$.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(1)\) putative Read $O(1)$ fixed positions $O(1)$ times each and majority-vote away the noise.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(1)\) At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = 1$.
\(\mathrm{sdeg}(f)\) Sign degree \(2\) putative Symmetrising a sign-representing polynomial gives a univariate $q$ on $t \in \{0, N/2, N\}$ with $q(0), q(N) > 0 > q(N/2)$, impossible for degree $1$; and $1 - 2(1-2t/N)^2$ has the right signs. So $\mathrm{sdeg} = \widetilde{\deg} = \deg = 2$ -- no relaxation of degree helps at all.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(N)\) putative The private-coin certificate game is linear here, and the argument is short. Upper: both players output a uniformly random index of $[N]$; when Alice holds a constant $x$ and Bob a balanced $y$ they differ on exactly $N/2$ indices, so they win with probability $(N/2)/N^2 = 1/(2N)$. Lower: fix Alice at $x = 0^N$, where she has a single output distribution $p$. Against a balanced $y$ her success is $\sum_{i \in \mathrm{supp}(y)} p(i)\,q_y(i) \le \max_{i \in \mathrm{supp}(y)} p(i)$. Let $y$ be the indicator of the $N/2$ indices with the smallest $p(i)$: the $(N/2)$-th largest value of $p$ is at most $2/N$, so the value is at most $2/N$ and $\mathrm{CG} \ge N/2$. Note the total-function sandwich $\mathrm{R}_0 \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ is not available on a promise problem and is not used. CGLMSG23
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(1)\) One shared random index $i$, output by both players, already wins with probability $1/2$. So $\mathrm{CG}^{\mathrm{pub}} \le 2$, matching $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA}) = \Theta(1)$. Against $\mathrm{CG} = \Theta(N)$ this is an unbounded private-versus-public certificate game gap on a partial function: shared randomness is what lets the two players agree on where to look. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(1)\) Between $\mathrm{CG}^{\mathrm{ns}}$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(1)\) Between $1$ and $\mathrm{CG}^{*} = \Theta(1)$. CGLMSG23
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(N/2+1\) putative One-sided error does not help, even though the cheap side is only two queries. Fix coins $r$ for which the run on $0^N$ outputs $0$ -- at least $2/3$ of them do -- and let $L \le q$ be the positions it reads. If $L \le N/2$ some balanced $y$ agrees with all of them, so the same run outputs $0$ on a $1$-input, which zero error on the $1$-side forbids. Hence $q \ge N/2+1$, and $\mathrm{R}^1 \le \mathrm{R}_0 = N/2+1$. Compare $\mathrm{R} = O(1)$.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(1)\) Sandwiched: $\Omega(\sqrt{\mathrm{R}}) \le \mathrm{LR} \le \mathrm{R} = O(1)$.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(1)\) Sandwiched: $\Omega(\sqrt{\mathrm{R}}) \le \bar\chi = O(\mathrm{LR}) = O(1)$.
\(\chi(f)\) Conflict complexity \(\Theta(1)\) At most $\bar\chi = \Theta(1)$, and at least $1$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(1)\) At most $\bar\chi = \Theta(1)$; finding a $\ast$ in a sabotaged input is as easy as the problem itself here.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(1)\) Sandwiched: $\Omega(\mathrm{Q}) \le \mathrm{R}^{*} \le \mathrm{R} = O(1)$.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(1)\) At most $\mathrm{R} = O(1)$, and at least $1$.
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity \(\Theta(1)\) Squeezed: $\mathrm{noisyR} = \Theta(1) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(1)$. Also what Theorem 8 of [BenDavidBlais20composition] predicts -- $\mathrm{noisyR}^{\mathrm{na}} = \Theta(\mathrm{R}^{\mathrm{na}})$ holds for partial functions. BenDavidBlais20composition
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(1)\) At most $\mathrm{D}^\mu = \Theta(1)$ for every $\mu$, and at least one query.
\(\mathrm{rdeg}(f)\) Rational degree \(1\) putative Rational degree collapses below exact degree. By the characterisation $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$: $\mathrm{ndeg}(f) = 1$ (see below), and $\mathrm{ndeg}(\bar f) = 1$ too, since $p(x) = |x| - N/2$ vanishes on exactly the balanced inputs. So $\mathrm{rdeg} = 1 < \deg = \widetilde{\deg} = \mathrm{sdeg} = 2$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(1\) At most $\mathrm{rdeg} = 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)$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(2\) Squeezed between $\mathrm{sdeg} = 2$ and $\widetilde{\deg} = 2$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(1\) $\mathrm{NQ} = \lceil\mathrm{ndeg}/2\rceil = 1$, from $\mathrm{ndeg} = 1$ below.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(1\) putative Nondeterministic degree collapses where ordinary degree does not. Take $p = \sum_i c_i x_i$ with $\sum_i c_i = 0$ and the $c_i$ otherwise generic: then $p$ vanishes at $0^N$ and at $1^N$, while $\sum_{i \in \mathrm{supp}(y)} c_i \ne 0$ for every balanced $y$ because generic points of the hyperplane $\sum c_i = 0$ avoid the finitely many further hyperplanes. So $\mathrm{ndeg} = 1 < \deg = 2$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(1)\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(1)$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(2\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 2$. In particular the measure that governs $\mathrm{Search}(\varphi)$ says nothing here. GoosPitassi14

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. 249 in total, strongest first.

… and 235 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses

Cited as a witness by