Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity

Abstract

We study how large the certificate complexity $C(f)$ of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function $f$ whose randomized query complexity with one-sided error satisfies $R_1(f)=\Theta (\sqrt{C(f)})$. This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function $F$ with bounded-error quantum query complexity $Q(F)=\tilde{O}(C(F{)}^{1/4})$, attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are $\tilde{O}(\sqrt{C(F)})$. We also prove matching lower bounds for these two measures on $F$.