Quantum evasiveness conjecture?

Question

A property of simple $n$-vertex graphs is said to be evasive if its deterministic query complexity is exactly maximal, $\binom{n}{2}$ (that is, the best algorithm must query all $\binom{n}{2}$ possible edges in the worst case). The Evasiveness Conjecture (see here) is a strengtheneing due to Karp says that all nontrivial monotone graph properties are evasive. The current best lower bound of $(1/3 - o(1))n^2$ is due to Scheidweiler and Triesch, and the evasiveness conjecture is known to hold for various classes of graphs (and this). The smallest open case is for graphs on 10 vertices, see e.g. Angel & Borja.

Very recently, Aaronson, Ben-David, Kothari, and Tal used Huang's proof the Sensitivity Conjecture to show that the quantum query complexity of any nontrivial monotone graph property is $\Omega(n)$, which is optimal up to a constant.

The Evasiveness Conjecture conjectures the exact form of the deterministic query complexity of such properties.

Is there a natural conjecture as to the exact form of the quantum query complexity of nontrivial monotone graph properties? If so, what is it, and how close/far are the current results from it?

The Evasiveness Conjecture has also been generalized to various classes of functions; I'd be interested to know about the same in the quantum setting as well.

Buhrman, Cleve, de Wolf, and Zalka (1999) mention quantum evasiveness, but only to show that some monotone graph properties do not require $\Omega(n^2)$ quantum queries. I had trouble finding anywhere else that discusses quantum evasiveness.

Update 2020 May 05: As pointed out by smapers in the answer & its comments, since the quantum query complexity of non-emptiness is $\Theta(n)$ (using Grover for the upper bound) and that of connectivity is $\Theta(n^{3/2})$, there is no function $f(n)$ that only depends on $n$. Leading me to refine the question to:

Is there some nice (meta-)property of the monotone property such that there is a reasonable conjecture that depends on $n$ and that meta-property?

Really I'm just curious about a conjecture more refined than big-Theta.

Answer 1

Since the quantum query complexity typically denotes the bounded-error quantum query complexity, there's some ambiguity. A more precise question could be: "What is the quantum query complexity to decide nontrivial monotone graph properties with probability at least $2/3$?".

A natural example in this context is the monotone property of having a single edge. Since Grover search is optimal for this problem, its bounded-error quantum query complexity seems like the natural candidate.

---

update (2020 May 5):

Since the monotone property of connectivity has quantum query complexity $\Theta(n^{3/2})$ (see here), and the property of having a single edge has quantum query complexity $\Theta(n)$, there is actually no hope for a simple function $f(n)$ only dependent on $n$ to fully characterize the quantum query complexity of monotone graph properties (even up to constants). This is in contrast to what is conjectured for the classical deterministic query complexity.

Alternatively, one could ask about "the minimum possible quantum query complexity of a nontrivial monotone graph property" (as formulated in the paper by Aaronson, Ben-David, Kothari, and Tal). In this case, a simple function of $n$ might still be possible, and the complexity of having a single edge again seems like a natural candidate.

---

update 2 (2020 May 5):

Answering the updated question, a possible candidate for the additional property would be the (worst-case) certificate size $c$ of the property. A corresponding candidate for the query complexity would then be $\Theta(\sqrt{n^2 c})$, which describes the quantum query complexity when using Grover search on a graph that is empty apart from a single certificate (i.e., a minimal graph having the property). This would be consistent with the examples of having a single edge ($c = 1$) and connectivity ($c = n-1$).

Here's some other consistent examples:

• Nonplanarity. Certificate size $c \in \Theta(n)$ (consider the graph obtained by replacing all edges of a $K_5$ graph by paths of length $\Omega(n)$). The quantum query complexity is $\Theta(n^{3/2}) = \Theta(\sqrt{n^2c})$ (link).
• Having more than $\binom{n}{2}/2$ edges. Certificate size $\binom{n}{2}/2+1$. The quantum query complexity is $\Theta(n^{3/2}) = \Theta(\sqrt{n^2c})$ (link).
• Triangle finding. Has certificate size $c = 3$. The current best upper bound is $\tilde{O}(n^{5/4})$ (Le Gall), but the best lower bound is only $\Omega(n) = \Omega(\sqrt{n^2 c})$.$^1$

$^1$At the end of his QIP talk (link), Le Gall does mention that he would be "surprised" if the quantum query complexity were $\tilde O(n)$.

Answer 2

If you want a conjecture without big-Oh notation for bounded-error quantum query complexity (or for that matter bounded-error randomized query complexity), this will be messy since the bound will have to depend on $\epsilon$, the allowed error. For example, the property "G contains an edge" is evasive for deterministic algorithms, but a $\epsilon$-error randomized algorithm can get by with fewer queries, and this depends on $\epsilon$.

To add to the examples above, there is a monotone graph property with complexity $\Theta(n^{1+\alpha})$ for any $\alpha\in[0,1]$. The property is simply "G has more than k edges" which has quantum query complexity $\Theta(n\sqrt{k})$, which follows from tight bounds on the quantum query complexity of the threshold function.

I also very much doubt that the quantum query complexity of all monotone graph properties is simply $\Theta(n\sqrt{C(P)})$ where $C(P)$ is the certificate complexity of the property. The reason this is consistent with known lower bounds is that this is the best lower bound that can be shown by the original adversary method, which is the most popular technique for proving lower bounds. We have very few lower bounds that go beyond what can be shown by the original adversary method.

I conjecture that the graph property "G contains a clique of size k" will have quantum query complexity $\omega(n)$ for constant $k$, even though its certificate complexity is constant. I think this should already be the case for $k=3$, which is the triangle problem, but we're not able to prove this.