Zero-error quantum certification complexity
Zero-error quantum cost of the certification task; equivalent to its exact quantum cost.
Definition
$\mathrm{Q}_0^{\mathrm{cert}}(f)=\max_{z\in D}\mathrm{Q}_0(f_z^{\mathrm{cert}})$, with the known-input promise defined in Operational certification complexity. The algorithm never answers incorrectly and may report ignorance with probability at most $1/2$.
Basic facts
- $\mathrm{Q}_{0}^{\mathrm{cert}}\le\mathrm{Q}_0$ and $\mathrm{Q}_{0}^{\mathrm{cert}}=\Theta(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}})$ [KLLPV26, Theorem 5].
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\). “\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) in terms of it” is the pair with \(\mathrm{Q}_{0}^{\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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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)\) | Theorem 5 and QEcert=Θ(n). KLLPV26 |
| AND of complemented EXACT-ONE functions total | \(\Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) | Theorem 5 and the QEcert bounds. KLLPV26 |