A certificate for an input $x$ is a subset of bits $S \subseteq \{1,...,n\}$ such that for all inputs $y$, $(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$. Then $C_x(f)$ is the minimum size of a certificate for input $x$ and the certificate complexity $C(f) = \max_x C_x(f)$. Thus, certificate complexity can be seen as a form of query complexity for nondeterministic machines: guess the smallest certificate for $x$ and then verify with $C_x(f)$ many queries. This is used as an intermediate complexity measure when proving relationships between deterministic query complexity ($D(f)$) and quantum query complexity ($Q_2(f)$).

Is it known, or believed that for a total functions $f$, $C(f) \leq Q_2(f)$? Are there any total functions $f$, where it is know that $C(f) \in o(Q_2(f))$ (or vice-versa)? And just for fun: does this question correspond in some formal way to the questions associated NP vs. BQP?

  • 2
    $\begingroup$ well, query complexity can only separate classes in a relativized world. And we know that $NP\nsubseteq BQP$ relative to an oracle because of the lower bound on search. You cannot separate NP from BQP using decision trees or certificate complexity, these are weaker models of computation. $\endgroup$ Mar 8 '11 at 22:28

In the paper Negative weights make adversaries stronger, Lee, Spalek, and Hoyer give a function for which $ADV^{±}(f)= \Omega( ({C_0(f)C_1(f)})^{0.549})$, where $ADV^±$ denotes the general adversary lower bound. This lower bound has since been proved to characterize quantum query complexity.

This function is obtained by composing a function on a few bits bits with itself $d$ times. You get in the end $C_0(f)=C_1(f)=3^d$ and thus $C(f) \in o(Q_2(f))$.


There are total functions with $Q_2 = o(C)$ and total functions with $C = o(Q_2)$. Marc gave one direction.

For the other direction, the OR function on $n$ inputs works. The certificate complexity is $n$ and the quantum query complexity is $\sqrt{n}$, by Grover's search algorithm. However, this example really only highlights that the correct quantity to look at is the geometric mean of the true and false certificate complexities, $\sqrt{C_0 C_1}$, and not the certificate complexity $C = \max\{C_0, C_1\}$.

A better example is the function OR($n/2$ inputs, AND($n/2$ inputs)). The 1 and 0 certificate complexities are $n/2$ and $n/2+1$ but the adversary bounds and therefore $Q_2$ are $\sqrt{n}$. (Any read-once AND-OR formula of size $n$ has $\sqrt{n}$ adversary bounds.)

To my knowledge, for functions with a transitive symmetry group on the input bits, e.g., symmetrical under cyclic permutations, no examples are known with $ADV^{\pm} < \sqrt{C_0 C_1}$. (On the other hand, the original adversary bound satisfies $ADV \leq \sqrt{C_0 C_1}$ for every total function; see, e.g., [Spalek and Szegedy: "All quantum adversary bounds are equivalent" Theorem 3.2].)

Finally, if the co-domain of the total function is non-boolean, the most natural quantity to consider is $\max_{i \neq j} \sqrt{C_i C_j}$. See the above Spalek and Szegedy theorem for details, but it should not be surprising. Note that a quantity like $(\prod_{i=1}^{m} C_i)^{1/m}$ is not well behaved when you extend the function's codomain. There are good questions here.

Another reference you might find interesting is [Aaronson, quant-ph/0210020]. Aaronson defines and relates randomized and quantum certificate complexities in a natural manner.

  • $\begingroup$ does the geometric mean continue to make sense when we look at functions to an arbitrary set S of size m > 2? Would we then just have $(C_0C_1...C_{m - 1})^{1/m}$ or something more subtle? $\endgroup$ Mar 11 '11 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.