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

Simon's problem

The first exponential quantum speedup for a promise problem: $\mathrm{Q}=O(n)$ vs $\mathrm{R}=\Omega(2^{n/2})$.

partial quantum arity: $n2^n$ bits (a function table $g:\{0,1\}^n\to\{0,1\}^n$)

Description

Promise: $g$ is either injective, or two-to-one with $g(x)=g(x\oplus s)$ for a hidden $s\ne 0$. Decide which (or, in the search version, find $s$).

Formal definition

Input: the table of $g:\{0,1\}^n\to\{0,1\}^n$. Promise: either $g$ is injective, or $\exists s \ne 0^n$ with $g(x)=g(y) \iff y \in \{x, x\oplus s\}$.

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(n)\)· Simon's algorithm gives $O(n)$; the matching $\Omega(n)$ quantum lower bound is also known, so the exponential speedup is exactly quadratic-free: $\mathrm{R} = 2^{\Theta(\mathrm{Q})}$. Simon97
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(2^{n/2})\) Simon97
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(2^{n/2})\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and $\mathrm{R}_{\varepsilon}(f) = \Theta(2^{n/2})$ here.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(1)\) Both certificate complexities are $O(1)$ under the promise -- exhibiting one colliding pair $x \ne y$ with $f(x)=f(y)$ settles the question -- so the positive adversary gives $O(1)$ against $\mathrm{Q} = \Theta(n)$. The largest known gap between $\mathrm{Adv}$ and $\mathrm{Q}$. HoyerSpalek05
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(2^{n/2})\) putative Both directions are about difference sets. Upper: query $A\cup B$ where $A = \{(u,0^{n/2})\}$ and $B = \{(0^{n/2},v)\}$, which is $2^{n/2+1}-1$ points whose pairwise differences $(u,0)\oplus(0,v)=(u,v)$ exhaust $\mathbb{F}_2^n$; a two-to-one $g$ with shift $s$ must therefore repeat a value inside $A\cup B$, and an injective one never does. Lower: an adversary answering with fresh distinct values survives as long as some shift is unexcluded, and $q$ queries exclude only the $\binom q2$ shifts realised as differences, so $q = \Omega(2^{n/2})$. Note this matches $\mathrm{R}$: the birthday paradox buys randomness nothing here, because covering all $2^n$ differences deterministically is just as cheap.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\Theta(2^{n/2})\) putative The $A\cup B$ query set above is fixed in advance, so the deterministic upper bound is already non-adaptive; and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(2^{n/2})\) putative Sampling $O(2^{n/2})$ uniformly random points is non-adaptive, and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Theta(2^{n/2})$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(2^{n/2})\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}_0 \le \mathrm{D}$, both ends $\Theta(2^{n/2})$.
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(2^{n/2})\) putative A certificate for an injective $g$ must exclude every shift $s\ne 0$, i.e. exhibit for each $s$ a queried pair $x, x\oplus s$ with different values; a set of $q$ positions realises at most $\binom q2$ differences, so $q \ge 2^{n/2}$, and the $A\cup B$ set above attains it. A two-to-one $g$ certifies in two queries, so $\mathrm{C}^0$ and $\mathrm{C}^1$ are wildly asymmetric here.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(2\) putative On a two-to-one input, one colliding pair.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Theta(2^{n/2})\) putative The injective side. See $\mathrm{C}$: a certificate must exhibit, for every shift $s \ne 0$, a queried pair $x, x\oplus s$ with $g(x) \ne g(x \oplus s)$, and $q$ queried points realise only $\binom q2$ differences.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(2\) putative The two-to-one side: one colliding pair $g(x) = g(y)$, $x \ne y$, already rules out injectivity, and the promise then forces the answer.
\(\mathrm{s}(f)\) Sensitivity \(0\) putative Counting a query as one evaluation of $g$, as everywhere in this entry. Changing $g$ at a single point never stays inside the promise: from an injective $g$ it can create at most one collision, and a two-to-one function needs all $2^{n-1}$ pairs to collide; from a two-to-one $g$ it orphans exactly one pair, leaving a function that is neither injective nor two-to-one. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ against $\mathrm{D} = \Theta(2^{n/2})$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(0\) putative See $\mathrm{s}$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(0\) putative See $\mathrm{s}$.
\(\mathrm{bs}(f)\) Block sensitivity \(2\) putative Every sensitive block has size $\ge 2^{n-1}$: crossing between the injective and the two-to-one side requires touching each of the $2^{n-1}$ pairs $\{x, x\oplus s\}$ at least once. Two disjoint blocks of exactly that size exist -- the two transversals of the pairing -- and three do not fit in $2^n$ points. So $\mathrm{bs}^0 = \mathrm{bs}^1 = 2$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(2\) putative See $\mathrm{bs}$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(2\) putative See $\mathrm{bs}$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(2\) putative The fractional relaxation buys nothing: every sensitive block has $\ge 2^{n-1}$ of the $2^n$ coordinates, so $2^{n-1}\sum_B w_B \le \sum_i \mathrm{load}(i) \le 2^n$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(2\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(1)\) putative $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$: to reject one fixed input of the other kind it is enough to query a random point of a block on which the two differ, which succeeds with constant probability. Rejecting them one at a time is free; $\mathrm{R} = \Theta(2^{n/2})$ is the price of rejecting all of them at once.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(2^{n/2})\) putative Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $\Theta(2^{n/2})$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(2^{n/2})\) putative Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $\Theta(2^{n/2})$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(O(2^{n/2})\) Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = \Theta(2^{n/2})$, and nothing sharper is available. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs: the cheap two-query collision certificates on the "periodic" side are massively ambiguous, since a periodic $g$ contains $2^{n-1}$ of them, and disambiguating them by "first collision in lex order" costs the full $\Theta(2^{n/2})$ again.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(2^{n/2})\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(2^{n/2})$.
\(\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 oracle functions, and no rectangle inside the promise meets both sides. Suppose it held a $1$-$1$ function $g$ and a two-to-one function $h$, and let $h(i) = h(j) = v$ with $i \ne j$. The hybrid agreeing with $h$ at $i$ and with $g$ elsewhere lies in the rectangle, so it must be on the promise, which forces it to be $1$-$1$, i.e. $v \notin g(\mathrm{dom} \setminus \{i\})$. But then the hybrid agreeing with $h$ at both $i$ and $j$ and with $g$ elsewhere -- also in the rectangle -- takes the value $v$ exactly twice and every other value once, so it is neither $1$-$1$ nor two-to-one. Hence every product $\mu$ is one-sided and $\mathrm{D}^\mu = 0$, an exponential gap below $\mathrm{R} = \Theta(2^{n/2})$. See \(\mathrm{forr}\) for the general form of this collapse.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(n)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(n)$. Against $\mathrm{Adv} = O(1)$ this is the largest known gap between the positive and the general adversary.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(n)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, both ends $\Theta(n)$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(n)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(n)$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$, and independently $\mathrm{QC} \le \mathrm{Q}$. Against $\mathrm{C} = \Theta(2^{n/2})$ this is an exponential quantum-certificate advantage: a constant-size quantum certificate replaces a difference-covering set.
\(\lambda(f)\) Spectral sensitivity \(0\) putative Spectral sensitivity is at most sensitivity for partial $f$, and $\mathrm{s} = 0$ here: the sensitivity graph on the promise has no edges. So $\lambda = 0$ while $\mathrm{Q} = \Theta(n)$.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\Theta(1)\) At most $\mathrm{C}^1 = 2$, the colliding pair: put $p = \sum_{x<y} \mathbb{1}[g(x) = g(y)]$, a degree-$2$ polynomial in the indicator variables that is $0$ on injective inputs and positive on two-to-one ones.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil = 1$: one nondeterministic quantum query guesses a colliding pair. Against $\mathrm{R} = \Theta(2^{n/2})$.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(O(n)\) $\widetilde{\deg} \le 2\mathrm{Q} = O(n)$, in the indicator variables $\mathbb{1}[g(x) = v]$.
\(\mathrm{sdeg}(f)\) Sign degree \(O(n)\) At most $\widetilde{\deg}_+ \le \widetilde{\deg} = O(n)$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(O(n)\) At most $\widetilde{\deg} = O(n)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(n)\) At most $\widetilde{\deg} = O(n)$, a rational function with denominator $1$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(n)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(n)$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(2^{n/2})\) Sandwiched: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, both $\Theta(2^{n/2})$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(O(2^{n/2})\) putative Directly, not through $\mathrm{C}$: put $w^g_x = 2^{-(n-1)/2}$ at every one of the $2^n$ points. Two promise inputs of different value differ at $\ge 2^{n-1}$ points (turning a two-to-one $g$ into an injective one requires touching each of its $2^{n-1}$ colliding pairs), so $\sum_{x : g(x)\ne g'(x)} w^g_x w^{g'}_x \ge 1$, and each weight vector sums to $\sqrt 2\,2^{n/2}$. The textbook bound $\mathrm{EC} \le \mathrm{C}$ is a total-function statement and is not used.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(1)\) putative The shared-randomness strategy needs nothing but the code distance: both players output the same uniformly random point $x$ of the domain of $g$, and win iff $g(x) \ne g'(x)$. Two promise inputs of different value differ at $\ge 2^{n-1}$ of the $2^n$ points, so this wins with probability $\ge 1/2$ and $\mathrm{CG}^{\mathrm{pub}} \le 2$. In general $\mathrm{CG}^{\mathrm{pub}}(f) \le n/d$ where $d$ is the least Hamming distance between two domain points of different value. 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] and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$ above; and $\mathrm{CA} \ge 1$. So the classical adversary bound is constant while $\mathrm{R} = \Theta(2^{n/2})$ -- Simon's problem is an extreme instance of the [CGLMSG23] observation that $\mathrm{R}$ can be exponentially larger than $\mathrm{CA}$ on partial functions. Every query resolves half of the surviving alternatives, so no adversary distribution can survive. CGLMSG23
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Omega(2^{n/4})\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ for every partial $f$, and $\mathrm{LR} \le \mathrm{R} = \Theta(2^{n/2})$.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Omega(2^{n/4})\) $\bar\chi = \Omega(\sqrt{\mathrm{R}})$ even for partial $g$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R}$.
\(\chi(f)\) Conflict complexity \(O(2^{n/2})\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$.
\(\mathrm{RS}(f)\) Sabotage complexity \(O(2^{n/2})\) From $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R})$.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(O(2^{n/2})\) $\mathrm{R}^{*} \le \mathrm{R}$; from below $\mathrm{R}^{*} = \Omega(\mathrm{LR}) = \Omega(2^{n/4})$ and $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(n)$.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(O(2^{n/2})\) At most $\mathrm{R}$.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(2^{n/2})\) putative At least $\mathrm{R}$; and reading each sampled point $O(1)$ times and majority-voting each of the $n$ output bits costs only $O(\log n)$ per read, absorbed into the $\Theta(2^{n/2})$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\widetilde\Theta(n)\) Between $\mathrm{Q} = \Theta(n)$ and $\mathrm{Q}\log\mathrm{Q} = O(n\log n)$. So the exponential separation survives a noisy oracle.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(O(2^{n/2})\) Sandwiched between $\widetilde{\deg} = O(n)$ and $\mathrm{R}_\varepsilon = \Theta(2^{n/2})$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(2^{n/2})\) From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(2^{n/2})\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(2^{n/2})\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(2^{n/2})$, since the decision version has a unique correct answer.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(2\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 2$. GoosPitassi14
\(\deg(f)\) Exact degree \(O(n)\) putative Exponentially below $\mathrm{D}$. Let $z_{i,v}$ be the degree-$n$ conjunction of input bits asserting $g(i) = v$. Then $P = \sum_{i<j}\sum_v z_{i,v}z_{j,v}$ counts colliding pairs, so $P = 0$ on injective tables and $P = 2^{n-1}$ on two-to-one tables, and $2^{1-n}P$ represents $f$ exactly on the promise with degree $2n$ in the input bits. Beware: $P$ is wildly unbounded off the promise, so this does not bound $\widetilde{\deg}$, which is separately $O(n)$ from $2\mathrm{Q}$.
\(\mathrm{rdeg}(f)\) Rational degree \(O(2^{n/2})\) At most $\mathrm{C} = \Theta(2^{n/2})$; from below $\mathrm{rdeg} \ge \mathrm{ndeg} = \Theta(1)$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(O(2^{n/2})\) At most $\mathrm{D} = \Theta(2^{n/2})$, at least $\mathrm{Q} = \Theta(n)$. Simon-style interference gives no exact algorithm: the hidden shift is only recovered with bounded error.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(O(2^{n/2})\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = O(2^{n/2})$.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(O(2^n)\) putative Private coins. An injective $g$ and a two-to-one $g^{\prime}$ must differ on at least $2^{n-1}$ of the $2^n$ table entries: for each of the $2^{n-1}$ pairs $\{x, x\oplus s\}$ we have $g^{\prime}(x)=g^{\prime}(x\oplus s)$ but $g(x)\ne g(x\oplus s)$, so at least one of the two entries moves. Both players output a uniformly random entry, winning with probability $\ge 2^{n-1}/(2^n)^2$. Contrast $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$: this is another unbounded private-versus-public certificate-game 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. 158 in total, strongest first.

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

Separations it witnesses