\(\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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{s}^0(f) = 0\)
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = n\) against \(\mathrm{s}(f) = 0\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{CA}(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = n\) against \(\mathrm{CA}(f) = \Theta(1)\)
-
\(\mathrm{UC}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{\mathrm{pub}}(f_n) = O(1)\)from \(\mathrm{UC}_{\min}(f) = n\) against \(\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{s}^1(f) = 0\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{*}(f_n) = O(1)\)from \(\mathrm{rank}(f) = n\) against \(\mathrm{CG}^{*}(f) = \Theta(1)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{\mathrm{E}}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{Q}_{\mathrm{E}}(f) = 1\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{0}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{Q}_{0}(f) = 1\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{\mathrm{ns}}(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \widetilde\Theta(n)\) against \(\mathrm{CG}^{\mathrm{ns}}(f) = \Theta(1)\)
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{s}^1(f) = 0\)
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = n\) against \(\mathrm{s}^0(f) = 0\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{\mathrm{pub}}(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = n\) against \(\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(1)\)
-
\(\mathrm{UC}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{CA}(f_n) = O(1)\)from \(\mathrm{UC}_{\min}(f) = n\) against \(\mathrm{CA}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{\mathrm{E}}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{Q}_{\mathrm{E}}(f) = 1\)
… and 65 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Unbounded: $\mathrm{fbs} = 2 - 2^{1-n}$ but $\mathrm{C} = \mathrm{C}_{\min} = n$. Total functions satisfy $\mathrm{C} = O(\mathrm{fbs}^2)$.
-
Unbounded: $\mathrm{CA} = \Theta(1)$ against $\mathrm{R} = \Theta(n)$ -- the classical adversary method is useless on the Hadamard promise. Compare \(\mathrm{SIMON}_n\), where the same argument gives an exponential gap.
-
The "find $s$" version is a relation: $\mathrm{Q}_E=1$ vs $\mathrm{R}=\Omega(n)$.
-
Unbounded: $\mathrm{C} = \mathrm{C}_{\min} = n$ against $\mathrm{Q}_E = 1$ -- one exact quantum query beats every certificate at every input.