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

Exact quantum certification complexity

Worst-case exact quantum query cost of recognizing a known input against all opposite-output inputs.

Definition

For each publicly known $z\in D$, let $f_z^{\mathrm{cert}}$ have domain $\{z\}\cup f^{-1}(1-f(z))$, accepting $z$ and rejecting the other inputs. Then $\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)= \max_z\mathrm{Q}_{\mathrm{E}}(f_z^{\mathrm{cert}})$. It uses the Operational certification complexity transform, rather than the computation of $f$ itself.

Basic facts

  • $\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}=O(\mathrm{Q}_0)$ [KLLPV26, Theorem 5].
  • $\mathrm{degcert}\le 2\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}$ [KLLPV26, Section 6.1].
  • On AND of complemented EXACT-ONE functions, this gives a lower bound of $\widetilde\Omega(m^{3/2})$ on $\mathrm{Q}_0$, while $\mathrm{Q}=O(m)$ and $\mathrm{rdeg}=m$.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\). “\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) in terms of it” is the pair with \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(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}}^{\mathrm{cert}}(f)\) in terms of it It in terms of \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\)
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) Zero-error quantum certification complexity total1,1 partial1,1 derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity total1,1 partial1,1 derived open pair → total2,4 partial2,? derived open pair →
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity total1,1 partial1,1 open pair → total2,4 partial2,? derived open pair →
\(\mathrm{QC}(f)\) Quantum certificate complexity total2,4 partial∞ open pair → total0.6667,1 partial0.6667,1 derived open pair →
\(\overline{\deg}^{\mathrm{cert}}(f)\) Bounded degree certification complexity total1,3 partial1,? derived open pair → total1,1 partial1,1 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 \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
AND total \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
PARITY total \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
MAJORITY total \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
AND-OR tree (depth 2) total \(\Theta(n)\) Certification costs at most its n-bit classical certificate; bounded degree certification n gives the quantum lower bound. KLLPV26
AND of complemented EXACT-ONE functions total \(\Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) 2QEcert≥degcert and QEcert=O(Q₀). KLLPV26