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.
The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |