{"id":"arxiv/2609.11664","url":"https://arxiv.org/abs/2609.11664","tags":["quant-ph"],"score":0,"title":"Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity","domain":"quant-ph","source":"arxiv","authors":["Andris Ambainis","Jānis Iraids","Martins Kokainis"],"reviews":0,"subject":"quant-ph","summary":"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) = Θ(\\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) = \\widetilde O({C}(F)^{1/4})$, attaining the general quartic bound up to polylogarithmic factors. For the same function, both…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-10","reactions":{}}