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$.
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...
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
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.· Electron. Colloquium Comput....· 0 citations
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...
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
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.