Q The Query Complexity Zoo
\(\mathrm{Q}_{\varepsilon}(f)\)

Bounded-error quantum query complexity

Number of applications of the phase/bit oracle O_x needed to compute f with error <= eps.

also written: Q_2(f), quantum decision tree complexity

Definition

A $T$-query quantum algorithm is $U_T O_x U_{T-1}\cdots O_x U_0 |0\rangle$, measured at the end; $O_x$ maps $|i,b\rangle\mapsto|i,b\oplus x_i\rangle$. $\mathrm{Q}_\varepsilon(f)$ is the least $T$ such that some algorithm outputs $f(x)$ with probability $\ge 1-\varepsilon$ for all $x$ in the domain. Unadorned $\mathrm{Q}(f):=\mathrm{Q}_{1/3}(f)$.

Parameters

\(\varepsilon\) (eps) default \(1/3\)range \([0, 1/2)\)

$\mathrm{Q}_\varepsilon(f) = O(\mathrm{Q}(f)\log(1/\varepsilon))$ by majority voting. For decision problems the $\log(1/\varepsilon)$ is sometimes removable via amplitude amplification when the algorithm has one-sided structure. In the small-bias regime $\varepsilon = 1/2-\gamma$ one has $\mathrm{Q}(f) = O(\gamma^{-1}\mathrm{Q}_{1/2-\gamma}(f))$ -- note $\gamma^{-1}$, not $\gamma^{-2}$: amplitude amplification is quadratically better than classical majority voting, which is the source of several quantum/classical gaps.

Detailed records: \(\mathrm{Q}_{\varepsilon}(f) \text{ as } \varepsilon\to 0\)

Basic facts

  • $\widetilde{\deg}(f) \le 2\,\mathrm{Q}(f)$ [BBCMdW01].
  • $\mathrm{D}(f) = O(\mathrm{Q}(f)^4)$ for total $f$ [ABKRT21], improving $O(\mathrm{Q}^6)$; matching separation $\mathrm{D}=\tilde\Omega(\mathrm{Q}^4)$ [ABBLSS17], so the exponent is 4, settled.
  • Quantum query complexity composes perfectly: $\mathrm{Q}(f\circ g) = \Theta(\mathrm{Q}(f)\mathrm{Q}(g))$.
  • For partial functions the gap with $\mathrm{R}$ is unbounded: $\mathrm{Q}=O(1)$ vs $\mathrm{R}=\tilde\Omega(n^{1-1/2k})$; exponential for Simon's problem.
  • The optimal total-function $\mathrm{R}$-versus-$\mathrm{Q}$ power is 4 [OpenAI26QuarticRQ]. The new family rules out every power below 4, matching $\mathrm{R}\le\mathrm{D}=O(\mathrm{Q}^4)$ [ABKRT21]; see \(F_{k,m}\).

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Q}_{\varepsilon}(f)\). “\(\mathrm{Q}_{\varepsilon}(f)\) in terms of it” is the pair with \(\mathrm{Q}_{\varepsilon}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\mathrm{Q}_{\varepsilon}(f)\) in terms of it It in terms of \(\mathrm{Q}_{\varepsilon}(f)\)
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity total1,1 partial1,1 relation1,1 open pair → total2,4 partial∞ relation∞ open pair →
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity total1,1 partial1,1 relation1,1 open pair → total2,4 partial∞ relation∞ derived open pair →
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation1,1 open pair → total4,4 partial∞ relation∞ open pair →
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total4,4 partial∞ open pair → total1,1 partial1,1 open pair →
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound total1,1 partial1,1 relation1,1 open pair → total1,1 partial1,1 relation1,1 derived open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 relation1,1 open pair → total4,4 partial∞ relation∞ open pair →

