<p>Since the quantum query complexity typically denotes the <em>bounded-error</em> 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 <span class="math-container">$2/3$</span>?".</p>

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

<hr>

<p><strong>update (2020 May 5):</strong></p>

<p>Since the monotone property of <em>connectivity</em> has quantum query complexity <span class="math-container">$\Theta(n^{3/2})$</span> (see <a href="https://arxiv.org/abs/quant-ph/0401091" rel="nofollow noreferrer">here</a>), and the property of <em>having a single edge</em> has quantum query complexity <span class="math-container">$\Theta(n)$</span>, there is actually no hope for a simple function <span class="math-container">$f(n)$</span> only dependent on <span class="math-container">$n$</span> 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.</p>

<p>Alternatively, one could ask about "the <em>minimum</em> possible quantum query complexity of a nontrivial monotone graph property" (as formulated in the paper by <a href="https://arxiv.org/abs/2004.13231" rel="nofollow noreferrer">Aaronson, Ben-David, Kothari, and Tal</a>). In this case, a simple function of <span class="math-container">$n$</span> might still be possible, and the complexity of <em>having a single edge</em> again seems like a natural candidate.</p>

<hr>

<p><strong>update 2 (2020 May 5):</strong></p>

<p>Answering the updated question, a possible candidate for the additional property would be the (worst-case) <em>certificate size</em> <span class="math-container">$c$</span> of the property. A corresponding candidate for the query complexity would then be <span class="math-container">$\Theta(\sqrt{n^2 c})$</span>, 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 <em>having a single edge</em> (<span class="math-container">$c = 1$</span>) and <em>connectivity</em> (<span class="math-container">$c = n-1$</span>).</p>

<p>Here's some other consistent examples:</p>

<ul>
<li><em>Nonplanarity.</em> Certificate size <span class="math-container">$c \in \Theta(n)$</span> (consider the graph obtained by replacing all edges of a <span class="math-container">$K_5$</span> graph by paths of length <span class="math-container">$\Omega(n)$</span>). The quantum query complexity is <span class="math-container">$\Theta(n^{3/2}) = \Theta(\sqrt{n^2c})$</span> (<a href="http://www.kecl.ntt.co.jp/people/tani.seiichiro/pdf/SmallOnSets.pdf" rel="nofollow noreferrer">link</a>).</li>
<li><em>Having more than <span class="math-container">$\binom{n}{2}/2$</span> edges.</em> Certificate size <span class="math-container">$\binom{n}{2}/2+1$</span>. The quantum query complexity is <span class="math-container">$\Theta(n^{3/2}) = \Theta(\sqrt{n^2c})$</span> (<a href="https://arxiv.org/abs/quant-ph/9802049" rel="nofollow noreferrer">link</a>).</li>
<li><em>Triangle finding.</em> Has certificate size <span class="math-container">$c = 3$</span>. The current best upper bound is <span class="math-container">$\tilde{O}(n^{5/4})$</span> (<a href="https://ieeexplore.ieee.org/abstract/document/6979006/" rel="nofollow noreferrer">Le Gall</a>), but the best lower bound is only <span class="math-container">$\Omega(n) = \Omega(\sqrt{n^2 c})$</span>.<span class="math-container">$^1$</span></li>
</ul>

<p><span class="math-container">$^1$</span>At the end of his QIP talk (<a href="https://www.youtube.com/watch?v=Lwrf0wGzIDM" rel="nofollow noreferrer">link</a>), Le Gall does mention that he would be "surprised" if the quantum query complexity were <span class="math-container">$\tilde O(n)$</span>.</p>

