Q The Query Complexity Zoo
\(\mathrm{DIST}^k_n\)

$k$-distinctness

$\mathrm{Q} = \Theta(n^{3/4 - 1/(4(2^k-1))})$, settled in 2026 after fourteen years; the approximate degree is still open.

total quantum arity: $n$ symbols over an alphabet $[q]$ (element queries); $k$ is a constant

Description

Decide whether some symbol occurs at least $k$ times in the list. $k = 2$ is the complement of \(\mathrm{ED}_n\). On the indicator matrix of the list it is $\mathrm{OR}_q \circ \mathrm{THR}^k_n$ restricted to Hamming weight $\le n$.

Formal definition

$$\mathrm{DIST}^k(x) \;=\; \bigvee_{i_1 < \cdots < i_k}\ [\,x_{i_1} = \cdots = x_{i_k}\,].$$

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· For constant $k$ and alphabet size $q = \Omega(n^2)$. Upper: [Belovs12kdist], a learning graph of cost $O(n^{1 - 2^{k-2}/(2^k-1)})$ -- the same exponent, $2/3$ at $k=2$ and $5/7$ at $k=3$. Lower: [Belovs26kdist, Thm. 1.1], by a compressed-oracle framework that subsumes the polynomial method; the same paper recovers $\Omega(n^{2/3})$ for element distinctness (its Thm. 6.10). Marked medium confidence only because the lower bound is a 2026 preprint; the exponent matches the 2012 algorithm exactly. Earlier: $O(n^{k/(k+1)})$ by quantum walk [Ambainis07]. Belovs12kdist Belovs26kdist
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\tilde\Omega\!\big(n^{3/4-1/(4k)}\big),\ O\!\big(n^{3/4-1/(4(2^k-1))}\big)\)· Open, so recorded as a range. Lower: [MTZ20, Thm. 17 / Cor. 18] for $2 \le k \le \log^4 q$ -- the first proof that $4$-distinctness is strictly harder than element distinctness. Upper: [Sherstov21, Thm. 1.1], degree $O(\sqrt n \cdot \min\{n,q\}^{1/2 - 1/(4(1-2^{-k}))})$, and $\tilde O(n^{3/4})$ for all $k \le \mathrm{polylog}(n)$ [MTZ20, Thm. 2]. The 2026 quantum lower bound does not transfer: [BT22] ask exactly how fast $\widetilde{\deg}$ approaches $n^{3/4}$ and it is still open. MTZ20 Sherstov21 BT22
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) Read everything; the lower bound is the usual hybrid argument in the element-query model.
\(\mathrm{D}(f)\) Deterministic query complexity \(n\) Element-query model.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\)· Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\)· Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\)· Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· $\mathrm{MAdv}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{MAdv}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)$ here.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(k\) putative Exhibit the $k$ positions carrying a repeated symbol. Counting a query as one symbol read, as throughout this entry and \(\mathrm{ED}_n\).
\(\mathrm{C}^0(f)\) 0-certificate complexity \(n\) putative Take a $0$-input in which one symbol occurs exactly $k-1$ times and everything else is distinct. Leave any other position unread and it could be overwritten with that symbol, completing a $k$-fold repeat; so the certificate must read all $n$ symbols.
\(\mathrm{C}(f)\) Certificate complexity \(n\) $\mathrm{C} = \max(\mathrm{C}^0,\mathrm{C}^1) = \max(n,k) = n$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(k\) putative The cheapest certificate anywhere is a $k$-fold repeat; every $0$-input costs $n$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(k\) putative At a $1$-input every sensitive position must destroy every $k$-fold repeat, so it lies in all of them; a $1$-input with a single $k$-group therefore has sensitivity exactly $k$, and no $1$-input has more. The same argument caps $\mathrm{bs}^1$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(k\) putative Disjoint sensitive blocks at a $1$-input must each meet every $k$-group, and a $k$-group has only $k$ positions, so $\mathrm{bs}^1 \le k$; the single-$k$-group input attains it.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\Theta(n)\) putative On the $0$-input of the $\mathrm{C}^0$ note, overwriting any of the $n-k+1$ positions outside the $(k-1)$-group with that group's symbol flips the answer. So the sensitivity is wildly asymmetric: $\Theta(n)$ on $0$-inputs against $k$ on $1$-inputs.
\(\mathrm{s}(f)\) Sensitivity \(\Theta(n)\) $\mathrm{s} = \max(\mathrm{s}^0,\mathrm{s}^1) = \Theta(n)$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\Theta(n)\) The $n-k+1$ singleton blocks of the $\mathrm{s}^0$ note are disjoint, and $\mathrm{bs}^0 \le n$.
\(\mathrm{bs}(f)\) Block sensitivity \(\Theta(n)\) $\mathrm{s} \le \mathrm{bs} \le n$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(n)\) Between $\mathrm{bs} = \Theta(n)$ and $n$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(n)\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n)\) $\mathrm{RC} = \Theta(\mathrm{FC}) = \Theta(n)$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(n)\) Squeezed between $\mathrm{fbs} = \Theta(n)$ and $\mathrm{C} = n$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(n\) Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(n\) Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\) $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(n)$; also capped by $\mathrm{R} = \Theta(n)$. The classical adversary is tight here even though the positive quantum adversary is not.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(\sqrt n)\) putative The certificate barrier $\mathrm{Adv}(f) \le \sqrt{\mathrm{C}^0 \mathrm{C}^1} = \sqrt{nk} = O(\sqrt n)$ for constant $k$ -- so the positive-weights adversary cannot even reach the $\Omega(n^{2/3})$ of \(\mathrm{ED}_n\), let alone the true exponent. This is why every lower bound in the row above goes through the polynomial method or a compressed oracle.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$, and $\mathrm{FC} = \Theta(n)$ here. Note this is below $\mathrm{Q}$, as it must be -- quantum certificate complexity is not a lower bound on $\mathrm{Q}$ in any useful sense here.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) Every symbol is relevant, so a non-adaptive algorithm reads all of them; $\mathrm{D} = n$ anyway.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(n)$.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(n)\) Squeezed between $\mathrm{fbs} = \Theta(n)$ and $\mathrm{C} = n$; equivalently $\Theta(\mathrm{CA})$, which is also $\Theta(n)$ here. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(n)\) For constant $k$ the correct sandwich $\mathrm{R}_0 \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23] closes: $\mathrm{R}_0 = \Theta(n)$ and $\mathrm{C}^0\mathrm{C}^1 = n \cdot k = \Theta(n)$. The value happens to agree with the one previously recorded, but the old justification -- $\mathrm{CG} \le \mathrm{D}$ -- is false in general: $\mathrm{CG}$ can exceed the arity, as it does for $\oplus_n$. For growing $k$ the ceiling degrades to $O(nk)$. CGLMSG23
\(\chi(f)\) Conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \chi(g) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. As on \(\mathrm{SURJ}_{N,R}\), the lower end rests on the observation that the [JainKlauck10] arguments survive the relaxation of the completeness constraint; the upper end is unconditional. JainKlauck10
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\tilde\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $O(\mathrm{R}\log \mathrm{R}) = O(n\log n)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\tilde\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n^{3/4-1/(4(2^k-1))})$ by the row above. Even the fourteen-year-old exponent is noise-robust up to a log.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega\!\big(n^{3/4 - 1/(4(2^k-1))}\big),\ O(n)\) Only the generic $\mathrm{Q}_{\varepsilon} \le \mathrm{Q}_0 \le \mathrm{D}$. Zero error is not obviously free here, unlike on the search problems in this file: a $k$-collision found is a $k$-element certificate, but certifying that no symbol repeats $k$ times costs $\mathrm{C}^0 = n$, so a zero-error algorithm must be right on $0$-inputs with certainty.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Omega\!\big(n^{3/4 - 1/(4(2^k-1))}\big),\ O(n)\) Same window as $\mathrm{Q}_0$, which it contains: $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} \le \mathrm{D} = n$. The usual $\mathrm{Q}_{\mathrm{E}} \ge \deg/2$ route is unavailable because $\deg(\mathrm{DIST}^k)$ is itself not recorded.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) putative Upper: $\mathrm{RS}\le\mathrm{R}=\Theta(n)$ [BenDavidKothari18]. Lower: take the input consisting of $n/(k-1)$ values each repeated exactly $k-1$ times -- a $0$-input with no room to spare. Starring any single symbol sabotages it: left alone its group stays at $k-1$ copies, changed to another group it makes that group $k$. So all $n$ symbols are sabotage positions over one base input, and finding the $\ast$ is finding a marked symbol among $n$. BenDavidKothari18
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n)\) $\mathrm{noisyR}\le\mathrm{R}$ [BenDavidBlais20composition], and $\mathrm{R}=\Theta(n)=\Theta(\text{arity})$ forces equality [CKMPSS23]. CKMPSS23 BenDavidBlais20composition
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\)· putative Upper: $\mathrm{D}^{\mathrm{prod}}\le\mathrm{R}=\Theta(n)$. Lower: fix (point masses are product measures) $n/2$ symbols as $m=n/(2(k-1))$ groups of $k-1$ copies of distinct values $a_1,\dots,a_m$; let free symbol $j$ independently be $a_{j\bmod m}$ with probability $1/M$ and otherwise a private value $b_j$ used nowhere else, where $M=n/2$. No accidental collision is possible, so the instance is a $1$-input exactly when some free symbol picks its $a$, an $\mathrm{OR}$ of $M$ independent events of probability $1/M$. Any tree that leaves a constant fraction of the free symbols unread errs with constant probability, so $\mathrm{D}^\mu=\Omega(n)$. Alphabet size $m+M=O(n)$ suffices.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\tilde\Omega\!\big(n^{3/4-1/(4k)}\big),\ O(n)\) $\widetilde{\deg}_\varepsilon\le\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), taking the lower end from the recorded approximate degree and the upper end from $\mathrm{R}=\Theta(n)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) $\mathrm{rdeg}_\varepsilon\le\widetilde{\deg}_\varepsilon$ (\(\mathrm{rdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\)), and the recorded approximate degree upper bound is the tight quantum one. No lower bound is recorded: the sign degree of $k$-distinctness is not known here, so the $\mathrm{sdeg}\le\mathrm{rdeg}_{1/3}$ route gives nothing.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15]; see \(\mathrm{rdeg}_{\varepsilon}(f)\). Equivalently, post-selection is at least as strong as the plain quantum algorithm, whose cost is $\Theta(n^{3/4-1/(4(2^k-1))})$. MahadevdeWolf15
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(n\log n)}\)· putative For $q\ge n$ (so that the all-distinct inputs exist) every $0$-input needs all $n$ symbols read, since $\mathrm{C}^0=n$, so distinct $0$-inputs end at distinct leaves; the $n!$ orderings of $n$ fixed distinct values already give $\mathrm{DTsize}\ge n!=2^{\Theta(n\log n)}$. The ceiling is $q^n$, which matches for $q=\mathrm{poly}(n)$.

Separations it witnesses

Notes

Open, per [Belovs26kdist, ยง7]: the approximate degree; alphabets smaller than $n^2$; non-constant $k$; and removing the "$\Omega(n)$ singletons" assumption on the input distribution. The framework is explicitly incomparable to the Liu-Zhandry compressed-oracle results, which fix a uniformly random input.