Ambainis–Iraids–Kokainis certificate cheat sheet
Quartic $\mathrm{C}/\mathrm{Q}$ and $\mathrm{R}_0/\mathrm{Q}$ separations, with quadratic $\mathrm{C}/\mathrm{Q}_{\mathrm{E}}$ and $\mathrm{C}/\mathrm{Q}_0$.
total arity: $\Theta(n^3\log^2 n)$ bits
Description
Use \(\mathrm{AIKuD}\) to specify a partial function $H(x,y)$: if its unique satisfied term is $T_{i,S}$, return $\bigvee_{p\in S}y_i(p)$; otherwise $H$ is undefined. Take $r=\lfloor\log_2\tau_n\rfloor+1$ copies of $H$, where $\tau_n=n(\lceil n/2\rceil+1)$, and a $2^r$-cell array of certificate descriptions. Their $H$ outputs address a cell. The total function accepts iff all $H$ inputs lie in their domains and the addressed cell contains valid local certificates for those outputs. Section 3.2 of [AIK26] specifies the checks and all malformed encodings.
Formal definition
Let $H(x,y)=\bigvee_{p\in S}y_i(p)$ if $x$ satisfies the unique term $T_{i,S}$ of \(\mathrm{AIKuD}\), and leave $H$ undefined otherwise. Fix the verifier $A(x,y,\beta,z)$ from [AIK26, Lemma 3.3 and Appendix D.1], $\tau_n=n(\lceil n/2\rceil+1)$ and $r=\lfloor\log_2\tau_n\rfloor+1$. An input has $r$ pairs $(x^{(t)},y^{(t)})$ and $2^r$ cells, each holding $r$ descriptions. $$F_n=1\iff\exists\beta\in\{0,1\}^r:\ \forall t\in[r],\ H(x^{(t)},y^{(t)})=\beta_t \ \text{and}\ A(x^{(t)},y^{(t)},\beta_t,z^{(t)}_\beta)=1.$$ Every other input rejects. Cell $\beta$ contains the descriptions $z^{(t)}_\beta$; the source's bit encoding and verifier are part of this definition.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{C}(f)\) Certificate complexity | \(\Omega(n^2)\) | Theorem 2.1, with explicit lower bound n(⌈n/2⌉+1). AIK26 |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(O(\sqrt n\log^3 n)\) | Theorem 2.1. AIK26 |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Theta(n\log^2 n)\) | Theorem 2.3; exact amplification and the count-field restriction. AIK26 |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Theta(n\log^2 n)\) | Theorem 2.3. AIK26 |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Omega(n^2)\) | C=Ω(n²); under the zoo’s expected-cost zero-error convention, R₀=Ω(C), so this retains an Ω bound rather than a literal coefficient-one inequality. AIK26 |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(O(\sqrt n\log^3 n)\) | Approximate degree ≤2Q; an immediate consequence of the quantum algorithm. BBCMdW01 AIK26 |
Separations its values prove — computed, not recorded
Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 3 in total.
-
\(\mathrm{R}_{0}(f_n) = \Omega\big(\widetilde{\deg}_{\varepsilon}(f_n)^{4}\big)\)from \(\mathrm{R}_{0}(f) = \Omega(n^2)\) against \(\widetilde{\deg}_{\varepsilon}(f) = O(\sqrt n\log^3 n)\)
-
\(\mathrm{R}_{0}(f_n) = \Omega\big(\mathrm{Q}_{\mathrm{E}}(f_n)^{2}\big)\)from \(\mathrm{R}_{0}(f) = \Omega(n^2)\) against \(\mathrm{Q}_{\mathrm{E}}(f) = \Theta(n\log^2 n)\)
-
\(\mathrm{R}_{0}(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{2}\big)\)from \(\mathrm{R}_{0}(f) = \Omega(n^2)\) against \(\mathrm{Q}_{0}(f) = \Theta(n\log^2 n)\)
Cited as a witness by
-
\(\mathrm{C}(F_n)=\Omega(\mathrm{Q}(F_n)^4/\log^{12}\mathrm{Q}(F_n))\)
-
\(\mathrm{C}(F_n)=\Omega(\mathrm{Q}_{\mathrm{E}}(F_n)^2/\log^4\mathrm{Q}_{\mathrm{E}}(F_n))\)
-
\(\mathrm{C}(F_n)=\Omega(\mathrm{Q}_0(F_n)^2/\log^4\mathrm{Q}_0(F_n))\)
-
\(\mathrm{R}_0(F_n)=\Omega(\mathrm{Q}(F_n)^4/\log^{12}\mathrm{Q}(F_n))\)