CC BY-SA 4.0
2020-05-04T19:16:55.747Z
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.
Joshua Grochow
CC BY-SA 4.0
2020-05-04T19:23:18.217Z
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?
smapers
CC BY-SA 4.0
2020-05-04T19:40:17.007Z
The quantum query complexity of connectivity is $\Theta(n^{3/2})$ (see [here](https://arxiv.org/abs/quant-ph/0401091)).
smapers
CC BY-SA 4.0
2020-05-04T23:38:08.417Z
So...does connectivity already invalidate your proposed Conjecture, or did I misunderstand your proposal? Also, the issue is that from one problem you can't necessarily tell. It's like saying that f(2)=4 and claiming that the only possible Conjecture is f(n)=2n. Any Conjecture must be *compatible* with Grover for nonemptiness, but the Conjecture could depend on some property of the graph property as well.
Joshua Grochow
CC BY-SA 4.0
2020-05-05T05:25:19.500Z
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?
smapers
CC BY-SA 4.0
2020-05-05T14:22:13.430Z
I was really just hoping for as exact an expression as possible, ideally without big-Oh notation. If that must depend on what property we're talking about (which apparently it must), then so be it. So, in combination with connectivity, I'd actually take your answer to be: there is no single function f(n), that only depends on n, that works. But whatever the answer is, a reasonable conjecture is that it agrees w/ Grover's algorithm for non-emptiness and ??? for connectivity. (Is there a natural proposal for connectivity?)
Joshua Grochow
CC BY-SA 4.0
2020-05-05T14:43:16.357Z
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.
smapers
CC BY-SA 4.0
2020-05-04T18:50:16.947Z
2020-05-05T15:59:46.463Z
2020-05-05T15:59:46.463Z
smapers
<p>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 <span class="math-container">$\epsilon$</span>, the allowed error. For example, the property "G contains an edge" is evasive for deterministic algorithms, but a <span class="math-container">$\epsilon$</span>-error randomized algorithm can get by with fewer queries, and this depends on <span class="math-container">$\epsilon$</span>.</p>

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

<p>I also very much doubt that the quantum query complexity of all monotone graph properties is simply <span class="math-container">$\Theta(n\sqrt{C(P)})$</span> where <span class="math-container">$C(P)$</span> 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.</p>

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

CC BY-SA 4.0
2020-05-06T06:13:02.103Z
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?
smapers
CC BY-SA 4.0
2020-05-06T22:22:33.147Z
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.
Robin Kothari
CC BY-SA 4.0
2020-05-05T18:23:46.237Z
2020-05-05T18:23:46.237Z
Robin Kothari
<p>A property of simple <span class="math-container">$n$</span>-vertex graphs is said to be <em>evasive</em> if its deterministic query complexity is exactly maximal, <span class="math-container">$\binom{n}{2}$</span> (that is, the best algorithm must query all <span class="math-container">$\binom{n}{2}$</span> possible edges in the worst case). The Evasiveness Conjecture (see <a href="https://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture" rel="nofollow noreferrer">here</a>) is a strengtheneing due to Karp says that all nontrivial monotone graph properties are evasive. The current best lower bound of <span class="math-container">$(1/3 - o(1))n^2$</span> <a href="https://doi.org/10.1137%2F120888703" rel="nofollow noreferrer">is due to Scheidweiler and Triesch</a>, and the evasiveness conjecture is known to hold for <a href="https://doi.org/10.1109%2FSFCS.1983.4" rel="nofollow noreferrer">various</a> <a href="https://doi.org/10.1137%2F0217031" rel="nofollow noreferrer">classes</a> of <a href="https://doi.org/10.1137%2FS0097539700382005" rel="nofollow noreferrer">graphs</a> (and <a href="https://dx.doi.org/10.4230/LIPIcs.STACS.2010.2445" rel="nofollow noreferrer">this</a>). The smallest open case is for graphs on 10 vertices, see e.g. <a href="https://arxiv.org/abs/1603.04412" rel="nofollow noreferrer">Angel &amp; Borja</a>.</p>

<p>Very recently, <a href="https://eccc.weizmann.ac.il/report/2020/066/" rel="nofollow noreferrer">Aaronson, Ben-David, Kothari, and Tal</a> used Huang's proof the Sensitivity Conjecture to show that the <em>quantum</em> query complexity of any nontrivial monotone graph property is <span class="math-container">$\Omega(n)$</span>, which is optimal up to a constant.</p>

<p>The Evasiveness Conjecture conjectures the exact form of the deterministic query complexity of such properties. </p>

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

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

<p><a href="https://arxiv.org/abs/cs/9904019" rel="nofollow noreferrer">Buhrman, Cleve, de Wolf, and Zalka</a> (1999) mention quantum evasiveness, but only to show that some monotone graph properties do not require <span class="math-container">$\Omega(n^2)$</span> quantum queries. I had trouble finding anywhere else that discusses quantum evasiveness.</p>

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

<blockquote>
  <p>Is there some nice (meta-)property of the monotone property such that there is a reasonable conjecture that depends on <span class="math-container">$n$</span> and that meta-property?</p>
</blockquote>

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

CC BY-SA 4.0
2020-05-05T14:45:36.427Z
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](https://arxiv.org/abs/1407.0085), but the best lower bound is $\Omega(n)$.
smapers
CC BY-SA 4.0
2020-05-05T14:48:33.717Z
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).
smapers
CC BY-SA 4.0
2020-05-05T15:19:14.877Z
@smapers: Oooh, I like it! Why not add to your answer (or did you just think of it after updating your answer)?
Joshua Grochow
CC BY-SA 4.0
2020-05-05T16:03:00.087Z
I added it to my answer.
smapers
<quantum-computing><query-complexity>
Quantum evasiveness conjecture?
Joshua Grochow
# Quantum evasiveness conjecture?

(Asked by: username_0 on 2020-05-04)

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](https://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture)) 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](https://doi.org/10.1137%2F120888703), and the evasiveness conjecture is known to hold for [various](https://doi.org/10.1109%2FSFCS.1983.4) [classes](https://doi.org/10.1137%2F0217031) of [graphs](https://doi.org/10.1137%2FS0097539700382005) (and [this](https://dx.doi.org/10.4230/LIPIcs.STACS.2010.2445)). The smallest open case is for graphs on 10 vertices, see e.g. [Angel & Borja](https://arxiv.org/abs/1603.04412).

Very recently, [Aaronson, Ben-David, Kothari, and Tal](https://eccc.weizmann.ac.il/report/2020/066/) 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](https://arxiv.org/abs/cs/9904019) (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 username_1 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.

**Tags:** quantum-computing, query-complexity

> **Comments:**
> **username_1**: 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](https://arxiv.org/abs/1407.0085), but the best lower bound is $\Omega(n)$.  
> **username_1**: 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).  
> **username_0**: @username_1: Oooh, I like it! Why not add to your answer (or did you just think of it after updating your answer)?  
> **username_1**: I added it to my answer.  

---

## 2 answers

### Answer by username_1 on 2020-05-04. Score: 5

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](https://arxiv.org/abs/quant-ph/0401091)), 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](https://arxiv.org/abs/2004.13231)). 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](http://www.kecl.ntt.co.jp/people/tani.seiichiro/pdf/SmallOnSets.pdf)).
* *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](https://arxiv.org/abs/quant-ph/9802049)).
* *Triangle finding.* Has certificate size $c = 3$. The current best upper bound is $\tilde{O}(n^{5/4})$ ([Le Gall](https://ieeexplore.ieee.org/abstract/document/6979006/)), but the best lower bound is only $\Omega(n) = \Omega(\sqrt{n^2 c})$.$^1$

$^1$At the end of his QIP talk ([link](https://www.youtube.com/watch?v=Lwrf0wGzIDM)), Le Gall does mention that he would be "surprised" if the quantum query complexity were $\tilde O(n)$.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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?  
> **username_1**: The quantum query complexity of connectivity is $\Theta(n^{3/2})$ (see [here](https://arxiv.org/abs/quant-ph/0401091)).  
> **username_0**: So...does connectivity already invalidate your proposed Conjecture, or did I misunderstand your proposal? Also, the issue is that from one problem you can't necessarily tell. It's like saying that f(2)=4 and claiming that the only possible Conjecture is f(n)=2n. Any Conjecture must be *compatible* with Grover for nonemptiness, but the Conjecture could depend on some property of the graph property as well.  
> **username_1**: 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?  
> **username_0**: I was really just hoping for as exact an expression as possible, ideally without big-Oh notation. If that must depend on what property we're talking about (which apparently it must), then so be it. So, in combination with connectivity, I'd actually take your answer to be: there is no single function f(n), that only depends on n, that works. But whatever the answer is, a reasonable conjecture is that it agrees w/ Grover's algorithm for non-emptiness and ??? for connectivity. (Is there a natural proposal for connectivity?)  
> **username_1**: 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.  

---

### Answer by username_2 on 2020-05-05. Score: 3

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.

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

---

