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

Quantum certificate complexity

Quantum analogue of certificate complexity; the square root of RC.

Definition

$\mathrm{QC}_x(f)$ is the minimum number of quantum queries needed to verify that the input is $x$ "as far as $f$ is concerned"; $\mathrm{QC}(f)=\max_x \mathrm{QC}_x(f)$.

Basic facts

  • $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)}) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08].
  • $\mathrm{QC}(f) \le \mathrm{Q}(f)$.
  • Operational certification for $\mathrm{Q}$, quantum distinguishing complexity, the quantum adversary bound, all four quantum sabotage variants, bounded approximate degree and block-multilinear bounded approximate degree equals $\Theta(\mathrm{QC})$ [KLLPV26, Theorems 4 and 6].
  • For every quantum sabotage variant, $\mathrm{QC}=O(\mathrm{QS})$ even on partial functions; Index shows the inequality need not be tight [CMP24, KLLPV26].

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{QC}(f)\). “\(\mathrm{QC}(f)\) in terms of it” is the pair with \(\mathrm{QC}(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{QC}(f)\) in terms of it It in terms of \(\mathrm{QC}(f)\)
\(\mathrm{RC}(f)\) Randomized certificate complexity total0.5,0.5 partial0.5,0.5 open pair → total2,2 partial2,2 derived open pair →
\(\mathrm{fbs}(f)\) Fractional block sensitivity total0.5,0.5 partial0.5,0.5 open pair → total2,2 partial2,2 derived open pair →
\(\mathrm{C}(f)\) Certificate complexity total0.5,0.5 partial0.5,0.5 derived open pair → total4,4 partial∞ derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1 partial1,1 derived open pair → total4,6 partial∞ derived open pair →
\(\mathrm{QS}_{\mathrm{str}}(f)\) Strong quantum sabotage complexity total1,1 partial1,1 open pair → total2,6 partial2,? derived open pair →
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) Exact quantum certification complexity total0.6667,1 partial0.6667,1 derived open pair → total2,4 partial∞ 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)\) Quantum certificate complexity is $\Theta(\sqrt{\mathrm{RC}})$; for OR this is the Grover-verification bound. Aaronson08
AND total \(\Theta(\sqrt n)\) Aaronson08
PARITY total \(\Theta(\sqrt n)\) $\mathrm{QC}=\Theta(\sqrt{\mathrm{RC}})$ and $\mathrm{RC}=\lceil n/2\rceil$. Verification is quadratically cheaper than computation even here. Aaronson08
MAJORITY total \(\Theta(\sqrt n)\) $\mathrm{QC}=\Theta(\sqrt{\mathrm{RC}})$. Verifying a majority is quadratically cheaper than computing it. Aaronson08
Threshold total \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(\max\{k,\,n-k+1\}) = \Theta(n)$ here. Verifying a threshold is quadratically cheaper than computing it, uniformly in $k$. Aaronson08
Symmetric functions (general) total \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n)$ here. Aaronson08
EXACT-HALF total \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n)$ here. So verifying is quadratically cheaper even though computing costs the full $\Theta(n)$ quantumly. Aaronson08
ODD-MAX-BIT total \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n)$ here. Aaronson08
ADDRESS / multiplexer total \(\Theta(\sqrt k)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(k)$ here. Aaronson08
Binary tree navigation total \(\Theta(\sqrt k)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(k)$ here. Verifying a claimed walk is quadratically cheaper than following it. Aaronson08
TRIBES total \(\Theta(\sqrt{n/\log n})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n/\log n)$ here. Strictly below $\mathrm{Q} = \Theta(\sqrt n)$ by a $\sqrt{\log n}$ factor. Aaronson08
AND-OR tree (depth 2) total \(\Theta(\sqrt n) = \Theta(N^{1/4})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = n$ here.
NAND tree (balanced AND-OR formula) total \(\Theta(N^{1/4})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(\sqrt N)$ here.
Recursive MAJORITY-of-3 total \(\Theta(2^{d/2}) = \Theta(N^{0.3155})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = 2^d$ here.
Kushilevitz's function (iterated) total \(\Theta(\sqrt N)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = N$ here.
Rubinstein's function total \(\Theta(\sqrt N)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(N)$ here.
Ambainis-Sun function total \(\Theta(\sqrt N)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(N)$ here.
AND composed with NOT-EXACT-HALF total \(\Theta(n) = \Theta(\sqrt N)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\Omega(118.3^{\,d})\) putative $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} \ge \mathrm{bs} \ge 14011^{\,d}$.
Pointer functions total \(\widetilde\Theta(n^{1/4})\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$.
Cheat-sheet functions total \(\widetilde\Theta(n^{1/4})\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. Quantum certificate complexity is a fourth power below $\mathrm{Q}$ here.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$ with $\mathrm{fbs}=\widetilde\Omega(n)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$.
Gilmer-Saks-Srinivasan functions total \(\Theta(\sqrt n)\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6})\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$.
Ambainis' exact-quantum function total \(\Theta(3^{d/2})\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. This is $\Theta(n^{1/2})$, well below $\mathrm{Q}=\Theta(n^{0.6845})$.
FORRELATION partial \(\Theta(1)\) An algorithm computing $f$ also verifies it, so $\mathrm{QC} \le \mathrm{Q} = 1$; and $\mathrm{QC} \ge 1$ for a non-constant $f$. This is what forces $\mathrm{fbs} = O(1)$ above, via $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$.
k-FORRELATION partial \(O(k)\) An algorithm computing $f$ also verifies its input, so $\mathrm{QC} \le \mathrm{Q} = \lceil k/2\rceil$; and $\mathrm{QC} \ge 1$. Independent of $n$.
Simon's problem partial \(\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.
Deutsch-Jozsa partial \(\Theta(1)\) An algorithm computing $f$ also verifies it, so $\mathrm{QC} \le \mathrm{Q} = 1$. Compare $\mathrm{C} = N/2+1$: this is the extreme case of quantum certificates beating classical ones.
Bernstein-Vazirani partial \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$, and independently $\mathrm{QC} \le \mathrm{Q} = 1$. Against $\mathrm{C} = \mathrm{C}_{\min} = n$: a constant-size quantum certificate replaces a whole basis of $\mathbb{F}_2^n$.
Marked bit partial \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{FC}}) = \Theta(1)$ [Aaronson08]. Constant quantum certificate complexity against $\mathrm{Q} = \Theta(\sqrt n)$ -- the same phenomenon Aaronson exhibits on \(\mathrm{COL}_n\), here at quadratic strength and with a two-line proof. Aaronson08
Dense marked bit partial \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{FC}}) = \Theta(1)$ [Aaronson08]; also $\mathrm{QC} \le \mathrm{Q} = \Theta(1)$. Aaronson08
Gap-Majority partial \(\Theta(\sqrt{\min(n, 1/\delta)})\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$, with $\mathrm{fbs} = \Theta(\min(n,1/\delta))$; and independently $\mathrm{QC} \le \mathrm{Q}$. Aaronson08
Gap-Majority at constant gap partial \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$. Aaronson08
Parity-labelled FIND-1 partial \(\Theta(1)\) At most $\mathrm{Q} = \Theta(1)$, and at least $1$.
Approximate index partial \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$: a constant-size quantum certificate, matching the constant-size classical one. Aaronson08
Collision problem partial \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$; a colliding pair is a two-query certificate and the promise makes it checkable. Aaronson08
Element distinctness total \(\Theta(\sqrt n)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{RC}})$ and $\mathrm{RC} = \Theta(n)$. Directly: at an all-distinct $x$ every adversary $y$ with $\mathrm{ED}(y) = 0$ differs from $x$ in one symbol, so distinguishing $x$ from all of them is unstructured search, $\mathrm{RC}_x = \Theta(n)$ and $\mathrm{QC}_x = \Theta(\sqrt n)$. Note $\mathrm{QC} = \Theta(\sqrt n)$ sits below $\mathrm{Q} = \Theta(n^{2/3})$: verifying is easier than deciding. Aaronson08
Ambainis-Belovs function partial \(O(\sqrt n)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = O(\sqrt n)$. The other ceiling, $\mathrm{QC} \le \mathrm{Q}$, is useless here because only a lower bound on $\mathrm{Q}$ is known. Aaronson06
Surjectivity total \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$ (\(\mathrm{QC}(f)\) vs \(\mathrm{FC}(f)\)), and $\mathrm{FC} = \Theta(n)$ here.
$k$-distinctness total \(\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.
Triangle finding total \(\Theta(m)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$, and $\mathrm{FC} = \Theta(m^2)$ here.
Ordered search partial \(\Theta(1)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$, and $\mathrm{FC} = 2$.
Inner product mod 2 total \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)}) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ [Aaronson08], and $\mathrm{fbs} = n$ here. So quantum certificate complexity is a full square root below $\mathrm{Q} = \Theta(n)$: verification is cheap even though computation is not. Aaronson08
Minsky-Papert one-in-a-box total \(\Theta(m) = \Theta(N^{1/3})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m^2)$ here. Curiously this coincides with $\mathrm{sdeg}$ and with $\mathrm{C}_{\min}$, all three at $N^{1/3}$. Aaronson08
Sink of a tournament total \(\Theta(\sqrt m) = \Theta(N^{1/4})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m)$ here. It coincides with $\lambda$ and with the lower end of the $\mathrm{Q}$ range. Aaronson08
Scorpion graphs total \(\Theta(\sqrt m) = \Theta(N^{1/4})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m)$ here. So a quantum verifier checks the scorpion property with a quadratically shorter certificate than the classical $\mathrm{C} = \Theta(m)$. Aaronson08
Graph connectivity total \(\Theta(m) = \Theta(\sqrt N)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m^2)$ here. The $1$-side already has a classical certificate of size $m-1$ (a spanning tree); what the quantum verifier compresses is the $\Theta(m^2)$-edge cut on the $0$-side. Aaronson08
AND of complemented EXACT-ONE functions total \(\Theta(m)\) QC=Θ(√fbs). Aaronson08 KLLPV26