The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(\sqrt{n})\) Grover upper bound, BBBV lower bound. Exactly $\tfrac{\pi}{4}\sqrt n$ asymptotically. Grover96 BBBV97
AND total \(\Theta(\sqrt{n})\)
PARITY total \(\lceil n/2 \rceil\) One query decides the parity of two bits (Deutsch); this is exactly tight. BBCMdW01
MAJORITY total \(\Theta(n)\) Via Paturi: $\widetilde{\deg}(\mathrm{MAJ}) = \Theta(n)$ because the jump is at the middle layer. BBCMdW01 Paturi92
Threshold total \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) BBCMdW01 NayakWu99
Symmetric functions (general) total \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) Approximate degree characterises $\mathrm{Q}$ exactly (up to constants) for symmetric functions. BBCMdW01 Paturi92
EXACT-HALF total \(\Theta(n)\)
ODD-MAX-BIT total \(\Theta(\sqrt n)\) putative Upper: quantum maximum-finding [DurrHoyer96] locates the highest $1$ in $O(\sqrt n)$ queries; its parity is the answer. Lower: setting all even-indexed bits to $0$ restricts $\mathrm{OMB}$ to $\mathrm{OR}$ on the odd ones, so $\mathrm{Q} \ge \mathrm{Q}(\mathrm{OR}_{\lceil n/2\rceil}) = \Omega(\sqrt n)$.
ADDRESS / multiplexer total \(\Theta(k)\) Squeezed between $\widetilde{\deg}/2 = \Omega(k)$ and $\mathrm{D} = k+1$. Quantum buys nothing on the multiplexer.
Binary tree navigation total \(\Theta(k)\) putative Squeezed: $\widetilde{\deg}(f)/2 \le \mathrm{Q}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}(f) = \Theta(k)$ from the line above and $\mathrm{D}(f) = k$. So navigation admits no quantum speedup at all: the $k$ walk steps must be taken one after another even coherently, and the embedded \(\oplus_n\) certifies it.
TRIBES total \(\Theta(\sqrt n)\) Grover over the $s$ tribes, Grover inside each: $\sqrt s\cdot\sqrt w = \sqrt n$. Tight, since $\widetilde{\deg}=\Theta(\sqrt n)$. Grover96 BT22
AND-OR tree (depth 2) total \(\Theta(n) = \Theta(\sqrt N)\) Robust quantum search: no log factor. HoyerMoscadeWolf03 BBBV97
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\) Continuous-time algorithm [FGG08], discrete-query version [ACRSZ10]; lower bound from $\lambda$. FGG08 ACRSZ10
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) $\mathrm{Adv}^{\pm}(\mathrm{MAJ}_3)=2$ and $\mathrm{Adv}^\pm$ composes perfectly, so $\mathrm{Q} = \Theta(\mathrm{Adv}^\pm(\mathrm{MAJ}_3)^d)$. Reichardt11
Kushilevitz's function (iterated) total \(\Omega(\sqrt N),\ O(N)\) Not pinned. $\mathrm{Q}$ composes perfectly, so $\mathrm{Q}(K^{\circ k}) = \Theta(\mathrm{Adv}^{\pm}(K)^k)$ and the whole question is the value of the base adversary bound, which lies between $\lambda(K) = \sqrt6$ and $\mathrm{D}(K)=6$. The two ends give exactly $\sqrt N$ and $N$.
Rubinstein's function total \(\Theta(\sqrt N) = \Theta(n)\) putative Quantum query complexity composes exactly, $\mathrm{Q}(f\circ g) = \Theta(\mathrm{Q}(f)\mathrm{Q}(g))$, and $\mathrm{Q}(\mathrm{OR}_n) = \Theta(\sqrt n)$. For the gadget $\mathrm{Q}(g) = \Theta(\sqrt n)$: Grover over the $n/2$ pairs finds a fired pair in $O(\sqrt n)$ queries and a second Grover checks that no other bit is $1$; conversely restricting to the $n/2$ paired variables turns $g$ into $\mathrm{EXACT}_1$, which needs $\Omega(\sqrt n)$. So $\mathrm{Q} = \Theta(\sqrt n \cdot \sqrt n) = \Theta(\sqrt N)$, quadratically below $\mathrm{R} = \Theta(N)$ and matching the lower bound $\lambda = \sqrt N$. LMRSS11 Reichardt11 HLS07
Ambainis-Sun function total \(\Omega(\sqrt N),\ O(N^{3/4})\) putative Not pinned. Lower: $\mathrm{Q} = \Omega(\lambda) = \Omega(3k+2) = \Omega(\sqrt N)$. Upper: $f$ is a DNF with $m = (3k+2)(2k+1) = \Theta(N)$ terms of width $w = 3k+2 = \Theta(\sqrt N)$, so robust Grover over the terms with a Grover $\mathrm{AND}_w$ inside each costs $O(\sqrt m\cdot\sqrt w) = O(k^{3/2})$ with no log overhead [HoyerMoscadeWolf03]. Equivalently, $\mathrm{Q}$ composes and $\mathrm{Q}(\mathrm{OR}_{3k+2}) = \Theta(\sqrt k)$ while $\mathrm{Q}(g) = O(k)$. Closing the gap needs the exact adversary bound of the gadget, exactly as for \(K^{\circ k}\). HoyerMoscadeWolf03 ABKRT21
AND composed with NOT-EXACT-HALF total \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) Lower from $\mathrm{Q}=\Omega(\lambda)$ and the recorded $\lambda = \Theta(n^{3/2})$. Upper by perfect composition $\mathrm{Q}(f\circ g)=O(\mathrm{Q}(f)\mathrm{Q}(g))$ [LMRSS11, Reichardt11] with $\mathrm{Q}(\mathrm{AND}_n)=\Theta(\sqrt n)$ and the trivial $\mathrm{Q}(\overline{\mathrm{EH}}_n)\le n$; the gadget really does cost $\Theta(n)$, since a symmetric function has $\mathrm{Q}=\Theta(\sqrt{n(n-\Gamma)})$ [BBCMdW01] and $\Gamma(\overline{\mathrm{EH}}_n)=1$. LMRSS11 Reichardt11 BBCMdW01
Meiburg's tournament-subcube function total \(\ge 118.3^{\,d}\) putative $\mathrm{Q} = \Omega(\sqrt{\mathrm{bs}})$, and $\mathrm{bs} \ge 14011^{\,d}$.
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $f_{2m,m}$ [ABBLSS17, Thm 5, Cor. 7]: Grover search over columns costs $\widetilde O(\sqrt m)=\widetilde O(n^{1/4})$. ABBLSS17
Cheat-sheet functions total \(\widetilde\Theta(n)\) For $\mathrm{BKK}$: $\mathrm{Q}=\Omega(n/\log^5 n)$ by reduction from $k$-sum plus the quantum composition theorem [ABK16, Thm 10], and $\mathrm{Q}\le n$ trivially. The cheat sheet inherits it, $\mathrm{Q}(f_{\mathrm{CS}})=\Omega(\mathrm{Q}(f))$ [ABK16, Lem. 12], with a matching $\widetilde O(n)$ algorithm (solve the $10\log n$ copies, then read the indexed cell). ABK16
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Quantum query complexity is multiplicative under composition, so $\mathrm{Q}(\hat f)=\widetilde\Omega(n\cdot\mathrm{Q}(f))$; with the base $\mathrm{BKK}_{\mathrm{CS}}$ contributing $\mathrm{Q}(f)=\widetilde\Omega(n^2)$ this is $\widetilde\Omega(n^3)$ [BHT17, Cor. 2]. BHT17
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=\widetilde\Omega(n^{4/3})$. The ceiling is $\mathrm{Q}\le\mathrm{D}=\widetilde O(n^2)$.
Gilmer-Saks-Srinivasan functions total \(\Omega(\sqrt n)\) Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=\Theta(n)$.
Random-indicator gadget total \(\Omega(\sqrt n)\) Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=n$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=\widetilde\Theta(\sqrt n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6})\) Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=\widetilde\Theta(n^{1/3})$; the ceiling is $\mathrm{Q}\le\mathrm{R}=\widetilde\Theta(n^{2/3})$.
Ambainis' exact-quantum function total \(\Theta(2.1213^d)\) The bounded-error complexity is $\Theta((3/\sqrt2)^d) = \Theta(n^{0.6845\ldots})$: the lower bound is Ambainis' adversary argument and the matching upper bound follows from the optimality of the negative-weight adversary bound. Note this is above $\deg$, so the degree lower bound on $\mathrm{Q}$ is not tight here. Ambainis13
FORRELATION partial \(1\) Prepare uniform superposition, query $x$, Hadamard, query $y$, Hadamard, measure. AaronsonAmbainis18
k-FORRELATION partial \(\lceil k/2\rceil\) AaronsonAmbainis18
Simon's problem partial \(\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
Deutsch-Jozsa partial \(1\) $\mathrm{Q} \le \mathrm{Q}_E = 1$, and one query is needed.
Bernstein-Vazirani partial \(1\) $\mathrm{Q} \le \mathrm{Q}_E = 1$.
Unique search partial \(\Theta(\sqrt n)\) Grover, and the $\Omega(\sqrt n)$ hybrid-argument lower bound already applies under the unique-marked promise. Grover96 BBBV97
Two-or-none search partial \(\Theta(\sqrt n)\) Upper: amplitude amplification with a known count of $2$ marked items, $O(\sqrt{n/2})$ queries. Lower: the adversary bound below. Grover96 Ambainis02
Marked bit partial \(\Theta(\sqrt n)\) putative Upper: search the $2n$ encoding bits for a $1$ with the unknown-number-of-solutions version of Grover [BBHT98]; there are $m \ge 1$ of them, it finds one in $O(\sqrt{2n/m}) = O(\sqrt n)$ queries, and which bit it finds is the answer -- a $y$-bit means $1$, a $z$-bit means $0$. Lower: $\mathrm{Q} \ge \widetilde{\deg}/2 = \Omega(\sqrt n)$. Grover96 BBHT98
Dense marked bit partial \(\Theta(1)\) At most $\mathrm{R} = \Theta(1)$, and at least $1$.
Unstructured search (relation) relation \(\Theta(\sqrt n)\) Grover96 BBBV97
FIND-1 under a density promise relation \(\Theta(1)\) A dense search problem: one uniform sample already works, so quantum has nothing to speed up. $\mathrm{Q} \le \mathrm{R} = O(1)$.
Approximate Hamming weight relation \(\Theta(1)\) At most $\mathrm{R}$, and at least a constant.
Correlated-string search relation \(O(\sqrt n)\) At most $\mathrm{R}$. No better quantum algorithm is recorded here, and no lower bound beyond $\Omega(1)$.
SearchCNF relation \(\Theta(1)\) At most $\mathrm{R} = \Theta(1)$; at least one query.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) Amplitude estimation of $|x|/n$ to additive $\delta$; the matching lower bound is the usual approximate-counting bound of [NayakWu99]. So the promise buys a quadratic quantum speed-up over $\mathrm{R}$, the same one as for approximate counting. NayakWu99
Gap-Majority at constant gap partial \(\Theta(1)\) Amplitude estimation to additive $\delta$; at constant $\delta$, $O(1)$ queries. NayakWu99
Parity-labelled FIND-1 partial \(\Theta(1)\) $\mathrm{Q} \le \mathrm{R} = O(1)$, and at least one query.
Approximate index partial \(O(\sqrt{k\log k})\) At most $\mathrm{R}$. Nothing better is known and nothing better is needed: the point of the family is the $\mathrm{R}$-vs-$\mathrm{noisyR}$ gap, and quantum plays no role in it.
Collision problem partial \(\Theta(n^{1/3})\) Upper: the birthday-paradox-plus-Grover algorithm of [BHT98]. Lower: the polynomial method [AaronsonShi04], originally for range $\Omega(n^2)$; [Kutin05] removed the range restriction (their proof needed range $\ge 3n/2$) and simplified the argument, and [Ambainis05smallrange] handles small ranges too. BHT98 AaronsonShi04 Kutin05
Element distinctness total \(\Theta(n^{2/3})\) Upper: the quantum walk of [Ambainis07]. Lower: the polynomial method [AaronsonShi04], which needs alphabet size $\Omega(n^2)$; [Ambainis05smallrange] gets $\Omega(n^{2/3})$ down to alphabet size $n$. The $\varepsilon$-dependence is $\Theta(n^{2/3}\log^{1/3}(1/\varepsilon))$ [SherstovThaler23]. Ambainis07 AaronsonShi04 Ambainis05smallrange
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) Theorem 1, via Theorem 8: the tripartite shift problem already needs $\Omega(n^{1/3})$ quantum queries whenever $q \ge 4n^3$, for every choice of right-hand sides. No matching upper bound is claimed; the construction is closely related to an earlier problem of Belovs and Rosmanis, whose lower bound it strengthens. AmbainisBelovs23
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) Theorem 39: at $t = \log^5 n$, any quantum algorithm making $o(\sqrt n \log^4 n)$ queries succeeds with probability only $2^{-\Omega(\log^4 n)}$ against the uniform distribution. The core is the $\Omega(t\sqrt n/\log\log n)$ direct-sum bound for $t$ copies of $\mathrm{AndOr}_n$ at exponentially small success, and a union bound over the $2^{2\log^3 n\log\log(n/2)}$ shifts. BenDavidKundu24search
Yamakawa-Zhandry problem relation \(\mathrm{poly}(n)\) YamakawaZhandry22
Surjectivity total \(\tilde\Theta(n)\) Lower: [BeameMachmouchi12, Cor. 3] gives $\Omega(n/\log n)$ -- their Cor. 2 shows $\Omega(N)$ element queries for $\mathrm{ONTO}$ with $[2N-2]\to[N]$, and the binary encoding costs the log. Upper: $n$, trivially. A clean $\Omega(n)$ is widely attributed to [Sherstov18asymmetry], but that paper states it only as a confidence in Remark 3.4 ("we are confident that ... one can eliminate the logarithmic factors"), not as a theorem, and about some $\mathrm{AC}^0$ function rather than $\mathrm{SURJ}$ in the binary encoding; hence the tilde. BeameMachmouchi12
$k$-distinctness total \(\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
Triangle finding total \(\Omega(m),\ O(m^{5/4})\)· Open. Best upper bound $O(m^{5/4})$ with no log factors [CLM20], after $\tilde O(m^{5/4})$ by combinatorial arguments [LeGall14, Thm. 1.1]. The ladder: $O(m^{3/2})$ by Grover, $\tilde O(m^{13/10})$ [MSS07, Thm. 4], $O(m^{35/27})$ [Belovs12span, Thm. 8], $O(m^{9/7})$ [LMS13, Thm. 7], also $\tilde O(m^{9/7})$ by nested quantum walks [JKM13]. The only lower bound is the trivial $\Omega(m)$ from a Grover search embedded in one bipartite block [CGP26, Lem. 3.3(3)]. Still open as of August 2026. CLM20 LeGall14 LMS13 Belovs12span MSS07
Recursive Fourier sampling partial \(\Theta(2^\ell) \text{ for } g = g_{\mathrm{mod}3}\) [Aaronson03rfs, Thm. 5]: $\mathrm{Q}(\mathrm{RFS}^g_\ell) = \Omega\big((1-\mu(g))^{-\ell/2}\big)$, where $\mu(g)$ is the nonparity coefficient of Def. 2. Prop. 6 gives $\mu(g_{\mathrm{mod}3}) = 3/4 - O(1/n)$, hence $\Omega(2^\ell)$, matching the algorithm. Thm. 7: $\mu(g) < 0.146$ forces $g$ to be a parity, so any legal $g$ gives $\Omega(2^{0.113\ell})$. This was the first lower bound to need the adversary method rather than the polynomial method. Aaronson03rfs
Welded trees relation \(\Theta(n)\)· putative Upper: [JefferyZur25, §5], a multidimensional (electric-network) quantum walk, $O(n)$ queries and $O(n^2)$ time; [Belovs24welded] reproves it in a page. The 2003 continuous-time walk is not an $O(n)$-query algorithm: simulating $e^{-iHt}$ for $t = O(n^4)$ costs $O(t^2)$ queries, so [CCDFGS03] as stated is $O(n^{8.5})$ queries, brought to $O(n^{2.5}\log^2 n)$ by [AtiaChakraborty21]. Lower, $\Omega(n)$: nobody states this as a theorem, but it is the light-cone argument -- names are random $2n$-bit strings in a space of size $2^{2n}$, so with probability $1 - 2^{-\Omega(n)}$ an algorithm never guesses a name it has not been handed, and after $t$ queries everything it has seen lies within distance $t$ of the ENTRANCE, which is $2n+2$ away from the EXIT; BBBV makes the hybrid argument quantum. [Belovs24welded] calls the linear upper bound optimal, which presupposes it. The $\Theta$ is therefore only as good as that folklore argument, hence the medium confidence. JefferyZur25 Belovs24welded
Local search on the hypercube relation \(\Theta(2^{n/3}n^{1/6})\) Upper: Aaronson's generic $O(N^{1/3}\Delta^{1/6})$. Lower: [Zhang09localsearch, Thm. 2], after [Aaronson06, Thm. 15] ($\Omega(2^{n/4}/n)$ by the relational adversary) and an unpublished $\Omega(2^{n/3}/n^{O(1)})$ of Ambainis. Zhang09localsearch Aaronson06
Local search on the grid relation \(\Theta(k^{d/3})\ (d \ge 6)\) [Zhang09localsearch, Thm. 3], matching Aaronson's $O(N^{1/3}\Delta^{1/6}) = O(k^{d/3})$. Below $d = 6$ the picture degrades one dimension at a time: $\tilde\Theta(k^{5/3})$ at $d = 5$, from $\Omega((k^5/\log k)^{1/3})$ [Zhang09localsearch, Thm. 3]; a genuine polynomial gap $\Omega(k^{6/5})$ to $O(k^{4/3})$ at $d = 4$, the one cell of the table still open; $\tilde\Theta(k)$ at $d = 3$, from $\Omega(k^{1-\delta})$ [SunYao09] against $O(k)$; and $\tilde\Theta(\sqrt k)$ at $d = 2$, from $\Omega(k^{1/2-\delta})$ [SunYao09] against $O(\sqrt k\log\log k)$ [Verhoeven06] via graph genus (also $O(\sqrt k(\log\log k)^{1.5})$ [Zhang09localsearch, Thm. 5]). Zhang09localsearch Aaronson06 SunYao09 Verhoeven06
Fourier fishing relation \(1\) [AaronsonChen17, Lem. 6.3]: Hadamard, query, Hadamard, measure. It solves Fourier sampling exactly and fishing with probability $\ge 0.801 - 1/n$ on the promise. AaronsonChen17 AaronsonAmbainis18
Ordered search partial \(\Theta(\log n)\) The constant is open. Lower: $\tfrac1\pi(\ln n - 1) \approx 0.2206\log_2 n$ [HNS02], by a weighted all-pairs inner-product argument. Upper: $5\log_{7265} n \approx 0.390\log_2 n$ [CCKS25]. The ladder of lower bounds: $\Omega(\sqrt{\log n}/\log\log n)$ [BuhrmandeWolf99ordered], $\log_2 n/(2\log\log n)$ [FGGS98limit], $\tfrac1{12}\log_2 n$ [Ambainis99ordered], then HNS. HNS02 CCKS25
Tseitin search on an expander relation \(O(\sqrt n)\) Grover over the $\Theta(n)$ vertices, each tested for violation with $d = O(1)$ queries. So the quadratic speedup that \(\mathrm{Search}(\varphi)\) does not need and \(\mathrm{WT}_n\) far exceeds is exactly what Tseitin gets. No matching $\Omega(\sqrt n)$ is recorded: $\mathrm{cbs}$ is a randomized lower bound with no known quantum analogue, and the natural relational adversary is weak here because two inputs with different violated vertices differ only along a path, which in an expander has length $O(\log n)$.
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{Q} \ge \widetilde{\deg}/2 \ge \mathrm{sdeg}/2 \ge n/4$ and $\mathrm{Q} \le \mathrm{D} = n$.
Minsky-Papert one-in-a-box total \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) Robust quantum search on the two levels; matches $\widetilde{\deg}/2$. HoyerMoscadeWolf03
Sink of a tournament total \(\Omega(\sqrt m),\ O(m)\) Open, and the same gap as $\widetilde{\deg}$. Lower: $\mathrm{Q} \ge \widetilde{\deg}/2 = \Omega(\sqrt{\mathrm{bs}}) = \Omega(\sqrt m) = \Omega(N^{1/4})$. Upper: $\mathrm{Q} \le \mathrm{D} = O(m)$, and the obvious quantum algorithm does no better -- amplitude amplification over the $m$ candidate sinks, each checked by a Grover search for an out-edge, costs $O(\sqrt m \cdot \sqrt m) = O(m)$, exactly what candidate elimination already gives classically. The at-most-one-sink promise is what blocks the usual $\mathrm{OR}\circ\mathrm{AND}$ adversary bound of $\Omega(m)$, so neither end is known to be tight.
Scorpion graphs total \(O(m)\) From $\mathrm{Q} \le \mathrm{D}$. No better bound is recorded, and no better one is obviously available: this is not a search problem.
Graph connectivity total \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) [DHHM06]: Grover-search the neighbourhoods in a BFS, $O(m^{3/2})$ queries; and $\Omega(m^{3/2})$ by the quantum adversary. Strong connectivity of a digraph, minimum spanning tree and single-source shortest paths in the adjacency-matrix model are all $\Theta(m^{3/2})$ too. DHHM06
Ben-David–Kothari championship function total \(\tilde O(\sqrt n)\) Lemma 5; the final verification costs O(√n log² n), with polylogs also in the sink-finding subroutine. BenDavidKothari26
Ambainis–Iraids–Kokainis certificate cheat sheet total \(O(\sqrt n\log^3 n)\) Theorem 2.1. AIK26
AND of complemented EXACT-ONE functions total \(\Theta(m)\) Lemma 55 gives O(m). At the all-zero input, all m² single-bit flips reject, so bs=m² and Q=Ω(√bs). KLLPV26
OpenAI’s nearly quartic randomized–quantum family total \(\widetilde O(\sqrt m)\) For each fixed k, Q≤C_k sqrt(m)(log m)^{b_k}. Constants and the log exponent may depend on k. OpenAI26QuarticRQ