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

Bernstein-Vazirani

One exact quantum query recovers an $n$-bit secret that costs $n$ classical queries.

partial quantum arity: $2^n$ bits (or $n$ bits with an inner-product oracle)

Description

Promise: $x_i = \langle s, i\rangle \bmod 2$ for a hidden $s \in \{0,1\}^n$. Output $s$ (or one bit of it).

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(1\) BernsteinVazirani97
\(\mathrm{D}(f)\) Deterministic query complexity \(n\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) Recovering $s$ needs $n$ bits of information from one-bit answers, so $\mathrm{R} = \Omega(n)$ even with bounded error; and $\mathrm{R} \le \mathrm{D} = n$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(1\) $\mathrm{Q} \le \mathrm{Q}_E = 1$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(1\) $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = 1$.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(0\) putative The support of a product distribution is a rectangle $\prod_i S_i$ of truth tables. If two truth tables in it differ at position $i$, then copying that one bit from the second into the first gives another point of the rectangle, and a string that differs from a linear function in exactly one place is not linear -- so it is off the promise. Hence any rectangle inside the promise is a single point and $\mathrm{D}^\mu = 0$ for every product $\mu$, against $\mathrm{R} = \Theta(n)$. See the \(\mathrm{forr}\) entry for the general phenomenon.
\(\mathrm{C}(f)\) Certificate complexity \(n\) putative A set of queried positions $i_1,\dots,i_k$ reveals $\langle s, i_j\rangle$, and pins $s$ down exactly when the $i_j$ span $\mathbb{F}_2^n$ -- so every certificate has $\ge n$ queries, and $e_1,\dots,e_n$ is one. Since this holds at every input, $\mathrm{C}_{\min} = \mathrm{C} = n$: BV is certificate-uniform.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(n\) putative See $\mathrm{C}$: the spanning requirement is input-independent.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(n\) putative Zero error forces a spanning query set on every run, and $\mathrm{R}_0 \le \mathrm{D} = n$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) putative The spanning set $e_1,\dots,e_n$ is fixed in advance, and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) putative Same non-adaptive algorithm; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$.
\(\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{s}(f)\) Sensitivity \(0\) putative The promise inputs are exactly the $2^n$ codewords of the Hadamard code, and two distinct codewords differ in $2^{n-1} \ge 2$ positions. So no single flip stays inside the promise and $\mathrm{s} = 0$, against $\mathrm{D} = n$.
\(\mathrm{bs}(f)\) Block sensitivity \(1\) putative The sensitive blocks at the input $x$ indexed by $s$ are exactly the sets $B_d = \{i : \langle d, i\rangle = 1\}$ for $d = s \oplus s' \ne 0$. Any two of them meet -- $|B_{d} \cap B_{d'}| = 2^{n-2} > 0$ for distinct nonzero $d, d'$ -- so no two disjoint sensitive blocks exist. Hence $\mathrm{s} = 0 < \mathrm{bs} = 1$, itself a small curiosity that no total function allows.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(1)\) putative Exactly $(2^n-1)/2^{n-1} = 2 - 2^{1-n}$. Each block $B_d$ has $2^{n-1}$ elements and each nonzero coordinate $i$ lies in exactly $2^{n-1}$ of the $2^n-1$ blocks, so by symmetry the LP optimum puts weight $2^{1-n}$ on every block. Against $\mathrm{C} = n$ this is an unbounded $\mathrm{C}$-vs-$\mathrm{fbs}$ gap.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(1)\) Equal to $\mathrm{fbs}$ by LP duality.
\(\lambda(f)\) Spectral sensitivity \(0\) putative The sensitivity graph is empty (see $\mathrm{s} = 0$), so $\lambda = 0$ while $\mathrm{Q}_E = 1$ and $\mathrm{D} = n$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(n\) putative Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(n\) putative Squeezed between $\mathrm{C}_{\min} = n$ and $\mathrm{UC} = n$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(n\) putative Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$; the $2^n$ subcubes "$x_{e_1} = b_1, \dots, x_{e_n} = b_n$" partition the promise.
\(\mathrm{rank}(f)\) Decision tree rank \(n\) putative Squeezed between $\mathrm{C}_{\min} = n$ and $\mathrm{D} = n$. Unlike \(\mathrm{DJ}_n\), where the depth is all caterpillar and $\mathrm{rank} = 2$, here every query genuinely branches.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^n\) putative Every leaf subcube has codimension $\ge \mathrm{C}_{\min} = n$, so there are at least $2^n$ leaves; and querying $e_1, \dots, e_n$ gives exactly $2^n$.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(1)\) putative One uniformly random query already distinguishes the codeword $x$ from any fixed other codeword with probability $1/2$, which is all $\mathrm{RC}$ asks; and $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$. The contrast with $\mathrm{R} = \Theta(n)$ is the point: rejecting one alternative at a time is easy, rejecting all $2^n-1$ of them at once is not.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(n)$.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(n\) putative Parity queries buy nothing. A query on a set $S$ of positions returns $\bigoplus_{i \in S}\langle s, i\rangle = \langle s, \sum_{i \in S} i\rangle$ -- again a single linear functional of $s$ -- so $q$ queries reveal at most $q$ bits about the $n$-bit secret and $\mathrm{D}^{\oplus} \ge n$; and $\mathrm{D}^{\oplus} \le \mathrm{D} = n$. The Hadamard promise is precisely the fixed point of the parity model.
\(\mathrm{s}^0(f)\) 0-sensitivity \(0\) Both halves inherit $\mathrm{s} = \max\{\mathrm{s}^0,\mathrm{s}^1\} = 0$: no single flip of a Hadamard codeword lands back in the promise.
\(\mathrm{s}^1(f)\) 1-sensitivity \(0\) As for $\mathrm{s}^0$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$, and independently $\mathrm{QC} \le \mathrm{Q} = 1$. Against $\mathrm{C} = \mathrm{C}_{\min} = n$: a constant-size quantum certificate replaces a whole basis of $\mathbb{F}_2^n$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(1\) Sandwiched: $1 \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = 1$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(O(n)\) putative Weight $1$ on each of the $n$ positions $e_1,\dots,e_n$ and $0$ elsewhere, at every input. Two promise inputs with secrets $s \ne s'$ disagree at some $e_j$, since $s$ and $s'$ differ in some coordinate $j$, so the required product $\sum_{i : x_i \ne y_i} w^x_i w^y_i \ge 1$ holds and the scheme costs $n$. From below only $\mathrm{EC} \ge \mathrm{fbs} = \Theta(1)$; note $\mathrm{EC} \le \mathrm{C}$ is a total-function statement and is not what is used here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(1)\) putative Both players output the same uniformly random position $i \in [2^n]$; they win iff $x_i \ne y_i$, which for two distinct Hadamard codewords happens with probability exactly $1/2$. So $\mathrm{CG}^{\mathrm{pub}} \le 2$, and $\ge 1$ trivially. (In general $\mathrm{CG}^{\mathrm{pub}}(f) \le N/d$ for $d$ the minimum Hamming distance between differently-valued inputs.) CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(1)\) Between $\mathrm{CG}^{\mathrm{ns}} \ge 1$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$.
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(1)\) Between $1$ and $\mathrm{CG}^{*} = \Theta(1)$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(1)\)· From $\mathrm{CA} = \Theta(\mathrm{CG}^{\mathrm{pub}})$ [CGLMSG23] with $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. Directly: any two codewords disagree on half of the positions, so a uniformly random query kills half of the surviving adversary mass and no weighting scheme can survive $\omega(1)$ queries. The classical adversary bound therefore certifies nothing about $\mathrm{R} = \Theta(n)$. CGLMSG23
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Omega(\sqrt n)\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ and $\mathrm{LR} \le \mathrm{R} = \Theta(n)$; the true value is not pinned down here.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Omega(\sqrt n)\) $\bar\chi = \Omega(\sqrt{\mathrm{R}})$, and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(n)$.
\(\chi(f)\) Conflict complexity \(O(n)\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(n)$. The total-function lower bound $\chi = \Omega(\mathrm{bs})$ [Li18] would only give $\Omega(1)$ anyway.
\(\mathrm{RS}(f)\) Sabotage complexity \(O(n)\) $\mathrm{RS} = O(\bar\chi) = O(\mathrm{R}) = O(n)$.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(O(n)\) $\mathrm{R}^{*} \le \mathrm{R} = O(n)$; from below only $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(1)$, since quantum query complexity composes perfectly. ($\mathrm{LR} = O(\mathrm{R}^{*})$ is recorded only for total $f$.)
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(O(n)\) $\mathrm{noisyR} \le \mathrm{R} = O(n)$. The strengthening "$\mathrm{R} = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR} = \Theta(\mathrm{R})$" does not apply: the arity is $2^n$, not $n$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(O(n)\) $\mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon = O(n)$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(n)\) $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(n)$; from below $(1-4\varepsilon)\mathrm{CA} \le \mathrm{prt}_\varepsilon + \log(1/\varepsilon)$ gives only $\Omega(1)$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(n)\) $\mathrm{rprt} \le \mathrm{prt} = O(n)$.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\widetilde\Theta(n)\) Faulty-oracle noise costs at most a log: $\mathrm{R} \le \mathrm{N}_p = O(\mathrm{R}\log \mathrm{R})$ with $\mathrm{R} = \Theta(n)$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(1)\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ with $\mathrm{Q} = 1$, so a robust oracle costs only a constant here.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) Degenerate: the secret $s$ is unique, so there is only one valid output and a pseudo-deterministic algorithm is just a randomized one. Hence $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(n)$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(1\) Degenerate: every input is critical (one valid output), so the solution function is forced and $\mathrm{cbs} = \mathrm{bs} = 1$. GoosPitassi14
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(1\) At most $\mathrm{bs} = 1$, and at least $1$ at every input, since replacing the table by the codeword of any other secret is a sensitive block. So both one-sided values equal $1$ however the outputs are split into two classes.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(1\) See $\mathrm{bs}^0$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Squeezed: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, and both ends are $\Theta(n)$ here.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Omega(n),\ O(n^2)\) putative Two players hold the Hadamard codewords of distinct secrets $s \ne s^{\prime}$ and must agree on a position where the tables differ, with private coins only. Upper: both output a uniformly random one of the $n$ positions $e_1,\dots,e_n$; the tables differ at $e_j$ exactly when $s_j \ne s^{\prime}_j$, which happens for some $j$, so they win with probability $\ge 1/n^2$. Lower: fix the first player at $s$ with output distribution $p$ on $\{0,1\}^n$. The $n-1$ heaviest positions span a subspace of dimension $\le n-1$, so some $d \ne 0$ is orthogonal to all of them; against $s^{\prime} = s \oplus d$ the difference set is $\{i : \langle d,i\rangle = 1\}$, which misses all of them, and the win probability is at most the $n$-th largest value of $p$, hence $\le 1/n$. Against $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$ this is another unbounded private-versus-public gap, as on \(\mathrm{DJ}_n\).

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

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

Separations it witnesses