We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced \nand formula. We show that the query complexity is $\tilde\Theta(d^{(k+1)/2})$ for 0-certificates, and $\tilde\Theta(d^{k/2})$ for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is $\tilde O(d^{(k+1)/2})$. Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced \nand formula. We show that the query complexity is Θ~(d(k+1)/2) for 0-certificates, and Θ~(dk/2) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O~(d(k+1)/2). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
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.
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting Q(f∘g)=Θ(Q(f)Q(g)) for all Boolean functions f and g; a direct sum theorem asserting that computing k copies of a function (or search problem) costs Ω(k) times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires Ω(k) times the cost of computing one copy to bounded error.
However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution μ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing k copies of f when the input comes from the product distribution μk instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions.
In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the γ2 norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted and unweighted methods of Ambainis and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, it can be shown that adversary methods can only prove lower bounds for Boolean functions f in O(min(nC0(f),nC1(f))), where C0,C1 is the certificate complexity and n is the size of the input.
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)=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 O(C(F)). We also prove matching lower bounds for these two measures on F.
We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to |0> on a 0-input and a state close to |1> on a 1-input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0-input and 1-input are distinguishable. Using this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zero-error and bounded-error quantum query complexity of f respectively, improving on the previously known sixth power relationship. We also define a query measure based on quantum statistical zero-knowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity. Lastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zero-error quantum query complexity or for QSZK would imply a general lifting theorem for bounded-error quantum query complexity.
We prove a very general lower bound technique for quantum and randomized query complexity, that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks and Szegedy. As an immediate consequence of our main theorem, adversary methods can only prove lower bounds for boolean functions f in O(min(nC0(f),nC1(f))), where C0,C1 is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used by Hoyer, Neerbek and Shi to give a quantum lower bound on ordered search and sorting.