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)$

Answer 3

If we restrict attention to graph properties, then we can prove slightly improved bounds compared to the general bounds you mention:

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.

First I think the 6th power bound can be improved to 4th power for graph properties. This follows from [1], where they show that any graph property has query complexity at least $\Omega(N^{1/4})$, where $N$ is the input size, which is quadratic in the number of vertices. Of course the classical query complexity is at most $N$.

The 4th power bound for monotone total functions can be improved to the 3rd power for monotone graph properties. This follows from an unpublished observation of Yao and Santha (mentioned in [2]) that all monotone graph properties have quantum query complexity $\Omega(N^{1/3}\log^{1/6}N)$.

[1] Sun, X.; Yao, AC.; Shengyu Zhang, "Graph properties and circular functions: how low can quantum query complexity go?," Computational Complexity, 2004. Proceedings. 19th IEEE Annual Conference on , vol., no., pp.286,293, 21-24 June 2004 doi: 10.1109/CCC.2004.1313851

[2] Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2005), "Quantum algorithms for the triangle problem", Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Vancouver, British Columbia: Society for Industrial and Applied Mathematics, pp. 1109–1117, arXiv:quant-ph/0310134.

Answer 4

A lot of progress has been made on this question in 2015.

First, in arXiv:1506.04719 [cs.CC], the authors have improved on the quadratic separation by showing a total function $f$ with

$$ Q(f) = \widetilde{O}(D(f)^{1/4}). $$

On the other hand, in arXiv:1512.04016 [quant-ph], it was shown that the quadratic relationship between quantum and deterministic query complexity holds when the domain of the function is very small.