PreprintarXiv licencearXiv
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 R1(f) = Θ(√(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) = Õ(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 Õ(√(C(F))). We also prove matching lower bounds for these two measures on F.
Related
- Randomized query complexity can beat certificate complexity
- Complexity separations for optimal matchgate-Clifford synthesis
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
- Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
BibTeX
@misc{ambainis2026nearoptimal,
title = {{Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity}},
author = {Andris Ambainis and Jānis Iraids and Martins Kokainis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.11664},
eprint = {2609.11664},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11664},
}
RIS
TY - UNPB
TI - Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
AU - Andris Ambainis
AU - Jānis Iraids
AU - Martins Kokainis
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.11664
UR - https://arxiv.org/abs/2609.11664
AB - 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) = Θ(√(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) = Õ(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 Õ(√(C(F))). We also prove matching lower bounds for these two measures on F.
ER -