Skip to content
Preprint

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

Sep 2026 · 0 citations · 18 references
Physics

TL;DR

A total Boolean function is constructed whose randomized query complexity with one-sided error satisfies ${R}_1(f) = \Theta(\sqrt{{C}(f)})$, which is optimal even when two-sided error is allowed.

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) = \widetilde 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 $\widetilde O(\sqrt{{C}(F)})$. We also prove matching lower bounds for these two measures on $F$.

View source

Similar papers

Aug 2026

An Optimal Separation Between Certificate Complexity and Approximate Degree

We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions $G$ with $$ C(G) = \tilde{\Omega}(\tilde{deg}(G)^4), $$ where $C$ denotes certificate complexity and $\tilde{deg}$ denotes $1/3$-approximate degree. This is optimal up...

K. Balodis · 2 citations · ⚡1
Preprint Sep 2026

Improved Quantum Query Bounds for Boolean Matrix Product Verification

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound o...

Amin Shiraz Gilani, François Le Gall, Xing-Yu Zhou · 0 citations
Sep 2026

Certification complexity of Boolean functions

This work studies an operational notion of certification and applies it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures.

Chandrima Kayal, Sophie Laplante, É. Larroque et al. · 0 citations
Preprint Sep 2026

Randomized query complexity can beat certificate complexity

A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f)<<C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. T...

S. Ben-David, Robin Kothari · 1 citation · ⚡1
Preprint Oct 2026

Optimal query complexity for fractional quantum evolution

The argument reduces any $N$-query circuit to the approximation of $e^{it\theta}$ by a trigonometric polynomial with degree bounded by $O(N)$ by a trigonometric polynomial with degree bounded by $O(N)$ together with Remez inequality to establish a matching lower bound for arbitrary query algorithms.

A. Liu, Adam Wesołowski, Jayne Thompson et al. · 0 citations
Preprint Sep 2026

Quantum Query Advantage Requires Space

The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.

Minbo Gao, Zheng-Feng Ji, Zi-Yi Xie · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.