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

Exact quantum query complexity

Number of queries of a quantum algorithm that outputs f(x) with probability 1.

also written: Q_0 in some papers (careful!), zero-error-with-certainty quantum complexity

Definition

$\mathrm{Q}_{\mathrm{E}}(f) = \mathrm{Q}_0(f)$ in the "always right" sense: the algorithm must output the correct answer with certainty. Note the notational hazard: some authors use $\mathrm{Q}_0$ for the Las Vegas (zero-error-but-may-abort) version, which is \(\mathrm{Q}_{0}(f)\) here.

Basic facts

  • $\deg(f) \le 2\,\mathrm{Q}_{\mathrm{E}}(f)$ [BBCMdW01].
  • $\mathrm{Q}_{\mathrm{E}}(\mathrm{PARITY}_n) = \lceil n/2\rceil$: the only known factor-2 speedup style behaviour for total functions.
  • First superlinear-advantage total function: $\mathrm{Q}_{\mathrm{E}}(f) = O(\mathrm{D}(f)^{0.8675\ldots})$ [Ambainis13], giving the $1.15$ exponents in the $\mathrm{Q}_{\mathrm{E}}$ column.
  • It is open whether $\mathrm{Q}_{\mathrm{E}}(f) = O(\deg(f))$ for total $f$ [BdW02, Open problem 4].
  • Exact quantum query complexity does not compose within constant factors on total functions: $\mathrm{Q}_{\mathrm{E}}(f_k\circ\mathrm{OR}_{m_k})=o(\mathrm{Q}_{\mathrm{E}}(f_k)\mathrm{Q}_{\mathrm{E}}(\mathrm{OR}_{m_k}))$ [PednekarPodder26composition, PednekarPodder26STOC]. See comp-QE.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Q}_{\mathrm{E}}(f)\). “\(\mathrm{Q}_{\mathrm{E}}(f)\) in terms of it” is the pair with \(\mathrm{Q}_{\mathrm{E}}(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}_{\mathrm{E}}(f)\) in terms of it It in terms of \(\mathrm{Q}_{\mathrm{E}}(f)\)
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total2,4 partial∞ relation∞ open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity total1.32,4 partial∞ relation∞ derived open pair → total1,1 partial1,1 relation1,1 open pair →
\(\deg(f)\) Exact degree total2,3 partial∞ open pair → total1,1 partial1,1 open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 relation1,1 open pair → total2,3 partial∞ relation∞ open pair →
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity total1.33,2 partial∞ relation∞ open pair → total2,3 partial∞ relation∞ open pair →

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

Known values

