6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ An additional example to keep in mind is the property of having a triangle. The current best bound is $\tilde{O}(n^{5/4})$ by Le Gall, but the best lower bound is $\Omega(n)$. $\endgroup$ – smapers May 5 at 14:45
  • 1
    $\begingroup$ Consistent with these three examples would be $\Theta(\sqrt{n^2 c})$ where $c$ is the certificate size (an edge/triangle/spanning tree). This bound would correspond to using Grover on a graph that is empty apart from a single certificate (i.e., a minimal graph having the property). $\endgroup$ – smapers May 5 at 14:48
  • $\begingroup$ @smapers: Oooh, I like it! Why not add to your answer (or did you just think of it after updating your answer)? $\endgroup$ – Joshua Grochow May 5 at 15:19
  • 1
    $\begingroup$ I added it to my answer. $\endgroup$ – smapers May 5 at 16:03
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How does this compare to the known quantum query complexities of other simple monotone properties, like connectivity? One example is certainly a natural candidate, but would be much more convincing if the same bound was the best known for many properties. $\endgroup$ – Joshua Grochow May 4 at 19:16
  • $\begingroup$ I agree that would provide evidence for the conjecture. However, if the conjecture were true, then the query complexity must necessarily be the one above - do you agree? $\endgroup$ – smapers May 4 at 19:23
  • $\begingroup$ The quantum query complexity of connectivity is $\Theta(n^{3/2})$ (see here). $\endgroup$ – smapers May 4 at 19:40
  • 1
    $\begingroup$ I must've misunderstood your question. I thought you were asking for a constant $C$ such that all monotone graph properties have quantum query complexity exactly $Cn$, in which case the above example seemed to give a natural candidate. But indeed connectivity shows that there's no such $C$, and in fact there's no expression that just depends on $n$ as in the classical case - it must depend on the problem instance. Are you hoping for a more involved expression? $\endgroup$ – smapers May 5 at 5:25
  • 1
    $\begingroup$ I agree, and updated my answer. The quantum connectivity algorithm effectively uses Grover search to find $n-1$ edges among $n^2$ possible edges - so its quantum query complexity would be the natural proposal. $\endgroup$ – smapers May 5 at 14:43
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's very interesting. Any clue on what the complexity of finding say a triangle might be? And any thought on the exact constant of the minimum possible quantum query complexity of a monotone graph property? $\endgroup$ – smapers May 6 at 6:13
  • 2
    $\begingroup$ Because the answer would depend on $\epsilon$, I'm not sure what to conjecture or how meaningful it will be since it will depend on an arbitrary choice. But if I had to conjecture for the adversary bound, I'd conjecture that it is at least the square root of the input size for all monotone graph properties, without any constants. Since "G contains an edge" has ADV equal to this, this would then be optimal. $\endgroup$ – Robin Kothari May 6 at 22:22

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.