<p>In the paper <a href="http://arxiv.org/abs/quant-ph/0611054">Negative weights make adversaries stronger</a>, Lee, Spalek, and Hoyer give a function for which $ADV^{&#177;}(f)= \Omega( ({C_0(f)C_1(f)})^{0.549})$, where $ADV^&#177;$ denotes the general adversary lower bound. This lower bound has since been proved to characterize quantum query complexity. </p>

<p>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))$.</p>

CC BY-SA 2.5
2011-03-08T23:24:23.460Z
2011-03-08T23:24:23.460Z
Marc
<p>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 <em>certificate complexity</em> $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)$).</p>

<p>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?</p>

CC BY-SA 2.5
2011-03-08T22:28:04.203Z
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.
Marcos Villagra
<cc.complexity-theory><quantum-computing><query-complexity>
Quantum query complexity and certificate complexity
Artem Kaznatcheev
# Quantum query complexity and certificate complexity

(Asked by: username_0 on 2011-03-08)

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?

**Tags:** cc.complexity-theory, quantum-computing, query-complexity

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-03-08. Score: 5 | Accepted answer

In the paper [Negative weights make adversaries stronger](http://arxiv.org/abs/quant-ph/0611054), 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))$.


---

