Parity-labelled FIND-1
The decision version of FIND-1: zero-error $O(1)$ against deterministic $n/4+1$.
partial arity: $n$ bits, $4 \mid n$
Description
Promise $|x| = n/4$, and $\mathrm{supp}(x)$ lies entirely inside the odd coordinates or entirely inside the even ones. Output $1$ in the first case, $0$ in the second. Splitting $[n]$ by parity is inessential -- any two fixed halves do -- but it makes the promise short to state.
The design has two halves to it. Every input carries $n/4$ ones and each one of them, wherever it is, names the answer on its own; so a single successful probe both finds and certifies, and a Las Vegas algorithm is done after four expected queries. A deterministic algorithm gets no such luck: the adversary answers $0$ and it has to exhaust an entire half. \(\mathrm{Find1}_{\ge n/2}\) makes that trade for a relation; the parity label is what turns it into a partial function, which is the setting where $\mathrm{D}$ vs $\mathrm{R}_0$ was otherwise witnessed only by the quadratic total-function \(g_{\mathrm{ABBLSS}}\) separation.
Restricted to the odd half the promise reads "all-zero, or exactly balanced", which is \(\mathrm{DJ}_n\) -- hence $\mathrm{Q}_E = 1$ below. What Deutsch-Jozsa lacks is a witness for its constant case, and that is exactly what the even half supplies here: it is why $\mathrm{R}_0$ is $O(1)$ here and $\Theta(n)$ there.
Formal definition
$\mathrm{Find1}^{\mathrm{par}}_n(x) = \mathbb{1}[\,\mathrm{supp}(x) \subseteq \mathrm{Odd}\,]$ restricted to $\{x : |x| = n/4,\ \mathrm{supp}(x) \subseteq \mathrm{Odd} \text{ or } \mathrm{supp}(x) \subseteq \mathrm{Even}\}$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{D}(f)\) Deterministic query complexity | \(n/4+1\) putative | Exactly. Upper: query $n/4+1$ odd positions; a $1$ among them says $\mathrm{supp}(x) \subseteq \mathrm{Odd}$, and all-zero rules that case out, since $n/4$ ones would then have to fit into the $n/4-1$ odd positions left over. Lower: the adversary answers $0$ throughout. After $q_{\mathrm{odd}}$ odd and $q_{\mathrm{even}}$ even queries both completions survive as long as $n/2 - q_{\mathrm{odd}} \ge n/4$ and $n/2 - q_{\mathrm{even}} \ge n/4$, so the algorithm must spend $n/4+1$ queries inside one parity class before either answer is safe. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(1)\) putative | At most $4$. Query uniformly random unqueried positions until one returns $1$, then report the parity of its index -- which is certain, since a single $1$ pins the side of the promise. A random position is $1$ with probability $n/4 \,/\, n$, so sampling without replacement finds one after $(n+1)/(n/4+1) < 4$ expected queries, and the algorithm never errs. Note this is the expected-cost convention (\(\mathrm{R}_{0}(f)\)); worst-case zero error would be $\mathrm{D}$ by definition, which is the whole content of the separation. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(1)\) | $\mathrm{R} \le \mathrm{R}_0 = O(1)$, and at least one query. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(1)\) | Squeezed: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0 = O(1)$. Since the algorithm only ever answers from a $1$ it has seen, one-sided error costs nothing -- as at \(\mathrm{Find1}_{\ge n/2}\), and unlike \(\mathrm{GapMaj}^{\delta}_{n}\), where $\mathrm{R}^1 = \Theta(n)$. |
| \(\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{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(1)\) putative | Sampling needs no adaptivity: read $10$ uniformly random positions and answer from any that is $1$. A position is $1$ with probability $1/4$, so this fails with probability $(3/4)^{10} < 0.06$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(n/4+1\) putative | The same count as $\mathrm{D}$, which never used adaptivity: a fixed set missing $n/4$ odd and $n/4$ even positions is consistent with both answers, and a fixed set of $n/4+1$ odd positions decides. So all the power here is in the coins, not in adaptivity. |
| \(\mathrm{C}(f)\) Certificate complexity | \(1\) putative | One queried $1$ certifies the answer at every input: if $x_i = 1$ with $i$ odd then no $0$-input of the promise agrees, since $0$-inputs vanish on all odd coordinates. So $\mathrm{C} = 1$ against $\mathrm{D} = n/4+1$ -- the certificate is as short as it can be and locating it is the entire problem. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(1\) putative | See $\mathrm{C}$: a single even-indexed $1$. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(1\) putative | See $\mathrm{C}$: a single odd-indexed $1$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(1\) putative | Equal to $\mathrm{C}$: every input has $n/4$ one-bit certificates, so the min over inputs and the max coincide. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(1\) putative | The one-bit certificate is already a verifier that needs no coins: query the fixed position $i \in \mathrm{supp}(x)$, accept iff it returns $1$. Every $y$ of the opposite value has $y_i = 0$, so it is rejected with certainty. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(1\) putative | Weight $1$ on a single $i \in \mathrm{supp}(x)$ is feasible -- every $y$ of the opposite value differs from $x$ at $i$ -- and $\mathrm{FC} \ge \mathrm{fbs} = 1$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(1\) putative | Between $\mathrm{bs} = 1$ and $\mathrm{C} = 1$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(1\) putative | Exactly $1$. A sensitive block at $x$ must produce a domain input of the other value, and such an input is $0$ on all of $\mathrm{supp}(x)$; so every sensitive block contains $\mathrm{supp}(x)$ and no two of them are disjoint. One block exists -- swap $\mathrm{supp}(x)$ for any $n/4$ coordinates of the other parity -- so $\mathrm{bs} = 1$ while $\mathrm{D} = n/4+1$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(1\) putative | See $\mathrm{bs}$; the two sides are symmetric. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(1\) putative | See $\mathrm{bs}$; the two sides are symmetric. |
| \(\mathrm{s}(f)\) Sensitivity | \(0\) putative | Identically zero: a single flip changes $|x|$ to $n/4 \pm 1$ and leaves the promise, so the sensitivity graph on the domain has no edges at all. An exact-weight promise kills $\mathrm{s}$ the same way a gapped one does at \(\mathrm{GapMaj}^{\delta}_{n}\). |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(0\) putative | See $\mathrm{s}$: no domain neighbours anywhere. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(0\) putative | See $\mathrm{s}$: no domain neighbours anywhere. |
| \(\lambda(f)\) Spectral sensitivity | \(0\) putative | The sensitivity graph is empty (see $\mathrm{s}$), so its spectral norm is $0$. |
| \(\deg(f)\) Exact degree | \(1\) putative | The linear polynomial $p(x) = (4/n)\sum_{i \text{ odd}} x_i$ is $1$ on every $1$-input and $0$ on every $0$-input of the promise. Off the promise it runs up to $2$, which is allowed for $\deg$ but not for $\widetilde{\deg}$ -- see the settings note at \(\deg(f)\). |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Theta(1)\) | At most $2\mathrm{Q} = O(1)$, and at least $1$. Unlike $\deg$ this is not witnessed by the linear polynomial above, which is unbounded off the promise. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(1\) putative | $\sum_{i \text{ odd}} x_i - 1/2$ has the right sign at every promise input. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(1\) putative | $\sum_{i \text{ odd}} x_i$ is nonzero on the domain exactly at the $1$-inputs. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(1\) putative | $\max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$, and the complement is handled by $\sum_{i \text{ even}} x_i$. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(1\) | $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil = 1$. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(1)\) | $\mathrm{Q} \le \mathrm{R} = O(1)$, and at least one query. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Theta(1)\) | $\mathrm{Q}_0 \le \mathrm{R}_0 = O(1)$; also $\mathrm{Q}_0 \le \mathrm{Q}_E = 1$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(1\) putative | One query, with certainty. Prepare $|\psi\rangle = (n/2)^{-1/2}\sum_{i \text{ odd}}|i\rangle$ and apply the phase oracle $|i\rangle \mapsto (-1)^{x_i}|i\rangle$. On a $0$-input every odd coordinate is $0$, so the state is unchanged; on a $1$-input exactly $n/4$ of the $n/2$ odd coordinates carry a $-1$, so the state is orthogonal to $|\psi\rangle$. The projective measurement $\{|\psi\rangle\langle\psi|,\, I - |\psi\rangle\langle\psi|\}$ then answers with probability $1$ either way. This is \(\mathrm{DJ}_n\) run on the odd half, and it is why the promise fixes $|x| = n/4$: half of the odd coordinates, so the $1$-case is exactly balanced. Contrast \(\mathrm{GapMaj}^{\delta}_{n}\) and \(\mathrm{Find1}_{\ge n/2}\), where exactness costs $\Theta(n)$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(\Theta(n)\) putative | The caterpillar "query odd positions until the first $1$" has one leaf per stopping point, so $O(n)$; and a tree of depth $d$ has more than $d$ leaves, so $\Omega(n)$ by $\mathrm{D} = n/4+1$. As at \(\mathrm{Find1}_{\ge n/2}\), the deterministic hardness is depth, not size. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(1\) putative | That caterpillar has rank $1$ -- one child of every internal node is a leaf -- and rank $0$ means a constant answer. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(0\) putative | The support of a product distribution on $\{0,1\}^n$ is a subcube, and the domain here contains no subcube of dimension $\ge 1$: flipping any single coordinate breaks $|x| = n/4$. So every product $\mu$ supported on the promise is a point mass, hence one-sided, and $\mathrm{D}^\mu = 0$ -- against $\mathrm{R} = \Theta(1)$ the measure is simply blind, as at \(\mathrm{GapMaj}^{\delta}_{n}\) and \(\mathrm{forr}\). |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(1)\) | By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(1)$. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Theta(1)\) putative | Read each of $O(1)$ sampled positions $O(1)$ times and majority-vote: $\mathrm{N}_p = O(\mathrm{R})$, and $\mathrm{N}_p \ge \mathrm{R}$ always. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(1)\) | At most $\mathrm{R} = O(1)$, and at least $1$: there is nothing for cheap low-bias queries to buy. |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Theta(1)\) | Between $\mathrm{Q} = \Theta(1)$ and $\mathrm{N}_p = \Theta(1)$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\Theta(1)\) | At most $\mathrm{Q} = \Theta(1)$, and at least $1$. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(1)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(O(1)\) | $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(1)$. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(1)\) | Sandwiched between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}$. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(1)\) | $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(1)\) | A lower bound on $\mathrm{R} = O(1)$, and at least a constant for a non-trivial problem. The classical adversary is powerless here -- correctly, since $\mathrm{R} = O(1)$. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(1)\) | At most $\mathrm{Q} = \Theta(1)$, and at least $1$. |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\Theta(1)\) | Between $1$ and $\mathrm{R} = O(1)$. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(O(1)\) | $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(1)$. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(O(1)\) | $\overline{\mathrm{prt}} \le \mathrm{prt} = O(1)$. |
Separations it witnesses
-
Unbounded, and the point of the example: $\mathrm{R}_0 = O(1)$ while $\mathrm{D} = n/4+1$. Zero error is no obstacle when every input carries $n/4$ self-certifying witnesses; what defeats determinism is having to find one. \(\mathrm{Find1}_{\ge n/2}\) says the same thing for relations, but a relation cannot witness the partial-function cell, which is why this one is needed.
-
Unbounded: $\mathrm{C} = 1$ against $\mathrm{D} = n/4+1$. The total-function bound $\mathrm{D} \le \mathrm{C}^0\,\mathrm{C}^1$ needs both sides to have short certificates and needs the search for them to be guided; here both sides do and it still fails.
-
Unbounded: one exact quantum query against $n/4+1$ deterministic ones. \(\mathrm{DJ}_n\) makes the same point, but there $\mathrm{R}_0 = \Theta(n)$, so the collapse is quantum; here $\mathrm{R}_0 = O(1)$ too, and every measure that is not $\mathrm{D}$ itself is constant.
Cited as a witness by
-
\(\mathrm{R}_0(\mathrm{Find1}^{\mathrm{par}}_n) = O(1),\ \ \mathrm{D}(\mathrm{Find1}^{\mathrm{par}}_n) = n/4+1\)