Bounding the gap between quantum and deterministic query complexity

Question

Although exponential separations between bounded-error quantum query complexity ($Q(f)$) and deterministic query complexity ($D(f)$) or bounded-error randomized query complexity ($R(f)$) are known, they only apply to certain partial functions. If the partial functions have some special structures then they are also polynomially related with $D(f) = O(Q(f)^9))$. However, I am mostly concerned about total functions.

In a classic paper it was shown that $D(f)$ is bounded by $O(Q(f)^6)$ for total functions, $O(Q(f)^4)$ for monotone total functions, and $O(Q(f)^2)$ for symmetric total functions. However, no greater than quadratic separations are known for these sort of functions (this separation is achieved by $OR$ for example). As far as I understand, most people conjecture that for total functions we have $D(f) = O(Q(f)^2)$. Under what conditions has this conjecture been proven (apart from symmetric functions)? What is the best current bounds on decision-tree complexity in terms of quantum query complexity for total functions?

Answer 1

As far as I know, the general bounds you state are essentially the best known. Changing the model slightly, Midrijanis has shown the bound that $D(f) = O(Q_E(f))^3$, where $Q_E(f)$ is the exact quantum query complexity of $f$; there are also tighter bounds known in terms of one-sided error (see Section 6 of this paper).

In terms of more specific, but still general, classes of functions, there is a paper of Barnum and Saks which shows that all read-once functions on $n$ variables have quantum query complexity $\Omega(\sqrt{n})$.

Although this progress has been limited, there has been considerable progress in lower bounding the quantum query complexity of specific functions; see this review for details (or e.g. the more recent paper of Reichardt, which proves that the most general version of the ''adversary'' bound characterises quantum query complexity).

Answer 2

I like Ashley Montanaro's answer, but I thought I would also include a set of functions for which the conjecture is known.

A set of functions which is often of interest is functions with constant-sized 1-certificates. This class of problems includes things like $OR$, distinctness, collision, triangle-finding and many other problems (not in the HSP-family) which have been shown to have query complexity separations.

For a constant-sized 1-certificate total function $f$, we have $D(f) = O(Q(f)^2)$.

---

Details:

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 1-certificate complexity $C_1(f) = \max_{x | f(x) = 1} C_x(f)$ (The 0-certificate complexity is the same but restricted to $f(x) = 0$).

You can show that $Q(f) \geq \sqrt{bs(f)} \geq 2C_0(f)/2^{C_1(f)} + 1$. Then you can use the algorithm presented in Buhrman and de Wolf's survey to show that: $D(f) \leq C_1(f)bs(f) \leq C_0(f)C_1(f)$