We construct a total Boolean function $f$ for which $Q(f) = \widetilde{O}(\sqrt[4]{C(f)})$, where $Q(f)$ denotes the bounded-error quantum query complexity and $C(f)$ denotes the certificate complexity. This resolves a longstanding open question and is tight up to logarithmic factors.
We construct a total Boolean function f for which Q(f)=O(4C(f)), where Q(f) denotes the bounded-error quantum query complexity and C(f) denotes the certificate complexity. This resolves a longstanding open question and is tight up to logarithmic factors.
Certificate complexity (C(f)) is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity (D) and other query models such as bounded-error randomized and quantum complexity (R,Q), but not as well for quantum zero-error (Q0) and exact query complexity (QE), where there is no agreed-upon certificate 'object' (even for Q). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of C,RC (randomized certificate complexity) and QC (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on QE and Q0, the quantum analogues of D and R0, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for Q0, but rational degree and Q are asymptotically smaller.
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)=Ω~(deg~(G)4), where C denotes certificate complexity and deg~ denotes 1/3-approximate degree. This is optimal up to polylogarithmic factors, since every total Boolean function f satisfies C(f)≤O(deg~(f)4) by the classical block-sensitivity bounds of Nisan and Nisan--Szegedy. Thus the result closes the gap between these two measures and improves the previously best known separation C(f)=Ω~(deg~(f)3) by Balodis, Ben-David, Göös, Jain, and Kothari. The construction starts from the partial function they used to quadratically separate 0-certificate complexity from unambiguous 1-certificate complexity. It already has the required certificate hardness, but its 0-certificates are unstructured, which blocks the derivation of a low-degree verifier. We keep its 1-condition and restrict the 0-inputs to those certified by a structured family whose validity admits a low-degree approximant, while preserving the quadratic hardness. The partial function with its low-degree verifier is then fed through the cheat-sheet framework to yield the total function G with the claimed separation. The main technical ingredient is an approximate polynomial that verifies the certificate in degree O~(n). The verifier forms a low-degree count W of the candidate 1-certificates that remain compatible with the asserted 0-certificate, and tests whether this count is zero. Crucially, the construction ensures that W never exceeds O~(n), instead of the Θ(n2) candidate pairs it counts bringing the verification down to degree O~(n).
One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.
For a (possibly partial) Boolean function f:{0,1}n→{0,1} as well as a query complexity measure M which maps Boolean functions to real numbers, define the composition limit of M on f by M∗(f)=limk→∞M(fk)1/k.
We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show R0∗(f)=max{R∗(f),C∗(f)}. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability.
Along the way, we prove various combinatorial properties of measures and composition limits.