<p>I like Ashley Montanaro's answer, but I thought I would also include a set of functions for which the conjecture is known.</p>
<p>A set of functions which is often of interest is functions with constant-sized 1-certificates. This class of problems includes things like <span class="math-container">$OR$</span>, distinctness, collision, triangle-finding and many other problems (not in the HSP-family) which have been shown to have query complexity separations.</p>
<p>For a constant-sized 1-certificate total function <span class="math-container">$f$</span>, we have <span class="math-container">$D(f) = O(Q(f)^2)$</span>.</p>
<hr />
<h3>Details:</h3>
<p>A certificate for an input <span class="math-container">$x$</span> is a subset of bits <span class="math-container">$S \subseteq \{1,...,n\}$</span> such that for all inputs <span class="math-container">$y$</span>, <span class="math-container">$(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$</span>. Then <span class="math-container">$C_x(f)$</span> is the minimum size of a certificate for input <span class="math-container">$x$</span> and the 1-certificate complexity <span class="math-container">$C_1(f) = \max_{x | f(x) = 1} C_x(f)$</span> (The 0-certificate complexity is the same but restricted to <span class="math-container">$f(x) = 0$</span>).</p>
<p>You can <a href="http://www.cs.mcgill.ca/%7Eakazna/Kaznatcheev20110419.pdf" rel="nofollow noreferrer">show</a> that <span class="math-container">$Q(f) \geq \sqrt{bs(f)} \geq 2C_0(f)/2^{C_1(f)} + 1$</span>. Then you can use the algorithm presented in Buhrman and de Wolf's <a href="http://www.sciencedirect.com/science/article/pii/S030439750100144X" rel="nofollow noreferrer">survey</a> to show that: <span class="math-container">$D(f) \leq C_1(f)bs(f) \leq C_0(f)C_1(f)$</span></p>

CC BY-SA 3.0
2011-05-31T21:09:18.737Z
2011-05-31T21:09:18.737Z
2020-06-17T09:38:08.363Z
Artem Kaznatcheev
<p>A lot of progress has been made on this question in 2015.</p>

<p>First, in <a href="http://arxiv.org/abs/1506.04719" rel="nofollow">arXiv:1506.04719 [cs.CC]</a>, the authors have improved on the quadratic separation by showing a total function $f$ with</p>

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

<p>On the other hand, in <a href="http://arxiv.org/abs/1512.04016v1" rel="nofollow">arXiv:1512.04016 [quant-ph]</a>, it was shown that the quadratic relationship between quantum and deterministic query complexity holds when the domain of the function is very small. </p>

CC BY-SA 3.0
2015-12-31T17:10:16.390Z
2015-12-31T17:10:16.390Z
Alessandro Cosentino
<p>If we restrict attention to graph properties, then we can prove slightly improved bounds compared to the general bounds you mention:</p>

<blockquote>
  <p>In a <a href="http://portal.acm.org/citation.cfm?id=502097" rel="nofollow">classic paper</a> 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.</p>
</blockquote>

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

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

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

CC BY-SA 3.0
2014-08-13T19:17:49.327Z
2014-08-13T19:17:49.327Z
Robin Kothari
<p>As far as I know, the general bounds you state are essentially the best known. Changing the model slightly, Midrijanis has <a href="http://arxiv.org/abs/quant-ph/0403168" rel="nofollow">shown</a> the bound that $D(f) = O(Q_E(f))^3$, where $Q_E(f)$ is the <i>exact</i> quantum query complexity of $f$; there are also tighter bounds known in terms of one-sided error (see Section 6 of <a href="http://arxiv.org/abs/quant-ph/0501142" rel="nofollow">this paper</a>).</p>

<p>In terms of more specific, but still general, classes of functions, there is a paper of Barnum and Saks which <a href="http://arxiv.org/abs/quant-ph/0201007" rel="nofollow">shows</a> that all read-once functions on $n$ variables have quantum query complexity $\Omega(\sqrt{n})$.</p>

<p>Although this progress has been limited, there has been considerable progress in lower bounding the quantum query complexity of <i>specific</i> functions; see <a href="http://arxiv.org/abs/quant-ph/0509153" rel="nofollow">this review</a> for details (or e.g. the more recent <a href="http://arxiv.org/abs/0904.2759" rel="nofollow">paper</a> of Reichardt, which proves that the most general version of the ''adversary'' bound characterises quantum query complexity).</p>

CC BY-SA 3.0
2011-04-14T17:38:01.260Z
2011-04-14T17:38:01.260Z
Ashley Montanaro
<p>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 <a href="http://arxiv.org/abs/0911.0996v1">special structures</a> then they are also polynomially related with $D(f) = O(Q(f)^9))$. However, I am mostly concerned about total functions.</p>

<p>In a <a href="http://portal.acm.org/citation.cfm?id=502097">classic paper</a> 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?</p>

<cc.complexity-theory><reference-request><quantum-computing><query-complexity>
Bounding the gap between quantum and deterministic query complexity
Artem Kaznatcheev
# Bounding the gap between quantum and deterministic query complexity

(Asked by: username_0 on 2011-04-14)

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](http://arxiv.org/abs/0911.0996v1) 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](http://portal.acm.org/citation.cfm?id=502097) 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?

**Tags:** cc.complexity-theory, reference-request, quantum-computing, query-complexity

---

## 4 answers

### Answer by username_3 on 2011-04-14. Score: 10 | Accepted answer

As far as I know, the general bounds you state are essentially the best known. Changing the model slightly, Midrijanis has [shown](http://arxiv.org/abs/quant-ph/0403168) 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](http://arxiv.org/abs/quant-ph/0501142)).

In terms of more specific, but still general, classes of functions, there is a paper of Barnum and Saks which [shows](http://arxiv.org/abs/quant-ph/0201007) 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](http://arxiv.org/abs/quant-ph/0509153) for details (or e.g. the more recent [paper](http://arxiv.org/abs/0904.2759) of Reichardt, which proves that the most general version of the ''adversary'' bound characterises quantum query complexity).


---

### Answer by username_0 on 2011-05-31. Score: 5

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](http://www.cs.mcgill.ca/%7Eakazna/Kaznatcheev20110419.pdf) 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](http://www.sciencedirect.com/science/article/pii/S030439750100144X) to show that: $D(f) \leq C\_1(f)bs(f) \leq C\_0(f)C\_1(f)$


---

### Answer by username_1 on 2015-12-31. Score: 3

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

First, in [arXiv:1506.04719 [cs.CC]](http://arxiv.org/abs/1506.04719), 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]](http://arxiv.org/abs/1512.04016v1), it was shown that the quadratic relationship between quantum and deterministic query complexity holds when the domain of the function is very small.


---

### Answer by username_2 on 2014-08-13. Score: 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](http://portal.acm.org/citation.cfm?id=502097) 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.


---

