Q The Query Complexity Zoo
\(\mathrm{AIKCS}\)

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 separating-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

MeasureValueNotes
\(\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.

Cited as a witness by