FunctionValueNotes
OR total \(n\) BBCMdW01
AND total \(n\) Exact quantum computation gives no speedup, as for OR. BBCMdW01
PARITY total \(\lceil n/2 \rceil\) BBCMdW01
MAJORITY total \(\Theta(n)\) At least $\deg/2 = n/2$ and at most $n$; [AmbainisGruslysEtAl16] pin down the exact quantum complexity of threshold functions. BBCMdW01 AmbainisGruslysEtAl16
Threshold total \(\Theta(n)\) Between $\deg(f)/2 = n/2$ and the trivial $n$.
Symmetric functions (general) total \(\Theta(n)\) Sandwiched: $\deg(f)/2 \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, and von zur Gathen-Roche makes $\deg(f) = n - O(n^{0.548})$, so both ends are $\Theta(n)$.
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
ODD-MAX-BIT total \(\Theta(n)\) Squeezed between $\deg/2 = n/2$ and $\mathrm{D} = n$. So $\mathrm{OMB}$ has a full quadratic exact-vs-bounded-error quantum gap.
ADDRESS / multiplexer total \(\Theta(k+1)\) Sandwiched: $\deg(f)/2 \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$ -- the same halving as on \(\mathrm{Tribes}_{w,s}\) -- with $\deg(f) = k+1$ and $\mathrm{D}(f) = k+1$ here, so both ends are $\Theta(k)$.
Binary tree navigation total \(\Theta(k)\) Squeezed between $\deg/2$ and $\mathrm{D}$, both $\Theta(k)$.
TRIBES total \(\Theta(n)\) Sandwiched: $\deg(f)/2 \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$ -- a $t$-query exact algorithm gives an exact polynomial of degree at most $2t$, so the degree bound is halved -- with $\deg(f) = n$ and $\mathrm{D}(f) = n$ here, hence $n/2 \le \mathrm{Q}_{\mathrm{E}} \le n$.
AND-OR tree (depth 2) total \(\Theta(n^2)\) $\mathrm{Q}_E \ge \deg/2 = n^2/2$.
NAND tree (balanced AND-OR formula) total \(\Theta(N)\) $\ge \deg/2$.
Recursive MAJORITY-of-3 total \(\Theta(N)\) Between $\deg/2 = N/2$ and $\mathrm{D} = N$. Exactness costs the full $N$ against $\mathrm{Q} = \Theta(N^{0.63})$.
Kushilevitz's function (iterated) total \(\Omega(N^{0.6131}),\ O(N)\) Between $\deg/2 = 3^k/2$ and $\mathrm{D} = N$. Unlike \(\mathrm{AND}_n \circ \mathrm{OR}_n\) and \(\bar{\wedge}\text{-tree}\), where $\deg = \mathrm{D}$ forces $\mathrm{Q}_E = \Theta(\mathrm{D})$, here the degree bound leaves a genuine $N^{0.39}$ window.
Rubinstein's function total \(\Theta(N)\) Between $\deg/2 = N/2$ and $\mathrm{D} = N$. Exact quantum query complexity is thus quadratically above $\mathrm{Q} = \Theta(\sqrt N)$.
Ambainis-Sun function total \(\Theta(N)\) Between $\deg/2 = \Theta(N)$ and $\mathrm{D} = \Theta(N)$.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Sandwiched: $\deg(f) \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\ge 118.3^{\,d}\) putative $\mathrm{Q}_E \ge \mathrm{Q} \ge 118.3^{\,d}$; the degree route $\mathrm{Q}_E \ge \deg/2$ gives only $59.2^{\,d}$ and is weaker.
Pointer functions total \(\widetilde O(\sqrt n)\) Same variant $g_{m,m}$ [ABBLSS17, Thm 12, Cor. 14]: the exact quantum algorithm costs $\widetilde O(m)$ on $m^2$ cells. Since that variant has $\mathrm{R}_0=\widetilde\Omega(n)$ this is a quadratic $\mathrm{R}_0$-vs-$\mathrm{Q}_E$ gap, and against $\mathrm{D}=\widetilde\Omega(n)$ it gives $\mathrm{D}=\widetilde\Omega(\mathrm{Q}_E^2)$. ABBLSS17
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze between $\mathrm{Q}=\widetilde\Omega(n)$ and $\mathrm{D}=\widetilde O(n)$.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{Q}_E\ge\mathrm{Q}$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{Q}_E\ge\mathrm{Q}=\widetilde\Omega(n^{2/3})$; the ceiling is $\mathrm{Q}_E\le\mathrm{D}=\widetilde\Theta(n^2)$.
Gilmer-Saks-Srinivasan functions total \(\Omega(n^{2/3})\) Squeeze: $\mathrm{Q}_E\ge\deg/2=\Omega(n^{2/3})$, which beats the route through $\mathrm{Q}$; the ceiling is $\mathrm{Q}_E\le\mathrm{D}=\Theta(n^2)$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{Q}_E\ge\mathrm{Q}=\widetilde\Omega(n^{1/4})$; the ceiling is $\mathrm{Q}_E\le\mathrm{D}=\widetilde\Theta(n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6})\) Squeeze: $\mathrm{Q}_E\ge\mathrm{Q}=\widetilde\Omega(n^{1/6})$; the ceiling is $\mathrm{Q}_E\le\mathrm{D}=\widetilde\Theta(n^{2/3})$.
Ambainis' exact-quantum function total \(O(2.593^d)\) The main theorem: $\mathrm{Q}_E(\mathrm{NE}^d) = O(2.593\ldots^d) = O(\mathrm{D}^{0.8675\ldots})$. The best known lower bound is only $\mathrm{Q}_E\ge\mathrm{Q}=\Omega(2.1213^d)$, so the exponent is not pinned; the value is recorded as $O(\cdot)$ for that reason. Ambainis13
FORRELATION partial \(O(n)\) At most $\mathrm{D} = \Theta(n)$, at least $\mathrm{Q} = 1$. The $\mathrm{Q}_E \ge \deg/2$ bound gives nothing, since $\deg$ itself is only known to be $O(n)$.
k-FORRELATION partial \(O(kn)\) At most $\mathrm{D} = O(kn)$, at least $\mathrm{Q} = \lceil k/2\rceil$.
Simon's problem partial \(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.
Deutsch-Jozsa partial \(1\) DeutschJozsa92
Bernstein-Vazirani partial \(1\) BernsteinVazirani97
Marked bit partial \(\Omega(\sqrt n),\ O(n)\) Between $\mathrm{Q}_0$ and $\mathrm{D}$.
Dense marked bit partial \(\Theta(n)\) Squeezed by the two entries above: $\mathrm{Q}_E \ge \deg/2 = \Omega(n)$ [BBCMdW01], and $\mathrm{Q}_E \le \mathrm{D} = n/2+1$. Against $\mathrm{Q}_0 = \Theta(1)$: demanding certainty costs a factor of $n$ here, even though aborting sometimes is free.
Unstructured search (relation) relation \(n\) putative An exact algorithm for $\mathrm{SEARCH}$ decides $\mathrm{OR}$ exactly at no extra cost -- output $[\,i \ne \bot\,]$ -- so $\mathrm{Q}_E(\mathrm{SEARCH}) \ge \mathrm{Q}_E(\mathrm{OR}_n) = n$, and $\mathrm{Q}_E \le \mathrm{D} = n$. So the quadratic Grover speedup is entirely a bounded-error effect, even though a search algorithm can always verify its own output: verification makes the error one-sided, not zero.
FIND-1 under a density promise relation \(n/2+1\)· putative Exactness is as expensive as determinism. A quantum algorithm that must output a valid index with certainty after $q$ queries still has to have queried a $1$ in every branch of its computation, and the adversary that answers $0$ to the first $n/2$ distinct positions keeps a promise-consistent input alive; and $\mathrm{Q}_E \le \mathrm{D} = n/2+1$. So the whole $\Theta(n)$-to-$O(1)$ collapse here is a bounded-error effect.
Approximate Hamming weight relation \(\Theta(n)\) Squeezed between $\mathrm{Q}_0 = \Theta(n)$ and $\mathrm{D} = \Theta(n)$.
SearchCNF relation \(O(n)\) Only $\mathrm{Q}_E \le \mathrm{D} = O(n)$ is available. The Las Vegas value $\mathrm{Q}_0 = \Theta(1)$ does not bound it: certainty on every branch is what \(\mathrm{SEARCH}_n\) shows can cost the full $n$, and no lower bound better than $\Omega(1)$ is proved here.
Gap-Majority partial \(\Theta(n)\) putative Exactness is as expensive as determinism: $\mathrm{Q}_E \ge \deg/2 = \Omega(n)$ and $\mathrm{Q}_E \le \mathrm{D} = \Theta(n)$. At constant $\delta$ this is an unbounded $\mathrm{Q}_E$-vs-$\mathrm{Q}$ gap.
Gap-Majority at constant gap partial \(\Theta(n)\) putative Exactness costs as much as determinism: $\mathrm{Q}_E \ge \deg/2$ and $\mathrm{Q}_E \le \mathrm{D}$. Against $\mathrm{Q} = \Theta(1)$, unbounded.
Parity-labelled FIND-1 partial \(1\) putative One query, with certainty. Prepare $|\psi\rangle = (n/2)^{-1/2}\sum_{i \text{ odd}}|i\rangle$ and apply the phase oracle $|i\rangle \mapsto (-1)^{x_i}|i\rangle$. On a $0$-input every odd coordinate is $0$, so the state is unchanged; on a $1$-input exactly $n/4$ of the $n/2$ odd coordinates carry a $-1$, so the state is orthogonal to $|\psi\rangle$. The projective measurement $\{|\psi\rangle\langle\psi|,\, I - |\psi\rangle\langle\psi|\}$ then answers with probability $1$ either way. This is \(\mathrm{DJ}_n\) run on the odd half, and it is why the promise fixes $|x| = n/4$: half of the odd coordinates, so the $1$-case is exactly balanced. Contrast \(\mathrm{GapMaj}^{\delta}_{n}\) and \(\mathrm{Find1}_{\ge n/2}\), where exactness costs $\Theta(n)$.
Approximate index partial \(O(\sqrt{k\log k})\) At most $\mathrm{D}$. From below the polynomial method gives $\mathrm{Q}_E \ge \deg/2 = \Omega(1)$, i.e. nothing at all, since $\deg = \Theta(1)$ here.
Collision problem partial \(O(n)\) At most $\mathrm{D} = n/2+1$; at least $\mathrm{Q}_0 = \Omega(n^{1/3})$.
Element distinctness total \(\Theta(n)\) Squeezed between $\deg/2 = n/2$ and $\mathrm{D} = n$. Exact quantum query complexity gets no asymptotic speedup on element distinctness, while bounded error gets $n^{2/3}$ -- the whole advantage lives in the error. BBCMdW01
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} \le \mathrm{D}$, i.e. between $\Omega(n^{1/3})$ and $O(n)$. Note that $\deg \le 2\mathrm{Q}_{\mathrm{E}}$ is useless in this direction -- $\deg$ is $9$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{Q}$.
Surjectivity total \(\tilde\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon} = \tilde\Theta(n)$ and $\mathrm{D} = n$ here.
$k$-distinctness total \(\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.
Recursive Fourier sampling partial \(2^\ell\) One level costs two queries by the Bernstein-Vazirani kickback trick, and the recursion is exact: [Aaronson03rfs, Lem. 1] puts the language version in $\mathrm{EQP}^A$; [BernsteinVazirani97, Thm. 8.4.3] gives a polynomial-time quantum machine accepting with probability $1$, from the recursion $T(n) \le \mathrm{poly}(n) + 4T(n/2)$. Aaronson03rfs BernsteinVazirani97
Welded trees relation \(O(n^{1.5}\log n)\) [LiLiLuo24, §5, Alg. 2]: run the plain coined quantum walk for a classically precomputable number of steps, then exact amplitude amplification. Zero error -- one of very few exponential $\mathrm{Q}_E$-vs-$\mathrm{R}$ separations known. Their bounded-error Alg. 1 uses $O(n^2\log n)$ queries. LiLiLuo24
Local search on the hypercube relation \(\Omega(2^{n/3}n^{1/6}),\ O(2^n/\sqrt n)\) $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_{\mathrm{E}}\le\mathrm{D}$, with $\mathrm{Q}=\Theta(2^{n/3}n^{1/6})$ and $\mathrm{D}=\Theta(2^n/\sqrt n)$. Nothing is known about exact local search: even the classical deterministic upper bound is the only ceiling available.
Local search on the grid relation \(\Omega(k^{d/3}),\ O(k^{d-1})\ (d \ge 6)\) $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_{\mathrm{E}}\le\mathrm{D}$, with $\mathrm{Q}=\Theta(k^{d/3})$ and $\mathrm{D}=\Theta(k^{d-1})$.
Ordered search partial \(\Theta(\log n)\) Upper $0.390\log_2 n$: [CCKS25] show every bounded-error $k$-query algorithm can be made translation-invariant with no workspace, and an LP search then finds an exact $5$-query algorithm for lists of length $7265$. Earlier exact algorithms: $0.526\log_2 n$ ($3$ queries, $52$ items) [FGGS99invariant], $0.433\log_2 n$ ($4$ queries, $605$ items) [CLP07]. Lower: $\mathrm{Q}_E \ge \mathrm{Q} \ge \tfrac1\pi(\ln n - 1)$. CCKS25 HNS02
Tseitin search on an expander relation \(O(n)\) $\mathrm{Q}_{\mathrm{E}}\le\mathrm{D}=\Theta(n)$. Reading every edge determines the whole violation vector, and nothing better is known exactly: the Grover algorithm behind $\mathrm{Q}=O(\sqrt n)$ has one-sided error.
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{Q}_E \ge \deg/2 = n/2$ and $\mathrm{Q}_E \le \mathrm{D} = n$. (With a parity oracle the answer would be $m+1$ or so; see $\mathrm{D}^{\oplus}$ below.)
Minsky-Papert one-in-a-box total \(N = m^3\) Sandwiched exactly: $\deg(f) \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, and both ends are $N = m^3$ here. Exact quantum computation buys nothing on a read-once AND-OR formula, while bounded error buys the full quadratic $\Theta(\sqrt N)$.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\deg/2 = (m-1)/2 \le \mathrm{Q}_{\mathrm{E}} \le \mathrm{D} = O(m)$. Unlike the bounded-error $\mathrm{Q}$, which is open between $\Omega(\sqrt m)$ and $O(m)$, the exact value is pinned.
Scorpion graphs total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\deg/2 = (3m-6)/2 \le \mathrm{Q}_{\mathrm{E}} \le \mathrm{D} = O(m)$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Sandwiched between $\deg/2 = N/2$ and $\mathrm{D} = N$. Exact quantum computation buys at most a factor $2$ on connectivity, while bounded error buys the $\Theta(N^{3/4})$ of \(\mathrm{Q}_{\varepsilon}(f)\).
Ben-David–Kothari championship function total \(\Theta(n\log n)\) v3 concurrent-work discussion extends the championship algorithm to exact queries and gives a matching restriction. AIK26
Ambainis–Iraids–Kokainis certificate cheat sheet total \(\Theta(n\log^2 n)\) Theorem 2.3; exact amplification and the count-field restriction. AIK26